【C】初阶数据结构8--链式二叉树

  前两篇文章我们讲解了顺序结构的二叉树 -- 堆以及堆的应用堆排序，所以这篇文章我们来讲解一下二叉树的链式结构 -- 链式二叉树。

---

目录

1  链式二叉树的结构

2  二叉树的遍历

1） 前序遍历

（1） 遍历规则

（2） 代码实现

2） 中序遍历

（1） 遍历规则

（2） 代码实现

3） 后序遍历

（1） 遍历规则

（2） 代码实现

4） 层序遍历

（1） 遍历规则

（2） 代码实现

3  链式二叉树的实现 

1） 求二叉树节点的个数

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

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

4） 二叉树的高度/深度

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

6） 二叉树的销毁

7） 判断一棵树是否是完全二叉树

8） 代码

---

重点一 链式二叉树的结构 1  链式二叉树的结构

  链式二叉树是用链式结构实现的二叉树，所以二叉树是由一个一个节点组成的，节点与节点之间用指针连接起来就形成了一棵二叉树。所以要定义链式二叉树的结构，主要就是要定义节点的结构，由于每个节点有左孩子也有右孩子，所以节点结构里面肯定要有两个指向左孩子和右孩子的指针域，另外，由于每个节点里面又有数据，所以节点结构里面还需要有一个存储数据的数据域：

typedef int BTDataType; //链式树的结构 typedef struct BinTreeNode { BTDataType data;//二叉树结点里面的数据 struct BinTreeNode* left;//左孩子指针 struct BinTreeNode* right;//右孩子指针 }BTNode;

---

2  二叉树的遍历

  所谓遍历，就是将二叉树中所有节点的值都访问一遍，然后将访问的值按照一定序列输出出来。对于二叉树的遍历总共有四种方式：前序遍历，中序遍历，后序遍历以及层序遍历，其中前序遍历，中序遍历和后序遍历就是深度优先遍历，层序遍历就是广度有限遍历。

1） 前序遍历 （1） 遍历规则

  前序遍历就是先访问一棵子树的根，然后再访问该节点的左子树，在其左子树里，再先访问根节点，然后访问左子树，依次类推，直到访问到空，然后回溯到最近的根节点，再访问其右子树，在其右子树里再按根左右的方式遍历整棵数，依次类推，如下面这棵二叉树：

其走前序遍历的过程为：首先从根节点出发，先访问根节点10，之后去访问其左子树，在左子树里又先访问根节点14，然后再去14的左子树里访问29根节点，之后再去29的左子树里访问22根节点，然后22去访问其左子树的根节点，由于是空，所以直接返回到22这个根节点，之后再去22根节点的右子树去访问根节点，由于是空，所以返回到22根节点，之后以22左为根节点的整棵子树全都访问结束，再向上回溯到 29 根节点，去访问29的右子树，之后的过程依次类推，所以这棵树先序遍历的过程为：

蓝色的为先后访问的序号，所以这棵树先序遍历的序列为：10， 14， 29， 22， 11， 15， 28， 9， 12， 9， 11。

（2） 代码实现

  由于整棵二叉树是递归定义的，所以我们也采取递归的算法来实现二叉树的前序遍历。这里给前序遍历的函数取名为 PreOrder，参数仅有一个就是二叉树节点的指针 root 表示一棵二叉树的根节点。递归算法最重要的就是实现定义边界条件。这里的边界条件就是当二叉树遍历到 NULL 的时候，我们就应该退出递归了，NULL 节点代表里面没有实际值，所以也就不需要遍历该节点，然后按照前序遍历 根左右 的过程写出代码即可：

//BTNode为链式二叉树的节点 void PreOrder(BTNode* root) { if (root == NULL) { return; } printf("%d ", root->data);//先输出根节点信息 PreOrder(root->left);//再遍历根节点的左子树 PreOrder(root->right);//再遍历根节点的右子树 }

我们来看一下其递归的过程：  

2） 中序遍历 （1） 遍历规则

  中序遍历就是先访问一棵树的左子树，然后访问根，再访问另一棵树的右子树，按照左根右的方式去遍历一整棵树，如下面这棵树：

其走中序遍历的过程为：先访问 21 根节点的左子树，然后再去访问 11 根节点的左子树，再访问 19 根节点的左子树，之后访问完 5 之后，输出 5 ，然后回溯到 19 根节点，然后输出 19 ，再去访问 19 根节点的右子树，然后再回溯到根 19，以 19 作为根节点的整棵子树访问完成，之后回溯到 11 该根节点，输出 11，然后再去访问 11 根节点的右子树，依次类推。其边的遍历过程与前序遍历相同，但是输出序列不同，这棵树走中序遍历的序列为：5， 19， 39， 11， 30， 21， 50， 25， 1， 32， 29， 17（前序遍历为：21， 11， 19， 5， 39， 30， 32， 25， 50， 1， 29， 17）。

（2） 代码实现

  其实中序遍历的代码与前序遍历类似，只不过是访问根节点顺序变了：

//BTNode为链式二叉树的节点 void InOrder(BTNode* root) { if (root == NULL) { return; } PreOrder(root->left);//先遍历根节点的左子树 printf("%d ", root->data);//再输出根节点信息 PreOrder(root->right);//再遍历根节点的右子树 } 3） 后序遍历 （1） 遍历规则

  后序遍历就是先访问一棵树的左子树，然后访问其右子树，最后访问根，按照左右根的方式遍历整棵树，如下面这棵树：

其走后序遍历的过程为： 先去访问 21 根节点的左子树，之后再去访问 11 根节点的左子树，再去访问 19 根节点的左子树，由于左子树只有一个节点，所以会输出 5，之后访问 19 根节点的右子树，输出 39，回溯到 19 根节点，输出 19，之后回溯到 11 根节点，再去访问其右子树 30，输出30，然后回溯到 11 根节点，输出 11，依次类推。所以这棵二叉树走后序遍历的序列为：5， 39， 19， 30， 11， 50， 1， 25， 17， 29， 32， 21。

（2） 代码实现

  后序遍历也类似于前序遍历和中序遍历代码逻辑，只要把输出根节点信息的顺序改变一下就可以了：

//BTNode为链式二叉树的节点 void PostOrder(BTNode* root) { if (root == NULL) { return; } PreOrder(root->left);//先遍历根节点的左子树 PreOrder(root->right);//再遍历根节点的右子树 printf("%d ", root->data);//最后输出根节点信息 } 4） 层序遍历 （1） 遍历规则

  层序遍历，也是二叉树里的广度优先遍历，就是按照二叉树的层次由第一层到第 k 层的顺序依次遍历每个节点，在每层里又会按照从左至右的顺序依次遍历。如下面这棵树进行层次遍历的过程为：

先走第一层（也就是整棵二叉树的根节点一层）21，输出21，再从左至右遍历第二层，输出11,32，依次类推。所以，整棵二叉树进行层序遍历的序列为：21， 11， 32， 19， 30， 25， 29， 5， 39， 50， 1， 17。 

（2） 代码实现

  实现二叉树的层序遍历需要借助一个数据结构队列，队列的每个节点里面存储的不再是整型，而是链式二叉树的每个节点的指针。先让根节点入队，然后输出其节点里存储的数据，如果根节点左子树不为空，那就让其左孩子入队，如果右孩子不为空，再让右孩子入队，然后让根节点出队，依次类推，直到队列为空为止，实现过程如图：

代码：

//Queue里面应该是 typedef BTNode* QDataType; void LevelOrder(BTNode* root) { assert(root); //借助队列 Queue q; QueueInit(&q); //先让根节点入队 QueuePush(&q, root); //循环判断队列是否为空 while (!QueueEmpty(&q)) { BTNode* pop = QueueFront(&q); //输出队头元素 printf("%d ", pop->data); //队头元素出队 QueuePop(&q); //左孩子不为空，让左孩子入队 if (pop->left) { QueuePush(&q, pop->left); } if (pop->right) { QueuePush(&q, pop->right); } } //不要忘记销毁队列 QueueDestroy(&q); }

---

3  链式二叉树的实现 

  对于链式二叉树，除了以上的四种遍历，还有其他操作需要实现，分别包括求二叉树节点个数、二叉树叶子节点的个数、二叉树第k层节点个数、二叉树的深度/高度、二叉树查找值为 x 的节点、二叉树的销毁和判断一棵树是否是完全二叉树。

  可以看到在链式二叉树里面并没有二叉树的初始化与插入和删除节点，因为对于一棵普通二叉树来说，其插入节点的限制太少了，导致插入在哪个节点的左右孩子上都可以，所以这里并不涉及普通二叉树的插入和删除节点，以后在 AVL 树（二叉平衡树）以及红黑树里面会有相应的插入与删除节点的操作。

1） 求二叉树节点的个数

  求二叉树节点的个数可以采用递归算法来解决。我们可以这样想，对于一棵二叉树来说，其节点个数就等于根节点个数（也就是1个）加上左子树节点个数和右子树节点个数。那么边界条件就是当一个节点为NULL时，代表这个节点并不是一个有效节点，所以返回0就可以了。

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

  找叶子节点的个数同样可以采用递归算法来解决。整棵树的叶子节点的个数就等于根节点的左子树中叶子结点的个数 + 右子树中叶子节点的个数。这个操作的边界条件有两个，一个是如果节点为NULL，代表没有节点了，返回0；另一个是找到了一个叶子结点(root->left == NULL && root->right == NULL)，就返回1。

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

  该操作也可以通过递归算法来解决。求第 k 层节点个数可以拆解为求左子树第 k - 1层节点个数 + 右子树第 k - 1层节点个数。边界条件也有两个，一个是节点为NULL时，返回0；另一个是如果 k 变为了1， 那么就需要返回 1。

4） 二叉树的高度/深度

   同样的，该操作也是使用递归算法来解决。整棵二叉树的高度可以想成是根节点的高度（也就是1）加上左子树与右子树的高度的较大值。所以返回是是左子树与右子树高度中的较大者。边界条件就是当节点为 NULL 时，代表该节点并不是一个有效节点，所以返回 0 就可以了。

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

  类似于上面几个操作，该操作也是利用递归算法来解决问题。该问题可以变成先看根节点的值是否是 x ，如果不是那就去左子树里面查找值为 x 的节点，如果左子树也没有，那就去右子树查找值为 x 的节点。要注意的是，查找值为 x 的节点只需要返回一个节点就可以了，返回只要找到一个节点值为 x 就要结束递归，返回该节点了。边界条件共有3个，一个就是如果节点为 NULL 了，说明不是有效节点，就返回 NULL；还有一个就是如果根节点值为 x 了，就说明找到了一个值为 x 的节点了，直接返回根节点；第三个就是如果在根节点与左子树和右子树内都没有找到值为 x 的节点，也需要返回 NULL 。

6） 二叉树的销毁

  销毁呢，同样可以采用递归算法来解决。销毁整棵二叉树可以看作是先销毁左子树，再销毁右子树，最后销毁根节点。要注意的是必须先销毁根节点的左子树或者右子树，才能销毁根节点，因为先销毁根节点的话，那么其左右子树就找不到了，会造成内存泄露的。边界条件就是当节点为 NULL 时，该节点不需要销毁，直接返回就可以了。

7） 判断一棵树是否是完全二叉树

  要判断一棵树是否是完全二叉树，我们需要从完全二叉树的特点出发，下面是一棵完全二叉树：

我们可以看到完全二叉树的特点就是在一层里节点都是从左至右依次排列的，且除了最后一层，上面的每层节点都是满的。所以从这个特性出发，我们可以看到如果对一棵完全二叉树进行层序遍历，在出现NULL节点之后，后面的节点一定都是空节点，所以判断一棵二叉树是否是完全二叉树的算法就可以这样设计：   借助辅助数据结构队列，先对一棵树进行层序遍历，但注意的是，如果某个节点的孩子节点是空，也要让其入队，之后循环取对头元素，让其左右孩子入队，让队头元素出队，直到队列为空或者队头元素为NULL；之后再判断队列是否为空，再次取对头，判断队头元素是否有非空节点，如果有，那就不是一棵完全二叉树，如果没有，那就是一棵完全二叉树。该算法的执行过程如下：  

---

8） 代码

BinaryTree.h文件：

#include<stdio.h> #include<assert.h> #include<stdlib.h> #include<stdbool.h> typedef int BTDataType; typedef struct BinaryTreeNode { BTDataType data; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }BTNode; //前序遍历 void PreOrder(BTNode* root); //中序遍历 void InOrder(BTNode* root); //后序遍历 void PostOrder(BTNode* root); //层序遍历 void LevelOrder(BTNode* root); //二叉树结点个数 int BTSize(BTNode* root); //二叉树叶子结点个数 int BTLeafSize(BTNode* root); //二叉树第k层的结点个数 int BTLevelkSize(BTNode* root, int k); //二叉树的深度 int BTLevel(BTNode* root); //二叉树查找值为x的结点 BTNode* BTFind(BTNode* root, int x); //二叉树销毁 //这里要传二级指针，因为根节点也要销毁，销毁之后实参要置为NULL void BTDestroy(BTNode** root); //判断是否为完全二叉树 bool BTComplete(BTNode* root);

BinaryTree.c文件：

#include"BinaryTree.h" //前序遍历 void PreOrder(BTNode* root) { if (root == NULL) { return; } //根 -- 左 -- 右 printf("%d ", root->data); PreOrder(root->left); PreOrder(root->right); } //中序遍历 void InOrder(BTNode* root) { if (root == NULL) { return; } //左 -- 根 -- 右 InOrder(root->left); printf("%d ", root->data); InOrder(root->right); } //后序遍历 void PostOrder(BTNode* root) { if (root == NULL) { return; } //左 -- 右 -- 根 PostOrder(root->left); PostOrder(root->right); printf("%d ", root->data); } //二叉树结点个数 //根结点个数加上左子树结点个数加上右子树结点个数 int BTSize(BTNode* root) { if (root == NULL) { return 0; } return 1 + BTSize(root->left) + BTSize(root->right); } //二叉树叶子结点个数 //左子树的叶子结点个数加上右子树的结点个数 int BTLeafSize(BTNode* root) { if (root == NULL) { return 0; } if (root->left == NULL && root->right == NULL) { //找到了一个叶子结点 return 1; } //返回左右孩子叶子结点个数 return BTLeafSize(root->left) + BTLeafSize(root->right); } //二叉树第k层的结点个数 int BTLevelkSize(BTNode* root, int k) { if (root == NULL) { return 0; } //如果k为1，返回1 if (k == 1) { return 1; } //返回左子树第k层结点个数 + 右子树第k层结点个数 return BTLevelkSize(root->left, k-1) + BTLevelkSize(root->right, k-1); } //二叉树的深度 int BTLevel(BTNode* root) { if (root == NULL) { return 0; } //返回左子树与右子树深度最大的深度+根结点深度 int leftdep = BTLevel(root->left); int rightdep = BTLevel(root->right); return 1 + (leftdep > rightdep ? leftdep : rightdep); } //二叉树查找值为x的结点 BTNode* BTFind(BTNode* root, int x) { if (root == NULL) { return NULL; } if (root->data == x) { return root; } //如果查找的左孩子不为空，返回左孩子查找的结点 BTNode* leftfind = BTFind(root->left, x); if (leftfind) { return leftfind; } //如果查找的右孩子不为空，返回右孩子查找的结点 BTNode* rightfind = BTFind(root->right, x); if (rightfind) { return rightfind; } //如果查找不到，返回NULL return NULL; } //二叉树销毁 void BTDestroy(BTNode** root) { if (*root == NULL) { return; } BTDestroy(&(*root)->left); BTDestroy(&(*root)->right); free(*root); *root == NULL; } //判断是否为完全二叉树 //要借助辅助数据结构队列 bool BTComplete(BTNode* root) { Queue q; QueueInit(&q); //让根结点入队 QueuePush(&q, root); //如果队列不为空，或者遇到了NULL结点，那就结束循环 while (!QueueEmpty(&q)) { //取队头，出队头 BTNode* top = QueueFront(&q); QueuePop(&q); if (top == NULL) { break; } //让结点的左右孩子都入队，不管为不为NULL QueuePush(&q, top->left); QueuePush(&q, top->right); } //判断队列为不为空，如果里面节点有NULL，那就返回false while (!QueueEmpty(&q)) { BTNode* top = QueueFront(&q); if (top != NULL) { QueueDestroy(&q); return false; } QueuePop(&q); } //如果队列没有遇到NULL结点 QueueDestroy(&q); return true; } //层序遍历 //需要借助辅助数据结构队列 void LevelOrder(BTNode* root) { //队列不能为空 assert(root); //先初始化一个队列 Queue q; QueueInit(&q); //然后让根节点入队 QueuePush(&q, root); while (!QueueEmpty(&q)) { //取队头元素 BTNode* top = QueueFront(&q); //打印数据 printf("%d ", top->data); //让头节点出队 QueuePop(&q); //如果左孩子不为空，就让左孩子入队 if (top->left) { QueuePush(&q, top->left); } //如果右孩子不为空，就让右孩子入队 if (top->right) { QueuePush(&q, top->right); } } //销毁队列 QueueDestroy(&q); }

test.c文件：

我们选择手动创建这么一颗树：

test.c文件：  

#include"BinaryTree.h" BTNode* buyNode(BTDataType x) { BTNode* root = (BTNode*)malloc(sizeof(BTNode)); if (root == NULL) { perror("malloc fail！\n"); exit(1); } root->data = x; root->left = root->right = NULL; return root; } //创建一颗链式二叉树 BTNode* CreateTree() { BTNode* node1 = buyNode(1); BTNode* node2 = buyNode(2); BTNode* node3 = buyNode(3); BTNode* node4 = buyNode(4); BTNode* node5 = buyNode(5); BTNode* node6 = buyNode(6); BTNode* node7 = buyNode(7); //接下来改变左孩子指针与右孩子指针指向，使其成为一棵树 node1->left = node2; node1->right = node3; node2->left = node4; node3->left = node5; node4->right = node6; return node1; } void Test() { BTNode* root = CreateTree(); //测试前序遍历 //1 2 4 6 3 5 //PreOrder(root); //测试中序遍历 //4 6 2 1 5 3 //InOrder(root); //测试后序遍历 //6 4 2 5 3 1 //PostOrder(root); //测试层序遍历 //1 2 3 4 5 6 //LevelOrder(root); //测试结点个数 //6 /*int size = BTSize(root); printf("%d ", size);*/ //测试叶子结点个数 //2 //int size = BTLeafSize(root); //printf("%d ", size); //测试第k层结点个数 /*int size = BTLevelkSize(root, 4); printf("%d ", size);*/ //测试二叉树的深度 //int depth = BTLevel(root); //printf("%d ", depth); //测试查找 /*BTNode* ret = BTFind(root, 7); if (ret == NULL) { printf("找不到!\n"); } else printf("%d ", ret->data);*/ //测试是否是完全二叉树 bool ret = BTComplete(root); if (ret) { printf("是完全二叉树"); } else { printf("不是完全二叉树"); } } int main() { Test(); return 0; }

 大家可以测试一下，如果把CreateTree函数改为以下代码，看看是不是一棵完全二叉树：

BTNode* CreateTree() { BTNode* node1 = buyNode(1); BTNode* node2 = buyNode(2); BTNode* node3 = buyNode(3); BTNode* node4 = buyNode(4); BTNode* node5 = buyNode(5); BTNode* node6 = buyNode(6); BTNode* node7 = buyNode(7); //接下来改变左孩子指针与右孩子指针指向，使其成为一棵树 node1->left = node2; node1->right = node3; node2->left = node4; node3->left = node5; node2->right = node6; return node1; }