目录

• 一、介绍
• 二、遍历二叉树
• • 1. ⭐前序遍历
  • 2. 中序遍历
  • 3. 后续遍历
  • 4. ⭐层序遍历
• 三、⭐二叉树其他问题求解
• • 1. 求节点个数
  • 2. 求叶子节点个数
  • 3. 求第kkk层节点个数
  • 4. 是否为完全二叉树
• 四、🌟创建链式结构的二叉树

一、介绍

对于一些非满二叉树的情况，使用顺序存储会造成一定的空间浪费，因此可以使用双向链表的形式来表示二叉树。

因为二叉树最多会有两个子树，所以对每个节点定义为含两个指针结构体。

每个节点的左指针指向该节点的左子树，右节点指向右子树。

二、遍历二叉树

对于链式存储实现的二叉树，其不像顺序存储那样可以通过下标访问，直接将整个树遍历完。

并且链表都是通过指针来访问下一节点的，再结合二叉树的特点，遍历整个二叉树，有以下方法：

1. ⭐前序遍历

采用递归的思想，我们知道根节点，就知道它的指向左右子树的指针，因此再调用该函数传递它的子树，直到子树为空。

其中前序遍历是指：访问根节点的操作发生在遍历其左右子树之前。

代码：

// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root)
{if (root == NULL)return NULL;printf("%d ", root->data);BinaryTreePrevOrder(root->left);//对左子树遍历BinaryTreePrevOrder(root->right);//对右子树遍历}

图示：

对图中的二叉树进行前序遍历输出的结果是A B D E H C F G

对于前序遍历的结果是比较好理解的，当遍历到一个节点时先输出它的数据，然后对它的左子树进行遍历，只有当遍历到空时，递归的函数才开始返回，然后执行调用该递归函数的下一条语句，即开始遍历右子树。

2. 中序遍历

中序遍历是指：访问根结点的操作发生在遍历其左子树之后，右子树之前；

代码：

// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{if (root == NULL)return NULL;BinaryTreePrevOrder(root->left);//对左子树遍历printf("%d ", root->data);BinaryTreePrevOrder(root->right);//对右子树遍历
}

图示：

对图中的二叉树进行中序遍历输出的结果是D B E H A F C G

对于中序遍历的理解：先对左子树进行遍历，直到空指针然后返回到调用该递归函数的地方，执行下一条语句，输出D，然后遍历该节点的右子树。只有遇到空或者节点的左右子树都遍历结束（函数语句都执行完）才会返回到调用该函数的地方。

3. 后续遍历

后序遍历是指：访问根节点的操作发生在遍历其左右子树之后。

代码：

// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{if (root == NULL)return NULL;BinaryTreePrevOrder(root->left);//对左子树遍历BinaryTreePrevOrder(root->right);//对右子树遍历printf("%d ", root->data);}

图示：

对图中的二叉树进行中序遍历输出的结果是D H E B F G C A

对于后续遍历的理解：只有当左右子树都为空，或者都遍历结束后再输出该节点是数据。并且是先左后右。

4. ⭐层序遍历

层序遍历就是将二叉树一层一层的遍历，此时递归的思想就不适合了，我们可以发现如果按层序的顺序，其实也是按根节点->左子树->右子树，并且都是以顺序排序。因此可以开辟数组，依次记录下当前节点的两个指针，以先存的先出的顺序（队列的特点），可以循环的变量整个二叉树。

图示：

代码：

// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{assert(root);//创建队列Queue* myQ = (Queue*)malloc(sizeof(Queue));QueueInit(myQ);//记录根节点指针QueuePush(myQ, root);while (!QueueEmpty(myQ))//当队列不为空{//取出队列第一个指针BTNode* temp = QueueFront(myQ);QueuePop(myQ);//并且去除该指针//输出数据printf("%c ", temp->data);//记录该节点的左右指针if(temp->left != NULL)QueuePush(myQ, temp->left);if(temp->right != NULL)QueuePush(myQ, temp->right);}printf("\n");QueueDestroy(myQ);//释放队列
}

输出的结果：A B C D E F G H

三、⭐二叉树其他问题求解

1. 求节点个数

简单点，可以通过递归的思想遍历。二叉树的节点个数 = 根节点个数+左右子树节点个数

代码：

// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{if (root == NULL)return 0;//		左子树节点个数				+ 右子树节点个数  			+ 根节点的个数return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}

2. 求叶子节点个数

叶子节点：度为0（左右子树为空）的节点。

和问题1类似，只不过有一些判断条件，只有左右子树都为空的时候再计数。

代码：

// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{if (root == NULL){return 0;}if (root->left == NULL && root->right == NULL){return 1;}//		左子树叶节点个数				+ 右子树叶节点个数  			return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

3. 求第kkk层节点个数

默认的话，认为根节点为第1层。

那么根节点的左右子树，就是第222层，再向下层数继续+1+1+1，直到kkk层就可以开始计数。

类似问题2，加一些判断，思想在转换一些：将根节点认为是第kkk层，每向下一层就−1-1−1，一直到第111层再开始计数

代码：

// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{if (root == NULL){return 0;}if (k == 1){return 1;}return BinaryTreeLevelKSize(root->left,k-1) + BinaryTreeLevelKSize(root->right,k-1);
}

4. 是否为完全二叉树

完全二叉树是完全按顺序的特别的二叉树。

因为是按顺序的，其中只有层序遍历最符合要求。非完全二叉树的情况，即在某层中，前面有空指针，但是后面还有非空指针；而完全二叉树，则是开始有空指针，到结束都只有空指针。

代码：

// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root)
{assert(root);//创建队列Queue* myQ = (Queue*)malloc(sizeof(Queue));QueueInit(myQ);//记录根节点指针QueuePush(myQ, root);while (!QueueEmpty(myQ))//当队列不为空{//取出队列第一个指针BTNode* temp = QueueFront(myQ);QueuePop(myQ);//并且去除该指针//存入该结点左右指针if (temp != NULL){QueuePush(myQ, temp->left);QueuePush(myQ, temp->right);}else//遇到空指针结束遍历{break;}}//遍历整个队列的内容while (!QueueEmpty(myQ)){BTNode* temp = QueueFront(myQ);QueuePop(myQ);//遇到非空指针，则不是完全二叉树if (temp != NULL){QueueDestroy(myQ);return 0;}}QueueDestroy(myQ);//是完全二叉树return 1;
}

四、🌟创建链式结构的二叉树

二叉树的遍历

分析：该问题主要还是需要根据一个字符串数组，来构建链式二叉树。

解题：因为该字符串是该二叉树先序遍历的结果，因此我们就用先序遍历来创建

BTNode* BuyNode(char c)
{BTNode* newNode = (BTNode*)malloc(sizeof(BTNode));newNode->data = c;newNode->left = NULL;newNode->right = NULL;return newNode;
}
//通过修改数组的下标的指针pi，可以保证数组按顺序向后遍历（类似静态变量了）
BTNode* BinaryTreeCreate(char* a, int* i)
{if (a[(*i)++] == '#')return NULL;BTNode* newNode = BuyNode(a[(*i)++]);newNode->left = BinaryTreeCreate(a, i);newNode->right = BinaryTreeCreate(a, i);return newNode;
}
//剩余部分还请自己试试吧

🦀🦀观看~