初阶数据结构二叉树的链式结构
【初阶数据结构】二叉树的链式结构
前言
上一节我们介绍了树以及二叉树的相关概念，性质以及结构，这节就来具体介绍二叉树的链式结构。
根据二叉树的概念可知， 对于一棵非空二叉树，它的左子树和右子树又分别是不同的二叉树 ，这就可以看出来了，二叉树最大的特征就是 递归 ，在下面对二叉树的各种操作都是由递归实现。
数据结构专题学习：
C++专题学习：
二叉树的创建
二叉树的创建并不是我们学习的重点，为了后续的学习，我们可以直接简简单单手搓一棵树：
BTNode* BuyNode(int val)
{
BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
if (newnode == NULL)
{
perror("malloc fail");
return;
}
newnode->left = NULL;
newnode->right = NULL;
newnode->val = val;
return newnode;
}
BTNode* CreatBinaryTree()
{
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 node1; //根节点
}二叉树的遍历
对于二叉树这种结构，最简单的操作就是遍历，
所谓二叉树的遍历就是按照某种特定的规则，依次访问二叉树中的结点
。只有学会了遍历操作，才能对其它的操作更快的学会。而二叉树的遍历总共有四种，分别是：
前序遍历，中序遍历，后序遍历以及层序遍历
，最重要的就是前面三个。最基本的要求是对于一棵二叉树，要把这四种情况都能写出来。
由于被访问的结点是某子树的根，所以N(Node)、L(Left subtree)、R(Right subtree)又可以解释为根、根的左子树和根的右子树。所以NLR、LNR、LRN分别又称为先根遍历，中根遍历和后根遍历。
前序遍历
前序遍历，也称先根遍历（NLR）
，即访问根节点的操作发生在其遍历左右子树之前，即
遍历顺序为：根、左子树、右子树。
因为二叉树是递归式的，所以遍历也用递归实现即可，代码如下：
void PreOrder(BTNode* root)
{
if(root == NULL)
{
printf("空树");
return ;
}
printf("%d ",root->val); //访问根节点；
PreOrder(root->left); //递归遍历左子树
PreOrder(root->right); //递归遍历右子树
}
想要准确的了解一个递归过程，就应该画出图来才能更好的理解，前序遍历的递归展开图如下，在图中也标注的部分顺序，大家可以试着自己画出来：
中序遍历
中序遍历，也称中根遍历（LNR）
，即访问根节点的操作发生在其遍历左右子树的中间，即
遍历顺序为：左子树、根、右子树。
与前序遍历类似，也是递归遍历，具体代码如下：
void InOrder(BTNode* root)//中序遍历
{
if (root == NULL)
{
printf("空树");
return;
}
InOrder(root->left); //递归遍历左子树
printf("%d ", root->val); //访问根节点；
InOrder(root->right); //递归遍历右子树
}
后序遍历
后序遍历，也称后根遍历（LRN）
，即访问根节点的操作发生在其遍历左右子树之后，即
遍历顺序为：左子树、右子树、根
。与前序遍历和中序遍历类似，同样是递归遍历，具体代码如下：
void PostOrder(BTNode* root)//后序遍历
{
if (root == NULL)
{
printf("空树");
return;
}
PostOrder(root->left); //递归遍历左子树
PostOrder(root->right); //递归遍历右子树
printf("%d ", root->val); //访问根节点；
}层序遍历
层序遍历与先，中，后序遍历有所不同。所谓层序遍历就是从二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第二层上的节点，接着是第三层的节点，以此类推，
自上而下，从左至右逐层访问树的节点的过程就是层序遍历。
过程如下图所示：
对于层序遍历，就需要借助一个队列。层序遍历的思想如下：
- 首先将根节点入队。
若队列非空，则队头节点出队，并访问该节点。若它有左孩子或者右孩子，则将它的孩子依次入队。- 重复步骤2，直至队列为空。
具体代码如下：
void LevelOrder(BTNode* root)//层序遍历
{
Queue q;
QueueInit(&q);//初始化一个队列
if (root)//如果根节点不为空，则将根节点放入队列中
{
QueuePush(&q, root);
}
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q); //取出队头元素
printf("%d ", front->val);
QueuePop(&q); //队头节点出队列
if (front->left)
QueuePush(&q, front->left); //左孩子不为空，则左孩子入队
if(front->right)
QueuePush(&q, front->right); //右孩子不为空，则右孩子入队
}
printf("\n");
QueueDestroy(&q);
}注：队列相关代码问题请参考： 。
二叉树的结点数相关问题
不仅是二叉树的遍历操作要用到递归，关于二叉树节点数相关问题也用的递归，如下面几个操作。
二叉树的结点个数
由前面我们知道，一棵二叉树可以分为根，左子树和右子树三个部分，那么想要求二叉树的节点个数时，只要知道左子树节点个数和右子树节点个数，再加上根结点就是整棵二叉树的节点个数。
即
二叉树的节点个数=左子树节点个数+右子树节点个数+1。
代码如下：
int TreeSize(BTNode* root)
{
return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}具体可以自己递归画图实现一下。
二叉树的叶子结点个数
所谓叶子节点，就是没有左右孩子，当叶子节点作为根节点时，就是左右子树都为空，按照这个性质，我们就可以求出叶子节点个数。也就是：
- 当该节点没有左右孩子时，是叶子节点，则加一。
- 当该节点有孩子时，将该节点作为根节点加上它下面的孩子为一棵树，也就是求左子树的叶子节点个数+右子树的叶子节点个数。
代码如下：
int TreeLeafSize(BTNode* root)
{
if (root == NULL)
return 0;
if (root->left == NULL && root->right == NULL)
return 1;
return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}二叉树第k层结点个数
和上面一样的方式，当我想求第k层的节点个数时，只要知道
左子树的第k-1层节点数+右子树的k-1层节点数即可。
直到递推到
k==1时，若还有节点则返回1，没有节点则返回0。
如对于我想求第3层的节点个数，就等于左子树第2层的节点数+右子树第2层的节点数，直到左右子树的第k=1层结束。
代码如下：
int TreeKLever(BTNode* root, int k)
{
assert(k > 0);
if (root == NULL)
return 0;
if (k == 1)
return 1;
return TreeKLever(root->left, k - 1) + TreeKLever(root->right, k - 1);
}二叉树查找值为x的结点
想要查找值为x的节点，其实也就是要遍历各个节点，找到相同的节点。我们可以直接将前序遍历的代码进行改造，
先遍历根结点，看是否为x若不是，则去左子树找，左子树找完去右子树找。
递归结束的两个条件：一个是如果访问的节点为空时，就返回空，另一个是如果节点与x对应，则直接返回该节点。
代码如下：
BTNode* TreeFind(BTNode* root, int x)
{
if (root == NULL)
return NULL;
if (root->val == x)
return root;
BTNode* ret1 = TreeFind(root->left, x);
if (ret1)
return ret1;
BTNode* ret2 = TreeFind(root->right, x);
if (ret2)
return ret2;
return NULL;//最后找不到则返回NULL
}二叉树的高度
求二叉树高度也是一样的，我只要知道左子树高度和右树高度哪个更高，
用高的那棵树的高度加1就是树的高度。
代码如下：
int TreeHight(BTNode* root)
{
if (root == NULL)
return 0;
int left = TreeHight(root->left);
int right = TreeHight(root->right);
return left > right ? left + 1 : right + 1;
}感谢大家观看，如果大家喜欢，希望大家一键三连支持一下，如有表述不正确，也欢迎大家批评指正。
