【数据结构】二叉树的链式结构，二叉树的遍历，求节点个数以及高度

目录

1. 二叉树链式结构的概念

2. 二叉树的遍历

2.1 前序遍历

2.2 中序遍历

2.3 后序遍历

2.4 层序遍历

3. 二叉树的节点个数以及高度

3.1 二叉树节点个数

3.2 二叉树叶子节点个数

3.3 二叉树的高度

3.4 二叉树第k层节点个数

3.5 二叉树查找值为x的节点

4.  二叉树的创建和销毁

4.1 二叉树的销毁

4.2 通过前序遍历的数组构建二叉树

4.3 判断是否是完全二叉树

5. 编程题

5.1 相同的树

5.2 单值二叉树

5.3 对称二叉树

5.4 二叉树的前序遍历

5.5 另一棵树的子树

6. 选择题

1. 二叉树链式结构的概念

由空树，根节点，根的左子树，根的右子树组成。

2. 二叉树的遍历

2.1 前序遍历

访问根结点的操作发生在遍历其左右子树之前(根左右)。当根节点为NULL时返回。

1 2 3 N N N 4 5 N N 6 N N(空可以省略)

1. 先访问根节点，然后访问根的左子树。

2. 如果根的左子树不为空就把左子树的第一个节点作为根继续往下。

3. 左子树访问完后就访问右子树。

void PreOrder(BTNode* root)
{
	if (root == NULL) return;

	printf("%d ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);
}

2.2 中序遍历

访问根结点的操作发生在遍历其左右子树之中(左根右)。当根节点为NULL时返回。

N 3 N 2 N 1 N 5 N 4 N 6 N(N可以省略) 

1. 先访问根节点的左子树。

2. 将左子树的第一个节点作为根节点继续访问根的左子树。

3. 当左子树为空就返回访问根，然后访问根的右子树。

void InOrder(BTNode* root)
{
	if (root == NULL) return;

	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}

2.3 后序遍历

访问根结点的操作发生在遍历其左右子树之后

N N 3 N 2 N N 5 N N 6 4 1

void PostOrder(BTNode* root)
{
	if (root == NULL) return;

	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->data);
}

2.4 层序遍历

1. 要借助队列。

2. 每个队列节点里面的数据是二叉树节点的指针。

3. 第一步，一开始，当二叉树根节点不为空就入队列。

4. 第二步，当队列不为空就不断出队列，并带入队头数据的左右节点，前提是他们不为空。

void LevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);

	//一开始，当二叉树根节点不为空就入队列。
	if (root != NULL) QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		printf("%d ", front->data);
		if(front->left != NULL) QueuePush(&q, front->left);
		if(front->right != NULL) QueuePush(&q, front->right);
	}
	printf("\n");

	QueueDestroy(&q);
}

3. 二叉树的节点个数以及高度

3.1 二叉树节点个数

1. 返回右子树的节点个数和左子树的节点个数并加上自己。

2. 遇到空节点返回0。

int BinaryTreeSize(BTNode* root)
{
	//遇到空节点返回0。
	if (root == NULL) return 0;

	//返回右子树的节点个数和左子树的节点个数并加上自己。
	return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;	 
}

3.2 二叉树叶子节点个数

1. 找自己的左子树和右子树。

2. 找到叶子就返回1。

int BinaryTreeLeafSize(BTNode* root)
{
	//空节点返回0
	if (root == NULL) return 0;

	//找到叶子就返回1。
	if (root->left == NULL && root->right == NULL) return 1;

	//找自己的左子树和右子树。
	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

3.3 二叉树的高度

1. 遇到空节点返回0。

2. 返回左右子树较大值，并加1也就是加上自己。

int BTHeight(BTNode* root)
{
	//遇到空节点返回0。
	if (root == NULL) return 0;

	//返回左右子树较大值，并加1也就是加上自己。
	int lefthigh = BTHeight(root->left);
	int righthigh = BTHeight(root->right);
	return max(lefthigh, righthigh) + 1;
}

3.4 二叉树第k层节点个数

思路：对于第一层是找第k层，对于第二层是找k-1层，对于第k层就是找当前层，不断让子树去找，每下去一层k就减一，当k==1时就是第k层。

1. k必须大于0。

2. 遇到空节点返回0。

3. 当k == 1返回1。

4. 继续找左右子树。

int BinaryTreeLevelKSize(BTNode* root, int k)
{
	//1. k必须大于0。
	assert(k > 0);

	//2. 遇到空节点返回0。
	if (root == NULL) return 0;

	//3. 当k == 1返回1。
	if (k == 1) return 1;

	//4. 继续找左右子树。
	return BinaryTreeLevelKSize(root->left, k-1) + BinaryTreeLevelKSize(root->right, k-1);
}

3.5 二叉树查找值为x的节点

1. 遇到值相等就返回该节点，遇到空节点就返回空。

2. 先判断根节点的值是否等于x，如果等于就返回根节点，不等于就找自己的左右子树。

3. 记录左右子树的结果，谁找到了就返回，都没找到就返回空。

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL) return NULL;
	if (root->data == x) return root;

	BTNode* left = BinaryTreeFind(root->left, x); 
	if (left != NULL) return left;
	BTNode* right = BinaryTreeFind(root->right, x);
	if (right != NULL) return right;

	return NULL;
}

4.  二叉树的创建和销毁

4.1 二叉树的销毁

1. 利用后序的思想，先释放左子树再释放右子树最后释放自己。

2. 在函数外置空，调用的人自己置空。

void BinaryTreeDestory(BTNode* root)
{
	if (root == NULL) return;
	BinaryTreeDestory(root->left);
	BinaryTreeDestory(root->right);
	free(root);
}

4.2 通过前序遍历的数组构建二叉树

链接：二叉树遍历_牛客题霸_牛客网

1. 用%s接收字符串。

2. 利用前序思想构建二叉树，将当前数组下标对应的值作为根的值构建节点，然后数组下标加一，再然后就去构建他的左子树和右子树。

3. 遇到#代表是空，下标加一然后返回空。

#include <stdio.h>

typedef char BTDataType;
typedef struct BTNode
{
	BTDataType data;
	struct BTNode* left;
	struct BTNode* right;
}BTNode;

BTNode* BuyNode(BTDataType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (node == NULL)
	{
		perror("malloc");
		return NULL;
	}
	node->data = x;
	node->left = node->right = NULL;

    return node;
}

BTNode* Insert(char* arr, int* pi)
{
    if(arr[*pi] == '#')
    {
        (*pi)++;
        return NULL;
    }
    BTNode* root = BuyNode(arr[*pi]);
    (*pi)++;
    root->left = Insert(arr, pi);
    root->right = Insert(arr, pi);
    return root;
}

void InOrder(BTNode* root)
{
    if(root == NULL) return;
    InOrder(root->left);
    printf("%c ", root->data);
    InOrder(root->right);
}

int main() 
{
    char arr[100];
    scanf("%s", arr);

    int i = 0;
    BTNode* root = Insert(arr, &i);

    InOrder(root);

    return 0;
}

4.3 判断是否是完全二叉树

1. 完全二叉树每一层都是连续的

2. 利用层序遍历的思想，将二叉树节点作为数据插入队列，遇到数据为空就结束遍历。

3. 判断队列剩下的数据有无非空，全都是空证明是连续的，有非空证明不连续。

bool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);

	if(root != NULL) QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front == NULL) break;

		QueuePush(&q, front->left);
		QueuePush(&q, front->right);
	}

	while (!QueueEmpty(&q))
	{ 
		if (QueueFront(&q) != NULL)
		{
			QueueDestroy(&q);
			return false;
		}
		QueuePop(&q);
	}

	QueueDestroy(&q);
	return true;
}

5. 编程题

5.1 相同的树

链接：. - 力扣（LeetCode）

思路：分治子问题。

1. 根节点值相等就比较他们的左子树和右子树。

2. 根节点值不相等直接返回false。

3. 接下来比结构，同时走到空意味着前面的结构和值是相等的，一个为空一个不为空证明结构不相等。 

bool isSameTree(struct TreeNode* p, struct TreeNode* q) 
{
    if(p == NULL && q == NULL) return true;
    if(p == NULL || q == NULL) return false;
    if(p->val != q->val) return false;
    
    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

5.2 单值二叉树

链接：. - 力扣（LeetCode） 

思路：

1. 将根节点和自己的左右孩子比较，注意左右孩子可能为空。

2. 相等则往下交给自己的左右子树。

bool isUnivalTree(struct TreeNode* root) 
{
    if(root == NULL) return true;
    if(root->left != NULL && root->val != root->left->val) return false;
    if(root->right != NULL && root->val != root->right->val) return false;

    return isUnivalTree(root->left) && isUnivalTree(root->right);
}

5.3 对称二叉树

链接： . - 力扣（LeetCode）

思路：

1. 根节点的左右子树要形成镜像对称。

2. 需要写一个子函数去比较左右子树是否对称。

3. 左子树的左边和右子树的右边对应，左子树的右边和右子树的左边对应。

bool isSameTree(struct TreeNode* p, struct TreeNode* q) 
{
    if(p == NULL && q == NULL) return true;
    if(p == NULL || q == NULL) return false;
    if(p->val != q->val) return false;
    
    return isSameTree(p->left, q->right) && isSameTree(p->right, q->left);
}

bool isSymmetric(struct TreeNode* root) 
{
    return isSameTree(root->left, root->right);    
}

5.4 二叉树的前序遍历

链接： . - 力扣（LeetCode）

思路：

1. 题目给个returnSize代表节点的个数。需要自己求。

2. 利用求的节点个数开空间。

3. 再写一个子函数进行前序遍历，将根值放入数组中，下标要传址。

void _preorderTraversal(struct TreeNode* root, int* ret, int* i)
{
    if(root == NULL) return;

    ret[(*i)++] = root->val;
    _preorderTraversal(root->left, ret, i);
    _preorderTraversal(root->right, ret, i);
}

int Size(struct TreeNode* root)
{
    if(root == NULL) return 0;
    else return 1 + Size(root->left) + Size(root->right);
}

int* preorderTraversal(struct TreeNode* root, int* returnSize) 
{
    *returnSize = Size(root);
    int* tmp = (int*)malloc(sizeof(int)*(*returnSize));
     
    int i = 0; 
    _preorderTraversal(root, tmp, &i);
    
    return tmp;
}

5.5 另一棵树的子树

链接： . - 力扣（LeetCode）

思路：

1. 遍历root，将root每个节点和subroot比较。

2. 注意，遍历到空意味着前面的比较都不相等。subroot也不可能为空。

bool isSameTree(struct TreeNode* p, struct TreeNode* q) 
{
    if(p == NULL && q == NULL) return true;
    if(p == NULL || q == NULL) return false;
    if(p->val != q->val) return false;
    
    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot)
{
    if(root == NULL) return false;
    
    if(isSameTree(root, subRoot) == true) return true;

    return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot); 
}

6. 选择题

1.某完全二叉树按层次输出(同一层从左到右)的序列为 ABCDEFGH 。则该完全二叉树的前序序列为()

A. ABDHECFG

B. ABCDEFGH

C. HDBEAFCG

D. HDEBFGCA

答：A

2.二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK; 中序遍历：HFIEJKG.则二叉树根结点为()

A. E

B. F

C. G

D. H

答：A

3.设一课二叉树的中序遍历序列：badce，后序遍历序列：bdeca，则二叉树前序遍历序列为____。

A. adbce

B. decab

C. debac

D. abcde

答：D

4.某二叉树的后序遍历序列与中序遍历序列相同，均为 ABCDEF ，则按层次输出(同一层从左到右)的序列为

A. FEDCBA

B. CBAFED

C. DEFCBA

D. ABCDEF 

答：A