《数据结构C语言版》——二叉树详解(图文并茂)

哈喽！这里是一只派大鑫，不是派大星。本着基础不牢，地动山摇的学习态度，从基础的C语言语法讲到算法再到更高级的语法及框架的学习。更好地让同样热爱编程(或是应付期末考试狗头.jpg)的大家能够在学习阶段找到好的方法、路线，让天下没有难学的程序(只有秃头的程序员 2333)，学会程序和算法，走遍天下都不怕！

引言

本文从最基础的什么是树开始，依次讲解树、二叉树的全部知识，并给出参考代码，相信哪怕是小白的你，在看完文章后也能豁然开朗。
妈妈再也不担心我不会手写数据结构了

树

在数据结构前面的章节，我们学习的都是一对一的线性结构，今天我们来学习一对多的情况，这就得提到“树”这个数据结构了~~~
那么什么是树呢？
如下这个简单的图就是树！

树的定义

这样还不够理解，我们得通过定义的方式加深印象。
树：是n(n≥0)个结点的有限集。 n=0时称为空树。
在任意一颗非空树中：
①有且仅有一个特定的称为根(root)的结点；
②当n＞1时，其余结点可分为m(m＞0)个互不相交的有限集，其中每个集合本身又是一棵树；
如图所示：
A、B都是树，但是C、D有相交的点，所以不是树

树的相关概念

初步认识什么是树之后，我们来了解树的一些相关概念。
结点的度：
        结点拥有的子树称为结点的度；
叶结点：
        度为0的结点称为叶子结点或终端结点；
树的度：
        树的度是树内各结点的度的最大值；
孩子结点：
        结点的子树的根称为该结点的孩子，相应地，该结点称为孩子的双亲；
兄弟结点：
        同一个双亲的孩子之间互称为兄弟；
祖先：
        结点的祖先是从根到该结点所经分支上的所有结点；
堂兄弟：
        双亲在同一层的节点互为堂兄弟；
子孙：
        以某结点为根的子树中的任一结点都称为该结点的子孙；
层次：
        结点的层次从根开始定义起，根为第一层，根的孩子为第二层；
树的深度：
        树中结点的走最大层次称为深度；
有序树：
        如果将树中结点的各子树看成从左至右是有次序的，不能互换的，则称该树为有序树，否则称为无序树；
森林：
        森林是m(m≥0)棵互不相交的树的集合。
下面配合图例来进行说明：
1的孩子为2，8，反之2和8的父结点为1，9的父结点为8；
1结点的度为2，2结点的度为2，4结点的度为3，因为结点4的度最大，所以该树的度为3；
5、6、7、3、9的度为0，所以都是叶子结点；
3和4互为兄弟结点，同样的5、6、7也互为兄弟结点；
4和9以及3和9都是堂兄弟关系；
结点5的祖先为4、2、1结点；
结点2的子孙为3、4、5、6、7；
从根开始定义，第一层，第二层..则图中树的高度为4；
结点2的高度为2。

树的存储结构

双亲表示法

有的结点可能没有孩子，但是除了根结点外，它们一定都有双亲，而且有且仅有一个双亲结点。
所谓双亲表示法就是在每个结点中，附设一个指示器指示其双亲结点在数组中的位置。
即一维数组的每个元素分别包含data 和 parent 关系。
相当于一个静态链表。同时，这里规定根节点的parent 指向-1。
例如这样一棵树：
用双亲表示法表示即为：
双亲表示法具有以优点：
结构简单；
查找双亲或祖先结点方便。

其代码结构如下：

/* 树的双亲表法结点结构定义*/
#define MAX_TREE_SIZE 100
typedef int  ElemeType;

typedef struct PTNode{ // 结点结构
    ElemeType data; //结点数据
    int parent;    // 双亲位置
}PTNode;

typedef struct { // 树结构
    PTNode nodes[MAX_TREE_SIZE];   // 结点数组
    int r; // 根的位置
    int n; // 结点数
}PTree;

孩子表示法

将树中的每个结点的孩⼦结点排列成⼀个线性表，⽤链表存储起来。对于含有 n 个结点的树来说，就会有 n 个单链表，将 n 个单链表的头指针存储在⼀个线性表中，这样的表⽰⽅法就是孩子表示法。如果结点没有孩⼦（例如叶⼦结点），那么它的单链表为空表。

例如这样一棵树用双亲表示法表示为：

其代码结构如下：

/* 树的孩子表示法结构定义*/
#define MAX_TREE_SIZE 100
typedef int  ElemeType;

typedef struct CTNode{  // 孩子结点
    int child; // 孩子结点的下标
    struct CTNode * next; // 指向下一结点的指针
}*ChildPtr;

typedef struct {  // 表头结构
    ElemeType data; // 存放在数中的结点数据
    ChildPtr firstchild; // 指向第一个孩子的指针
}CTBox;

typedef struct {  // 树结构
    CTBox nodes[MAX_TREE_SIZE]; // 结点数组
    int r;  // 根的位置
    int n;  // 结点树
}CTree;

孩子兄弟表示法

任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。
因此我们设置两个指针，分别指向该结点的第一个孩子和此节点的右兄弟
孩子兄弟表示法的结点结构
data(数据域) firstchild(指针域) rightsib(指针域)
存储结点的数据信息存储该结点的第一个孩子的存储地址存储该结点的右兄弟结点的存储地址

data(数据域)	firstchild(指针域)	rightsib(指针域)
存储结点的数据信息	存储该结点的第一个孩子的存储地址	存储该结点的右兄弟结点的存储地址

我们也常称其为 左孩子右兄弟，这一“秘籍”在做手画图的题时很有效
例如这样一棵树：
用孩子兄弟表示法表示的结果如下：

其代码结构如下：

/* 树的孩子兄弟表示法结构定义*/
#define MAX_TREE_SIZE 100
typedef int  ElemeType;

typedef struct CSNode{
    ElemeType data;
    struct CSNode * firstchild;
    struct CSNode * rightsib;
    
}CSNode, *CSTree;

自此，树的相关性质和表示方法及其结构我们都学习了，接下来才是重点内容，二叉树！

二叉树

一图带你明确什么是二叉树！！！
没错这个就是二叉树~~ 仔细看，每一个小树枝都仅有两个“分支”

二叉树的定义

光有图还不够严谨，二叉树的定义是这样的
二叉树(Binary Tree)：是n(n≥0)个结点的有限集合，该集合或者为空集(称为空二叉树)，或者由一个根结点和两颗互不相交的、分别称为根结点的左子树和右子树的二叉树组成。
定义就是这样，好像并不清楚，简而言之满足以下两个条件的树就是二叉树：
本身是有序树；
树中包含的各个结点的度不能超过 2，即只能是 0、1 或者 2；
如图所示，a的度最多是2，所以是二叉树，而b有度为3的结点，所以不是二叉树！

二叉树的特点

二叉树肯定有不同于普通树的特点来彰显它的好处。
二叉树的特点有：
每个结点最多有两颗子树，所以二叉树中不存在度大于2的结点。注意不是只有两颗子树，而是最多有。没有子树或者有一颗子树都是可以的。
左子树和右子树是有顺序的，次序不能颠倒。就像人有双手、双脚。
即使树中某结点只有一颗树，也要区分它是左子树还是右子树。
如图左右是不一样的存在
由于“左右有别”这一性质，所以二叉树有了五种基本形态：
空二叉树
只有一个根结点
根结点只有左子树
根结点只有右子树
根结点既有左子树又有右子树
二叉树五种基本形态如下图所示：
那么如果是有三个结点的二叉树，又有几种形态呢？
没错，也是五种，你画对了吗~~~
它们都代表不同的二叉树

二叉树的性质

二叉树有一些需要理解并且记住的性质，以便于我们更好地使用它。
二叉树性质1：在二叉树的第i层上最多有2^(i-1)个结点（i≥1）。
第一层是根结点，只有一个，所以2(1-1）=20=1。第二层有两个，2(2-1)=21=2。第三层有四个，2(3-1)=22=4。第四层有八个，2(4-1)=2^3=8。
二叉树性质2：深度为k的二叉树至多有2^k-1个结点（k≥1）。
注意这里一定要看清楚，是2k后再减去1，而不是2(k-1)。以前很多同学不能完全理解，这样去记忆，就容易把性质2与性质1给弄混淆了。深度为k意思就是有k层的二叉树，我们先来看看简单的。如果有一层，至多1=21-1个结点。如果有二层，至多1+2=3=22-1个结点。如果有三层，至多1+2+4=7=23-1个结点。如果有四层，至多1+2+4+8=15=2^4-1个结点。
二叉树性质3：对任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。
终端结点数其实就是叶子结点数，而一棵二叉树，除了叶子结点外，剩下的就是度为1或2的结点数了，我们设n1为度是1的结点数。则树T结点总数n=n0+n1+n2
终端结点数其实就是叶子结点数，而一棵二叉树，除了叶子结点外，剩下的就是度为1或2的结点数了，我们设n1为度是1的结点数。则树T结点总数n=n0+n1+n2 。
二叉树性质4：具有n个结点的完全二叉树的深度为|log（2^n）+1| (向下取整)。
由满二叉树的定义我们可以知道，深度为k的满二叉树的结点数n一定是2k-1。因为这是最多的结点个数。那么对于n=2k-1倒推得到满二叉树的深度为k=log2(n＋1)，比如结点数为15的满二叉树，深度为4。
二叉树性质5：如果对一棵有n个结点的完全二叉树（其深度为|log（2^n）+1|）的结点按层序编号（从第一层到第层，每层从左到右），对任一结点i（1<=i<=n），有
1．如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是结点。
2．如果2i>n，则结点i无左孩子（结点i为叶子结点）；否则其左孩子是结点2i。
3．如果2i+1>n，则结点i无右孩子；否则其右孩子是结点2i+1

特殊的二叉树

二叉树再进行细分也能划分好几种二叉树，暂时只需要了解并且能够辨别，至于有什么用处，以后再讨论~~~

斜树

顾名思义，斜树一定得是斜着的树。
所有结点都只有左子树的二叉树叫左斜树
所有结点都只有右子树的二叉树叫右斜树
两者统称为斜树。
如图这就是左斜树和右斜树

满二叉树

在一棵二叉树中，所有分支结点都存在左子树和右子树，并且所有的叶子都在同一层，这种树我们称之为满二叉树。
根据定义，满二叉树就是这样的：
但是这样的情况：
只有B是满二叉树
相信你已经有所判断能力了~~
满二叉树有属于自己的特点：
叶子只能出现在最下一层
非叶子结点的度一定是2
在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多

完全二叉树

定义：对一颗具有n个结点的二叉树按层序编号，如果编号为i(1 ≤ i ≤ n )的结点域同样深度的满二叉树中编号为i的结点在二叉树中的位置完全相同，则这棵树称为完全二叉树。
好像不是很明白。换而言之
若一棵二叉树至多只有最下面两层的结点的度数可以小于2，并且最下层的结点都集中在该层最左边的若干位置上，则此二叉树为完全二叉树。
完全二叉树就是这样的：
对比一下：
同样的，完全二叉树也有自己的特点：
叶子结点只用出现在最下两层
最下层的叶子一定集中在左部连续位置
倒数两层若有叶子结点，一定都在右部连续位置
如果结点度为1，则该结点只有左孩子
同样结点数的二叉树，完全二叉树的深度最小

二叉树的存储结构

顺序存储

顺序存储只适用于完全二叉树、满二叉树
由于它们的特殊性，使得用顺序存储结构也可以轻松实现。
顺序存储结构就是用一维数组存储二叉树中的结点，并且结点的存储位置，也就是数组的下标，要能体现结点之间的逻辑关系，比如双亲与孩子的关系，左右兄弟的关系等。
如图这样一个二叉树：
我们就可以将其存储在数组中，其对应关系就是这样的：
根据性质，将树中结点按照层次并从左到右依次标号(从下标0开始)，若结点 $i$ 有左右孩子，则其左孩子结点为 2i+1，右孩子结点为 2i+2，此性质可用于还原数组中存储的完全二叉树
若下标从1开始也是一样的道理，左孩子结点为2i，右孩子结点为2i+1

二叉链表

二叉树每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域就很方便存储这样的结构了。我们称其为二叉链表
结点结构如图所示：
因此我们存储二叉树只需要将左右孩子的指针指向其对应的孩子即可，就像这样：
根据这个图，我们不难得到结点的存储结构代码：
//结点结构体定义
typedef struct BTNode{
	int data;
	struct BTNode *LChild,*RChild;
}BTNode,*BTree;
以这样的一颗简单的二叉树，我们了解如何手动创建一下二叉链表：
int main(){
	BTree root = (BTNode *)malloc(sizeof(BTNode));
	root->data = 1;
	BTNode *p = (BTNode *)malloc(sizeof(BTNode));
	p->data = 2;
	root->LChild = p;
	p = (BTNode *)malloc(sizeof(BTNode));
	p->data = 3;
	root->RChild = p;
	printf("根：%d 左孩子：%d 右孩子：%d\n",root->data,root->LChild->data,root->RChild->data);
	return 0;
}
得到结果显然就是这样的：

二叉树的遍历

二叉树的遍历是指 从根结点出发，按照某种次序一次访问二叉树中的所有结点，使得每个结点被访问一次且仅被访问一次。
二叉树的遍历方式有很多，如果我们限制了从左到右的方式，那么主要分为以下四种：
前序遍历
中序遍历
后序遍历
层次遍历
接下来我们对这四种遍历进行系统的学习~~~

前序遍历

规则是：
若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。
注意：这里用词和贴切~~明明在说前序遍历的规则，结果规则里又是前序遍历，没错这就是递归！
使用递归来实现遍历操作是非常的简洁。

递归实现遍历及其简洁明了。
前序遍历的代码如下：
//前序遍历
void PreOrderTraverse(BTree T){
	if(T == NULL)
		return;
	printf("%d",T->data);
	PreOrderTraverse(T->LChild);
	PreOrderTraverse(T->RChild);
}

中序遍历

第一次经过时不访问，等遍历完左子树之后再访问，然后遍历右子树

中序遍历和前序遍历原理是一样的，差别只是访问的次序不同，体现在代码上就上顺序的差异。
中序遍历的代码如下：
//中序遍历
void InOrderTraverse(BTree T){
	if(T == NULL)
		return;
	PreOrderTraverse(T->LChild);
	printf("%d",T->data);
	PreOrderTraverse(T->RChild);
}

后序遍历

第一次和第二次经过时都不访问，等遍历完该节点的左右子树之后，最后访问该节点

同样的，后序遍历和前序遍历原理是一样的，差别只是访问的次序不同，体现在代码上就上顺序的差异。
后序遍历的代码如下：
//后序遍历
void PostOrderTraverse(BTree T){
	if(T == NULL)
		return;
	PreOrderTraverse(T->LChild);
	PreOrderTraverse(T->RChild);
	printf("%d",T->data);
}

层次遍历

通过对树中各层的节点从左到右依次遍历，即可实现对正棵二叉树的遍历，此种方式称为层次遍历。

推导遍历结果

除了掌握四种遍历方式的思想和代码的实现，能够根据已知的遍历结果来反推二叉树的形态也是考研、期末的常考重点题型。

前序+中序遍历序列

通过遍历结果来反推二叉树的形态，最重要的是理解每种遍历之间和二叉树的联系。
例如：我们可以从前序遍历得到根，其第一个就是根结点，根结点在其中序遍历的序列中，把该位置左右分为了根结点的左右子树，然后我们就可以将整个中序序列划分为三大部分了。然后我们又对其每一个小部分进行再次的判断，又能得到左、右子树的根和对应的左右子树…一直细化三部分后就能得到最终结果了。
前序遍历序列：根结点左子树的前序遍历序列右子树的前序遍历序列
中序遍历序列：左子树的中序遍历序列根结点右子树的中序遍历序列

例题：
由前序遍历第一个结点可知，该结点的根结点就是A，于是在中序遍历序列中找到A的左右，则在A的左边就是A左子树包含的结点，在A的右边就是A右子树包含的结点。
然后整个序列划分为 {B,C,D} A {E}
对于BCD这颗“小树”，在前序序列中得到D是根结点，然后在中序序列中找到D，D的左边是B，右边是C，所以对于{B,C,D}这个集合，D为根结点，B为D的左结点，C为D的右结点。
A的右子树由于只有E，所以E就是A的右孩子结点。
这样就完成了！我们可以得到如下的结果：

后序+中序遍历序列

如果是后序+中序遍历序列的话，思路也是一样的，但是在后序遍历序列中，靠右的才是根结点，这里和前序序列靠左刚好相反。
后序遍历序列：左子树的中序遍历序列右子树的中序遍历序列根结点
中序遍历序列：左子树的中序遍历序列根结点右子树的中序遍历序列

看一道例题：
思路和前序+中序一样的，只不过前序遍历第一个为根结点，后序遍历从后往前找根结点。
最终结果如下：

层序+中序遍历序列

层序遍历序列：根结点左子树的根右子树的根
中序遍历序列：左子树的中序遍历序列根结点右子树的中序遍历序列

例题：
方法也是一样的，对于层次遍历先遍历的是根结点，其他就不再赘述了，本题答案如下：
在画出二叉树形态后记得验证一下！不容马虎。

前序、后序、层序序列两两组合

学习完二叉树的遍历之后，我们还是没有实现整个二叉树，对的，还没说怎么建立二叉树，树都没有怎么遍历？？？
接下来，我们对二叉树的建立进行讲解。

二叉树的建立

对于普通的二叉树，为了能让每个结点确认是否有左右孩子，我们可以对它进行扩展，也就是将二叉树中每个结点的空指针引出一个“虚结点”，用“#”来代替。
同时，这里我们采用输入前序遍历序列来构造二叉树的方式进行讲解。
例如这样一颗二叉树：
将其空指针用“虚结点”引出后表示为：
其先序遍历序列为：
12#3##4##
那么如何创建呢？
我们有这样的规则：
按照输入的序列创建二叉树，分别递归的创建左子树和右子树
如遇到‘#’代表子树为空
于是递归实现的代码如下：
//方法二：先序遍历创建二叉树的序列存储
char str[24];
int index = 0;
//先序序列创建二叉树
void CreateTree(BTree *T){ //注意 这里使用二级指针，因为我们要修改指针的值
	char ch;
	//方法一 每次递归进行输入值
	scanf("%c",&ch);
	//ch = str[index++];  //方法二 先输入字符串
	if(ch == '#')
		*T = NULL;
	else{
		*T = (BTNode *)malloc(sizeof(BTNode));
		(*T)->data = ch;
		CreateTree(&(*T)->LChild);
		CreateTree(&(*T)->RChild);
	}
}
这里我们输入字符串时可以采用两种方法，一种就是递归时输入，只需要一行代码即可，上述代码就是这种方式；还有一种就是利用全局变量定义一个字符串进行输入，再定义一个index作为索引，每次自增操作。
测试代码：
int main(){
	BTree root = (BTNode *)malloc(sizeof(BTNode));
	printf("输入先序序列来创建二叉树：\n");
	//scanf("%s",str);  //方法二对应代码
	CreateTree(&root);
	printf("\n先序遍历结果：\n");
	PreOrderTraverse(root);
	printf("\n中序遍历结果：\n");
	InOrderTraverse(root);
	printf("\n后序遍历结果：\n");
	PostOrderTraverse(root);
	return 0;
}
其结果如下：

二叉树完整代码

二叉树定义、创建、遍历的完整代码如下

#include<stdio.h>
#include<string.h>
#include<iostream> 
#include<math.h>
using namespace std;
//二叉链表的实现
//结点结构体定义
typedef struct BTNode{
	char data;
	struct BTNode *LChild,*RChild;
}BTNode,*BTree;
//前序遍历
void PreOrderTraverse(BTree T){
	if(T == NULL)
		return;
	printf("%c",T->data);
	PreOrderTraverse(T->LChild);
	PreOrderTraverse(T->RChild);
}
//中序遍历
void InOrderTraverse(BTree T){
	if(T == NULL)
		return;
	PreOrderTraverse(T->LChild);
	printf("%c",T->data);
	PreOrderTraverse(T->RChild);
}
//后序遍历
void PostOrderTraverse(BTree T){
	if(T == NULL)
		return;
	PostOrderTraverse(T->LChild);
	PostOrderTraverse(T->RChild);
	printf("%c",T->data);
}
//方法二：先序遍历创建二叉树的序列存储
//char str[24];
//int index = 0;
//先序序列创建二叉树
void CreateTree(BTree *T){ //注意 这里使用二级指针，因为我们要修改指针的值
	char ch;
	//方法一 每次递归进行输入值
	scanf("%c",&ch);
	//ch = str[index++];  //方法二 先输入字符串
	if(ch == '#')
		*T = NULL;
	else{
		*T = (BTNode *)malloc(sizeof(BTNode));
		(*T)->data = ch;
		CreateTree(&(*T)->LChild);
		CreateTree(&(*T)->RChild);
	}
}
int main(){
	BTree root = (BTNode *)malloc(sizeof(BTNode));
	printf("输入先序序列来创建二叉树：\n");
	//scanf("%s",str);  //方法二对应代码
	CreateTree(&root);
	printf("\n先序遍历结果：\n");
	PreOrderTraverse(root);
	printf("\n中序遍历结果：\n");
	InOrderTraverse(root);
	printf("\n后序遍历结果：\n");
	PostOrderTraverse(root);
	return 0;
}

树、二叉树的内容到这里就讲完了，这里只是最基础的部分，后序还有平衡二叉树、二叉搜索树、线索二叉树、红黑树、哈夫曼树、森林和树与二叉树的转换，这些内容会在单独的文章进行讲解，感兴趣的读者可以持续关注本博客。
创作不易，还请大家多多三连支持~~~~

文章出处登录后可见！

已经登录？立即刷新

《数据结构C语言版》——二叉树详解(图文并茂)

引言

树

树的定义

树的相关概念

树的存储结构

双亲表示法

孩子表示法

孩子兄弟表示法

二叉树

二叉树的定义

二叉树的特点

二叉树的性质

特殊的二叉树

斜树

满二叉树

完全二叉树

二叉树的存储结构

顺序存储

二叉链表

二叉树的遍历

前序遍历

中序遍历

后序遍历

层次遍历

推导遍历结果

前序+中序遍历序列

后序+中序遍历序列

层序+中序遍历序列

前序、后序、层序序列两两组合

二叉树的建立

二叉树完整代码

相关推荐