数据结构——链式二叉树

目录

🍁一、二叉树的遍历

🌕（一）、前序遍历(Preorder Traversal 亦称先序遍历)

🌕（二）、中序遍历(Inorder Traversal)

🌕（三）、后序遍历(Postorder Traversal)

（四）、层序遍历

🍁二、学习链式二叉树的意义

🍁三、二叉树遍历的代码实现

🌕（一）、前序遍历的代码实现

🌕（二）、中序遍历的代码实现

🌕（三）、后序遍历的代码实现

🌕（四）、求节点个数

🌕（五）、求叶子节点的个数

🌕（六）、求第K层的节点个数

---

🍁一、二叉树的遍历

在此之前我们先了解一下二叉树的四种遍历方式。

二叉树遍历 (Traversal) 是按照某种特定的规则，依次对二叉 树中的节点进行相应的操作，并且每个节点只操作一次 。

🌕（一）、前序遍历(Preorder Traversal 亦称先序遍历)

即先访问根节点，再访问左子树，最后访问右子树，如下图：

🌕（二）、中序遍历(Inorder Traversal)

即先访问左子树，再访问根节点，最后访问右子树，如下图：

🌕（三）、后序遍历(Postorder Traversal)

即先访问左子树，再访问右子树，最后访问根节点，如下图：

（四）、层序遍历

即一层一层的访问完毕，如下图：

🍁二、学习链式二叉树的意义

（一）、首先我们学习这部分知识要知道的是：普通的二叉树是没有意义的，你说用来存储数据，我直接用顺序表和链表等等不是更方便吗？

（二）、我们在这里学习链式二叉树有两个意义：

①：为后续学习更复杂的二叉树搜索树（如AVL、红黑树）打基础；

②：很多OJ题就喜欢考这一块；

（三）、在这里增删查改不是重点，我们重点学习二叉树的结构（递归结构）

🍁三、二叉树遍历的代码实现

在实现遍历算法之前，为我们首先得有一棵二叉树，因为我们只需要测试某一个功能，所以不需要完整的二叉树结构，这时我们就可以手动的快速建立一个二叉树，如下：

#include<stdio.h>
#include<stdlib.h>//二叉树结构体
typedef struct BinaryTreeNode
{struct BinaryTreeNode* right;struct BinaryTreeNode* left;int val;
}BTNode;//创建一个结点
BTNode* BuyNode(int x)
{BTNode* node = (BTNode*)malloc(sizeof(BTNode));if (node == NULL){printf("malloc fail");return;}node->val = x;node->right = NULL;node->left = NULL;return node;
}int main()
{//手动构建一颗二叉树//获得6个结点BTNode* node1 = BuyNode(1);BTNode* node2 = BuyNode(2);BTNode* node3 = BuyNode(3);BTNode* node4 = BuyNode(4);BTNode* node5 = BuyNode(5);BTNode* node6 = BuyNode(6);//手动连接一个二叉树node1->left = node2;node1->right = node4;node2->left = node3;node4->left = node5;node4->right = node6;return 0;
}

如上就是该二叉树的代码结构：

🌕（一）、前序遍历的代码实现

//前序遍历
void PrevOrder(BTNode* node1)
{if (node1 == NULL)return;printf("%d ", node1->val);PrevOrder(node1->left);PrevOrder(node1->right);
}

上面就是前序遍历的代码部分，根据规则先访问根节点（即打印），再访问左子树，最后访问右子树（递归），代码部分很简洁，但最重要的是要理解其递归栈帧展开结构：

、

蓝色字体是该位置表示的结点；

红色箭头是代码走向；

红色带圈数字是代码执行顺序；

🌕（二）、中序遍历的代码实现

这三种遍历方法无非就是访问顺序不一样，所以只需要改变相应顺序即可：

//中序遍历
void InOrder(BTNode* node1)
{if (node1 == NULL)return;PrevOrder(node1->left);printf("%d ", node1->val);PrevOrder(node1->right);
}

先访问左子树，再访问根节点（打印），最后访问右子树；

递归栈帧开辟与前序类似，可参考前序遍历自行思考；

🌕（三）、后序遍历的代码实现

//后序遍历
void EndOrder(BTNode* node1)
{if (node1 == NULL)return;PrevOrder(node1->left);PrevOrder(node1->right);printf("%d ", node1->val);
}

🌕（四）、求节点个数

//求结点个数
int TreeSixe(BTNode* root)
{return (root == NULL) ? 0 : (TreeSixe(root->left) + TreeSixe(root->right)+1);
}

求一颗二叉树有多少个节点，我们很容易想到和遍历的思路有关，这样我们就可以写出上述代码：

具体我们可以结合递归栈帧展开图来读代码，由上述所示，我们先计算的是左子树的节点个数，再计算右子树的节点个数，最后再加上当前根节点数，然后返回值，所以这类似于一种后序遍历。

🌕（五）、求叶子节点的个数

//求叶子结点个数
int TreeLeafSize(BTNode* root)
{//度为1的节点就可能访问到NULL，所以需要此判断if (root == NULL)return 0;if (root->left == NULL && root->right == NULL)return 1;return TreeLeafSize(root->left) + TreeLeafSize(root->right);}

三种情况：

①：该节点为空，返回0；

②：该节点的左孩子和右孩子都为NULL，即该节点为叶子节点，此时返回1；

③：该节点即不为NULL，也不为叶子节点，即该节点为非叶子节点，此时将任务抛给它的左右子树（左右孩子），所以返回递归和。

注意：

这里有一点容易混淆，就是很多人觉得最多就到叶子节点，不会到空节点，所以第一个if是不是可以不要？答案肯定是要的，因为这种想法是忽略了度为1的非叶子节点的情况，这种节点只有一个孩子，所以当该孩子访问完后就会访问另一个孩子，即访问到NULL；

🌕（六）、求第K层的节点个数

//求第k层的结点数
int TreeKLevel(BTNode* root,int k)
{if (root == NULL){return 0;}if (k == 1)return 1;return TreeKLevel(root->left, k - 1) + TreeKLevel(root->right, k - 1);
}

如求第三层，即为求第一层的第三层==求第二层的第二层==求第一层的第一层，利用k--1，每递归依次，就进行一次k-1表示到达下一层，当k==1时，即当前层数为要求节点数的层数，若root为NULL，即没有该节点，返回0；若k!=1,root不等于NULL，即还没有到达要求层数，则继续向下层递归。

本次知识到此结束，希望对你有所帮助！