【数据结构】链式二叉树

前言

在前面我们学习了一些二叉树的基本知识，了解了它的结构以及一些性质，我们还用数组来模拟二叉树建立了堆，并学习了堆排序，可是数组结构的二叉树有很大的局限性，平常我们用的最多树结构的还是链式二叉树，因此本章我们来学习一些链式二叉树的相关知识。

普通的链式二叉树作用不大，同时二叉树也不是经常用来存储数据，因为存储数据用顺序表或链表就已经够了，链式二叉树通常是为了后续更加高级的树结构做铺垫，就如同单链表一样。不过基础不牢，地动山摇，本章的学习还是很重要的。

关于本章的代码可以访问这里获取

---

一、创建一颗二叉树

在学习二叉树的基本操作前，需先要创建一棵二叉树，然后才能学习其相关的基本操作。由于现在各位对二叉树结构掌握还不够深入，为了降低大家学习成本，此处手动快速创建一棵简单的二叉树，快速进入二叉树操作学习，等二叉树结构了解的差不多时，我们反过头再来研究二叉树真正的创建方式。

我们来手动创建下面的二叉树：

首先这里的二叉树每个节点都有一个数据域，两个指针域，于是我们可以用结构体去构建它们。

1、节点的定义

typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType val;struct BinaryTreeNode* leftTree;struct BinaryTreeNode* rightTree;
}BTNode;

结构体有了，接下来我们就要去创建节点了，把一个个节点创建出来然后我们挨个手动链接就能完成我们想要的二叉树了！

2、节点的创建

//创建节点
BTNode* BuyNode(BTDataType val)
{BTNode* tmp = (BTNode*)malloc(sizeof(BTNode));if (NULL == tmp){perror("malloc fail:");return;}tmp->val = val;tmp->leftTree = tmp->rightTree = NULL;return tmp;
}

3、节点链接成树

int main()
{BTNode* n1 = BuyNode(1);BTNode* n2 = BuyNode(2);BTNode* n3 = BuyNode(3);BTNode* n4 = BuyNode(4);BTNode* n5 = BuyNode(5);BTNode* n6 = BuyNode(6);n1->leftTree = n2;n2->leftTree = n3;n1->rightTree = n4;n4->leftTree = n5;n4->rightTree = n6;}

这样上面的树我们就构建好了！
注意：上述代码并不是创建二叉树的方式，真正创建二叉树方式后序详解重点讲解。

二、二叉树的遍历

1、前序、中序以及后序遍历介绍

学习二叉树结构，最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。

按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历：

1. 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。
2. 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。
3. 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。

由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。

• 我们来看对于上面的树其前序遍历的顺序：

按照前序遍历的定义，我们应该先遍历根，再遍历左子树，再遍历右子树。

我们从根节点开始遍历，按照前序遍历的规则我们应该先访问根1，然后访问左子树，同时左子树2又是一个树按照前序遍历的规则我们应该先访问根节点，再访问左子树，于是我们要去访问3节点，3节点访问完毕后，我们又要去访问3节点的左子树，3节点的左子树是是空树于是返回，这时对于节点3这个树我们已经访问完了根节点与左子树了，接下来就要去访问3的右子树了，3节点的右子树是是空树于是返回。此时3节点已经访问完毕了。于是返回给2节点，此时2节点等到3节点返回后，2节点已经访问过了左子树，接下来就要去访问2的右子树了，2节点的右子树是是空树于是返回。

就这样层层递归，对于这颗树的前半部分遍历顺序就是：
1 2 3 NULL NULL NULL

对于右边的右子树，按照同样的规则先遍历根，再遍历左子树，再遍历右子树。

我们便可以得到这颗树的前序遍历顺序是：
1 2 3 NULL NULL NULL 4 5 NULL NULL 6 NULL NULL

• 我们来看对于上面的树其中序遍历的顺序：
  
  我们进入这颗树，看到了1，但是我们不能访问，我们应该先访问左子树2，进入这颗树，看到了2，但是我们不能访问，我们应该先访问左子树3，进入这颗树，看到了3，但是我们不能访问，我们应该先访问左子树NULL，左子树是NULL于是返回到3节点进行访问根，根访问完毕于是访问访问3的右子树，右子树是NULL于是返回到3节点，3节点中序遍历完毕返回给2节点…

就这样层层递归,我们便可以得到这颗树的中序序遍历顺序是：

NULL 3 NULL 2 NULL 1 NULL 5 NULL 4 NULL 6 NULL

• 我们来看对于上面的树其后序遍历的顺序：
  

同理层层递归,我们便可以得到这颗树的后序序遍历顺序是：
NULL NULL 3 NULL 2 NULL NULL 5 NULL NULL 6 4 1

2、前序、中序以及后序遍历的代码实现

//二叉树的前序遍历
void PrevOrder(BTNode* root)
{//判断是否为空，空直接返回if (NULL == root){return;}//前序遍历，先遍历根printf("%d ", root->val);//遍历完根再遍历左子树PrevOrder(root->leftTree);//遍历完左子树再遍历右子树PrevOrder(root->rightTree);
}

对于上面的树遍历结果为：

可以画出递归图帮助理解

中序遍历与前序遍历一样，只不过打印的位置发生了变化。

//二叉树的中序遍历
void InOrder(BTNode* root)
{if (NULL == root){return;}InOrder(root->leftTree);printf("%d ", root->val);InOrder(root->rightTree);
}

同理，后续遍历只不过打印的位置发生了变化。

//二叉树的后续遍历
void PostOrder(BTNode* root)
{if (NULL == root){return;}PostOrder(root->leftTree);PostOrder(root->rightTree);printf("%d ", root->val);
}

三、二叉树的层序遍历

二叉树的遍历方式有很多种，除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。

设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。

其流程图如下：

对于二叉树的前序遍历，中序遍历以及后续遍历，我们都采用了递归的方式，那是因为它们的遍历都可以将大问题分为小问题，进而递归解决，可是显然二叉树的层序遍历并不能用递归解决，因为同一层内的节点都没有办法直接访问到彼此，但是我们可以借助队列的特性来帮我们进行解决这个问题。

层序遍历的算法：
首先我们可以先判断根节点是否为NULL，如果为NULL，就结束程序，不为空先创建一个队列，将根节点的地址存入队列里面，然后获取队列里面的第一个元素，利用这个元素将此元素的左右孩子节点也带入队列里面，如果为空就不带入队列，然后删除队头元素，让队列里面的元素一个一个输出就行了。

//二叉树的层序遍历
void LevelOrder(BTNode* root)
{if (root == NULL){return;}Queue q;QueueInit(&q);QueuePush(&q, root);int KLevel = 1;while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);printf("%d ", front->val);QueuePop(&q);if (front->leftTree != NULL){QueuePush(&q, front->leftTree);}if (front->rightTree != NULL){QueuePush(&q, front->rightTree);}}printf("\n");QueueDestroy(&q);
}

还有的二叉树层序遍历，要求层序打印，也不难办，多加一个变量控制每一层的层数就行了。

//二叉树的层序遍历及层序打印
void LevelOrder2(BTNode* root)
{if (root == NULL){return;}Queue q;QueueInit(&q);QueuePush(&q, root);int KLevel = 1; //每一层的个数while (!QueueEmpty(&q)){while (KLevel--){BTNode* front = QueueFront(&q);printf("%d ", front->val);QueuePop(&q);if (front->leftTree != NULL){QueuePush(&q, front->leftTree);}if (front->rightTree != NULL){QueuePush(&q, front->rightTree);}}//运行到这里，说明上一层以经打印完了，队列中的数据就是下一层要打印的个数。printf("\n");KLevel = QueueSize(&q);}QueueDestroy(&q);
}

四、二叉树的节点个数以及高度

1、二叉树的节点个数

利用递归思想：二叉树的节点个数 = 根 + 左子树的节点个数 + 右节点的节点个数

// 二叉树节点个数
int TreeNodeSide(BTNode*root)
{if (NULL == root){return 0;}return TreeNodeSide(root->leftTree) + TreeNodeSide(root->rightTree) + 1;
}

2、二叉树叶子节点的个数

利用递归思想：二叉树叶子节点的个数 = 左子树叶子节点的个数 + 右子树叶子节点的个数

判断是否是叶子节点的条件是：左孩子 == 右孩子 == NULL

//求叶子节点
int TreeLeftSize(BTNode*root)
{if (root == NULL){return 0;}if (root->leftTree == NULL && root->rightTree == NULL){return 1;}return TreeLeftSize(root->leftTree) + TreeLeftSize(root->rightTree);
}

3、二叉树第k层节点个数

利用递归思想：
二叉树第k层节点个数 = 左子树第k-1层个数＋右子树的第k-1层个数
①k >1   根的第k层==左子树第k-1层个数＋右子树的第k-1层个数

②k == 1  不为NULL，就返回1；为NULL就返回0。

//求第K层节点的个数
int TreeKLevelSize(BTNode* root, int k)
{if (NULL == root){return 0;}if (k == 1){return 1;}return TreeKLevelSize(root->leftTree, k-1) + TreeKLevelSize(root->rightTree, k-1);
}

4、树的高度

利用递归思想：
树的高度 = 左子树的高度 与 右子树的高度 的较大者 + 1

//求树的高度
int TreeHeight(BTNode* root)
{if (NULL == root){return 0;}int left_height = TreeHeight(root->leftTree);int right_heignt=TreeHeight(root->rightTree);return left_height >= right_heignt ?left_height + 1 : right_heignt + 1;
}

5、二叉树查找值为x的节点

利用递归思想：
二叉树查找值为x的节点 = 判断根节点是否是值为x的节点，不是就去左子树去找，再找不到就去右子树去找，直到找不到。

// 二叉树查找值为x的节点
BTNode* TreeFind(BTNode* root, int x)
{if (NULL == root){return NULL;}if (root->val == x){return root;}BTNode* ret1 = TreeFind(root->leftTree, x);if (ret1 != NULL){return ret1;}BTNode* ret2 = TreeFind(root->rightTree, x);if (ret2 != NULL){return ret2;}return NULL;}

五、二叉树的创建和销毁

通过前面的学习相信你对与递归解决二叉树的相关问题已经有了一定的理解，二叉树本身就是递归定义的，所以对于二叉树创建与销毁也应该是递归的。

1、二叉树的创建

给我们一个序列，通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树， 其中“#”表示的是空格，空格字符代表空树。

算法：我们可以判断二叉树的值是否应该为空，来判断要不要创建一个节点来存储相应的值，如果创建完节点，我们可以递归创建根的左子树，左子树创建完毕我们可以递归的去创建右子树，左右子树都创建完毕了，我们的树也就创建完毕了，然后我们返回根节点的地址就行了。

//这里的pi是外面的int i=0;的地址，这里必须用&，为了让每一层递归中的i不一样
BTNode* TreeCreat(char* str, int* pi)
{if(str[(*pi)] == '#'){(*pi)++;return NULL;}BTNode* root = (BTNode*)malloc(sizeof(BTNode));root->ch = str[(*pi)];(*pi)++;root->left = TreeCreat(str, pi) ;root->right = TreeCreat(str, pi);return root; 
}

2、二叉树的销毁

二叉树的销毁我们最好采用后序遍历的方式，因为采用前序遍历我们会先销毁根节点，根节点被销毁了我们就很难找到左右节点了，这样就会导致内存泄漏，同理如果采用中序遍历中间销毁根就会很难找到右节点了。

算法：采用递归，要销毁一个树就先销毁这棵树的左子树，再销毁右子树，最后再销毁根。

//二叉树的销毁
void TreeDestory(BTNode* root)
{if (root == NULL){return;}TreeDestory(root->leftTree);TreeDestory(root->rightTree);free(root);//root == NULL; 可以不写，这里root只是形参,改变root不会影响外面原本的指针
}

这里的是BTNode* root，销毁完了还要在外面手动将root置空。如果我们传递BTNode** root就可以解决这个问题，你可以实现一下。

3、判断一棵树是不是完全二叉树

判断一棵树是不是完全二叉树利用递归好像并不能解决问题，但是我们遍历一棵树的方式并不是只有递归的前中后序，我们可以利用层序遍历的方式来判断一棵树是不是完全二叉树。

算法：我们可以层序遍历整个树，并将所有节点的地址都存放到队列里面（NULL也放），然后从队列里面取数据，拿到第一个NULL后判断，后面的节点是不是都是NULL,如果都是NULL说明是完全二叉树。

//判断一棵树是不是完全二叉树
bool TreeComplete(BTNode* root)
{Queue q;QueueInit(&q);if (root){QueuePush(&q, root);}while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);//遇到NULL,跳出去进行进一步判断。if (front == NULL){break;}else{QueuePush(&q, front->leftTree);QueuePush(&q, front->rightTree);}}//判断while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);//如果队列里面还有非NULL元素，说明非完全二叉树if (front != NULL){QueueDestory(&q);return false;}}QueueDestory(&q);return true;
}