【数据结构】二叉树

本篇我们来说一下数据结构中的树。

1.树的概念及结构

1.1 概念

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

树可以拆成根和子树，子树又可以拆成根和子树...所以又说，树是递归定义的。

注意：树形结构中，子树之间不能有交集，否则就不是树形结构。如下。

1.2 结构

结点的度：一个结点含有的子树的个数称为该结点的度；如上图：A的为6
叶结点或终端结点：度为0的结点称为叶结点；如上图：B、C、H、I...等结点为叶结点
非终端结点或分支结点：度不为0的结点；如上图：D、E、F、G...等结点为分支结点
双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点；如上图：A是B的父结点
孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点；如上图：B是A的孩子结点
兄弟结点：具有相同父结点的结点互称为兄弟结点；如上图：B、C是兄弟结点
树的度：一棵树中，最大的结点的度称为树的度；如上图：树的度为6
结点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推；
树的高度或深度：树中结点的最大层次；如上图：树的高度为4
堂兄弟结点：双亲在同一层的结点互为堂兄弟；如上图：H、I互为兄弟结点
结点的祖先：从根到该结点所经分支上的所有结点；如上图：A是所有结点的祖先
子孙：以某结点为根的子树中任一结点都称为该结点的子孙。如上图：所有结点都是A的子孙
森林：由m（m>0）棵互不相交的树的集合称为森林；

1.3 树的表示（详解）

树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既然保存值域，也要保存结点和

结点之间的关系，实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及

孩子兄弟表示法等。我们这里就简单的了解其中最常用的 孩子兄弟表示法。

struct TreeNode
{int val;struct TreeNode* leftchild; //左孩子struct TreeNode* rightbrother; //右兄弟
};

左孩子的意思是，无论父节点有多少孩子，leftchild只指向父节点左边开始的第一个孩子。

右兄弟的意思是，挨着指向父节点右边的兄弟节点，没有兄弟节点指向空。具体分析如下。

A有两个孩子，A的child指向A左边的第一个孩子B，A没有兄弟节点，A的brother指向空。

B有三个孩子，B的child指向B左边的第一个孩子D，B有兄弟节点C，B的brother指向C。

D没有孩子，D的child指向空，D有兄弟，D的brother指向右边的兄弟E；C有一个孩子，C的child指向这个孩子G，C没有兄弟，C的brother指向空。

E有两个孩子，E的child指向E的左边第一个孩子H，E有兄弟，E的brother指向右边的兄弟F；G现在没有孩子也没有兄弟，都指向空。

H没有孩子，H的child指向空，H有兄弟，H的brother指向右边的兄弟I。F没有兄弟也没有孩子，都指向空。

I没有兄弟也没有孩子，I的child和brother都指向空。

此时整个树就连接完成了，这个设计非常巧妙。

2.二叉树

2.1 二叉树的概念

一棵二叉树是结点的一个有限集合，该集合 :

1. 或者为空

2. 由一个根结点加上两棵别称为左子树和右子树的二叉树组成

从上图可以看出：

1. 二叉树 不存在度大于2 的结点

2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

注意：对于任意的二叉树都是由以下几种情况复合而成的：

2.2 特殊二叉树

二叉树里有两个特殊的二叉树：满二叉树、完全二叉树。

满二叉树 ：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K ，且结点总数是2^k - 1，则它就是满二叉树。

完全二叉树 ：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为 K的，有n 个结点的二叉树，当且仅当其每一个结点都与深度为 K 的满二叉树中编号从 1 至n的结点一一对应时称之为完全二叉树。

要注意的是满二叉树是一种特殊的完全二叉树。

2.3 二叉树的存储结构

2.3.1 顺序存储

顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树、满二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储，堆后面才会说。

非完全二叉树会存在空间浪费的情况。

如果不空出来，下面的父子关系就直接混乱了。

2.3.2 父子关系

假设父节点在数组的下标为i：

左孩子在数组的下标：2*i + 1；右孩子在数组的下标：2*i + 2；

假设子节点在数组中的下标为j：

父节点在数组中的下标：(j - 1) / 2；

2.3.3 链表存储

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩和右孩子所在的链结点的存储地址。

typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{struct BinTreeNode* left; // 指向当前结点左孩子struct BinTreeNode* right; // 指向当前结点右孩子BTDataType data; // 当前结点值域
}

2.4 二叉树的性质

若规定根结点的层数为1，则一棵非空二叉树的第i层上最多有 $2^{^{i-1}}$ 个结点
若规定根结点的层数为1，则深度为h的二叉树的最大结点数是 $2^{^{h}}-1$
对任何一棵二叉树, 如果度为0其叶结点个数为 $n_{0}$ ，度为2的分支结点个数为 $n_{2}$ ，则有 $n_{0}=n_{2}+1$
若规定根结点的层数为1，具有n个结点的满二叉树的深度，h = $\log_{2}(n+1)$

2.5 相关练习

1. 某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（）

A 不存在这样的二叉树

B 200

C 198

D 199

答案：B

度为2的有199个，就是 $n_{2}=199$ ，因为 $n_{0}=n_{2}+1$ ，所以叶子节点有200个。

2. 在具有 2n 个结点的完全二叉树中，叶子结点个数为（）

A n

B n+1

C n-1

D n/2

答案：A

假设度为2的节点个数有 $n_{2}$ 个，度为1的有 $n_{1}$ 个，叶子节点有 $n_{0}$ 个，2n = $n_{2}$ + $n_{1}$ + $n_{0}$ ，而 $n_{0}=n_{2}+1$ ，所以2n = $n_{1}$ + 2 $n_{0}$ - 1；在完全二叉树中，度为1的 $n_{1}$ 的个数，要不就是1，要不就是0；由于2n一定是偶数，只有当 $n_{1}$ 为1时， $n_{1}$ + 2 $n_{0}$ - 1的结果才为偶数；所以这个式子最后化简为2n = 2 $n_{0}$ ， $n_{0}$ 就是叶子节点个数，为n。

3.一棵完全二叉树的结点数位为531个，那么这棵树的高度为（）

A 11

B 10

C 8

D 12

答案：B

完全二叉树的节点个数范围如下。

所以把选项往 $2^{^{h-1}}$ 和 $2^{h}-1$ 里带，发现h为10时，531在这个范围内。

3.堆

堆是一颗完全二叉树。

堆的详解在【数据结构】堆的概念、结构、模拟实现以及应用

4.二叉树的链式结构

4.1 二叉树的遍历

学习二叉树结构，最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的结点进行相应的操作，并且每个结点只操作一次。

4.1.1 前序、中序、后序遍历

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

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

可以发现，这三种遍历的特点其实是递归遍历。

4.1.2 层序遍历

层序遍历就是一层一层遍历访问。

4.2 二叉树的遍历的代码实现

首先我们手搓一个二叉树出来。

#include <stdio.h>
#include <stdlib.h>typedef char BTDataType;
typedef struct BTNode //节点，用结构体封装
{BTDataTypeval;struct BTNode* left;struct BTNode* right;
}BTNode;BTNode* CreatNode(BTDataType x) //创建节点
{BTNode* node = (BTNode*)malloc(sizeof(BTNode));if (node == NULL){perror("malloc fail");return;}node->val = x;  node->left = NULL;node->right = NULL;return node;
};

int main()
{BTNode* node0 = CreatNode('A'); //创建节点BTNode* node1 = CreatNode('B');BTNode* node2 = CreatNode('C');BTNode* node3 = CreatNode('D');BTNode* node4 = CreatNode('E');BTNode* node5 = CreatNode('F');BTNode* node6 = CreatNode('G');//链接node0->left = node1;    node0->right = node2;node1->left = node3;node1->right = node4;node2->left = node5;node2->right = node6;return 0;
}

这里的链接和前面的图一致。

三种遍历方式的实现都是用了递归，递归的知识在这里不多说，不太懂得的建议先弄懂递归。

4.2.1 前序遍历

void Preorder(BTNode* node) //前序：根 左 右
{if (node == NULL)return;       //为空时直接返回printf("%c ", node->val);//根Preorder(node->left);    //左Preorder(node->right);   //右
}

我们传根节点过去。

Preorder(node0);

和我们前面分析的结果一样。

4.2.2 中序遍历

同样是递归实现，顺序不同。

void Inorder(BTNode* node) //中序：左 根 右
{if (node == NULL)return;       //为空时直接返回Inorder(node->left);     //左printf("%c ", node->val);//根Inorder(node->right);    //右
}

同样直接传根节点过去。

Inorder(node0);  //中序

和前面的分析结果一致。

4.2.3 后序遍历

后序遍历同理。

void Postorder(BTNode* node) //后序：左 右 根
{if (node == NULL)return;       //为空时直接返回Postorder(node->left);    //左Postorder(node->right);   //右printf("%c ", node->val); //根
}

直接传根节点过去。

Postorder(node0);//后序

和前面推理的结果一致。

4.2.4 层序遍历

层序遍历我们要结合队列来实现。根节点进队列，出队列的时候带着自己的“孩子”进队列。

到这一步之后，D出队列，D没有孩子，队列就不用进数据，E、F、G同理。

当队列为空时，数据全部出完，层序遍历完成。

C语言中没有队列的库，不过我们之前用C语言自己实现过队列：【数据结构】队列的概念、结构和实现详解

我们把自己实现的队列放进当前工程。

然后在二叉树的.c文件中包含队列的头文件。

#include "queue.h" //队列头文件

队列存放的数据是二叉树节点，所以我们还要在 queue.h 里改一下类型，只需要改动一句代码。

//typedef BTNode QDataType;  //不可以这样写
typedef struct BTNode* QDataType; //要用原生类型

现在就可以代码实现层序遍历了。

void Leveloder(BTNode* node) //层序遍历
{Queue q;QueueInit(&q); //队列初始化if (node)QueuePush(&q, node);while (!QueueEmpty(&q)){BTNode* temp = QueueFront(&q);//取队头数据printf("%c ", temp->val);QueuePop(&q); //根出//有子就入if (temp->left)QueuePush(&q, temp->left);if (temp->right)QueuePush(&q, temp->right);}QueueDestroy(&q); //队列销毁
}

拿前面的二叉树做测试。

Leveloder(node0);
printf("\n");

4.3 节点个数及高度等

4.3.1 节点个数

节点个数最好的求法就是递归，任意一棵树的节点个数都可以看成：左子树个数+右子树个数+1

int BTSize(BTNode* node)  //节点个数
{if (node == NULL)return 0;elsereturn BTSize(node->left) + BTSize(node->right) + 1;
}

这个代码可以用一个三目操作符进行简化。

int BTNodeSize(BTNode* node)  //节点个数
{return node == NULL ? 0 :BTNodeSize(node->left) + BTNodeSize(node->right) + 1;
}

验证一下代码，传根节点过去。

printf("BTNodeSize:%d\n", BTNodeSize(node0));

4.3.2 叶子节点个数

求叶子结点的个数同理，递归表示，求法为左节点的叶子节点个数+右节点的叶子节点个数。

int BTLeafSize(BTNode* node) //叶子节点个数
{if (node == NULL)return 0;if (node->left == NULL && node->right == NULL)return 1;return BTLeafSize(node->left) + BTLeafSize(node->right);
}

验证一下代码，传根节点过去。

printf("BTLeafSize:%d\n", BTLeafSize(node0));

4.3.3 二叉树的高度（深度）

求二叉树的高度，左子树和右子树谁更高，更高的那边+1就是树的高度了，每一棵树都按照这种方法计算，同样用到了递归。

int BTHeight(BTNode* node)  //树的高度
{if (node == NULL)return 0;int BTleft = BTHeight(node->left);  //左子树高度int BTright = BTHeight(node->right);//右子树高度return BTleft > BTright ? BTleft + 1 : BTright + 1;//返回大的高度+1
}

验证一下代码，传根节点过去。

printf("BTHeight:%d\n", BTHeight(node0));

4.3.4 第k层节点个数

求第k层的节点个数，可以看做求子节点的k-1层的节点个数。比如下图，求k=3层的节点个数，对第一层来说，k=3，对于第二层来说，k=2，对于第三层来说，k=1。

这里用递归来解决，代码如下。

int BTkSize(BTNode* node, int k)
{if (node == NULL) //为空就是没有节点return 0;if (k == 1) //求第一层，第一层就一个节点return 1;return BTkSize(node->left, k - 1) + BTkSize(node->right, k - 1);
}

我们用前面的二叉树来检测。

//求第三层节点个数
printf("BTHeight:%d\n", BTkSize(node0, 3));

4.3.5 查找值为x的结点

查找值为x的节点，我们可以选择前序遍历，前序遍历是最方便的。如果在根节点找到了，直接返回，不用再去左右子树找，如果根节点没找到，取左子树找，在左子树找到了就不用再去右子树找了，如果左右子树都没找到，返回NULL。

BTNode* BTFindx(BTNode* node, BTDataType x)
{if (node == NULL)return NULL;if (node->val == x)return node;BTNode* temp1 = BTFindx(node->left, x);if (temp1)return temp1;BTNode* temp2 = BTFindx(node->right, x);if (temp2)return temp2;return NULL;
}

我们用前面的二叉树验证一下。

//查找F
BTNode* ret = BTFindx(node0, 'F');
if (ret)printf("x:%c\n", ret->val);
elseprintf("Didn't find!\n");

//查找不存在的k
BTNode* ret = BTFindx(node0, 'k');
if (ret)printf("x:%c\n", ret->val);
elseprintf("Didn't find!\n");

4.4 二叉树的创建和销毁

4.4.1 销毁

二叉树的销毁要走后序遍历，根节点最后释放，如果先把根节点释放了，子节点就找不到了。

void BTDestroy(BTNode* node)
{if (node)return;BTDestroy(node->left);BTDestroy(node->right);free(node);
}

4.4.2 创建

假设要求通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树。先画图分析。

B的左子树就复原完了，现在复原B的右子树。

B复原完之后，也就是A的左子树全部复原完了，现在剩下的就是A的右子树。

现在我们思路就很清晰了。

//通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* CreateBT(BTDataType* a, int* pi)
{if (a[*pi] == '#')return NULL;BTNode* node = CreatNode(a[*pi]);(*pi)++;node->left = CreateBT(a, pi);  //建左节点(*pi)++;node->right = CreateBT(a, pi); //建右节点return node;
}

a是数组，pi是下标，要传地址过去。CreateNode是最开始写的一个创建节点的函数。

我们用前序打印一下这个二叉树。

int main()
{char arr[] = {"ABD##E#H##CF##G##"};int i = 0;BTNode* Tree = CreateBT(&arr, &i);Preorder(Tree); //前序printf("\n");return 0;
}

也可以试试中序、后序、层序遍历。

本次分享就到这里，我们下篇见~

【数据结构】二叉树

1.树的概念及结构

1.1 概念

1.2 结构

1.3 树的表示（详解）

2.二叉树

2.1 二叉树的概念

2.2 特殊二叉树

2.3 二叉树的存储结构

2.3.1 顺序存储

2.3.2 父子关系

2.3.3 链表存储

2.4 二叉树的性质

2.5 相关练习

3.堆

4.二叉树的链式结构

4.1 二叉树的遍历

4.1.1 前序、中序、后序遍历

4.1.2 层序遍历

4.2 二叉树的遍历的代码实现

4.2.1 前序遍历

4.2.2 中序遍历

4.2.3 后序遍历

4.2.4 层序遍历

4.3 节点个数及高度等

4.3.1 节点个数

4.3.2 叶子节点个数

4.3.3 二叉树的高度（深度）

4.3.4 第k层节点个数

4.3.5 查找值为x的结点

4.4 二叉树的创建和销毁

4.4.1 销毁

4.4.2 创建

相关资讯

热文排行

最新新闻

推荐新闻

热搜词