1200字范文 > 数据结构（十一） -- C语言版 -- 树 - 二叉树基本概念

数据结构（十一） -- C语言版 -- 树 - 二叉树基本概念

时间：2023-12-19 09:43:34

内容预览

零、读前说明一、二叉树相关概念1.1、定义1.2、性质1.3、满二叉树与完全二叉树1.3.1、满二叉树1.3.2、完全二叉树1.3.3、特点延伸二、二叉树储存结构2.1、顺序结构存储2.2、链式结构存储2.2.1、二叉链表表示法2.2.2、三叉链表表示法2.2.3、双亲表示法三、二叉树的遍历3.1、遍历的说明3.2、遍历的实质

零、读前说明

本文中所有设计的代码均通过测试，并且在功能性方面均实现应有的功能。设计的代码并非全部公开，部分无关紧要代码并没有贴出来。如果你也对此感兴趣、也想测试源码的话，可以私聊我，非常欢迎一起探讨学习。由于时间、水平、精力有限，文中难免会出现不准确、甚至错误的地方，也很欢迎大佬看见的话批评指正。嘻嘻。。。。。。。。。。。。收！

一、二叉树相关概念

1.1、定义

二叉树是n(n≥0)个节点的有限集合，由一个根节点以及两个互不相交的、分别称为左子树和右子树的二叉树组成。

二叉树的基本特征为：

（1）每个节点最多只有两个子树（不存在度大于2的节点）

（2）左子树和右子树的次序不能颠倒，是一种有序树

那么对于下图1.1的几种情况，均为合法的二叉树结构/形态。从左到右依次是：左右子树、左子树、右子树、根、空树。

图1.1 二叉树的形态

1.2、性质

1、在第i层的节点数目之多有2i - 1 -1个，并且在第i层上至少有1个节点（叶子节点）。

2、深度为i的二叉树，至多有2 k -1（k>0）个节点，并且深度为i是至少有i个节点。

3、对于一个二叉树，若度数为2的节点数有n2个，则叶子树（n0）必定为n0 = n2 +1个，比如下图1.2所致这样的树。

图1.2 二叉树举例

度数为2的节点有 5 个（A,B,C,D,E）

那这个的叶子节点有5+1=6个（F,I,G,K,L,M）。

1.3、满二叉树与完全二叉树

1.3.1、满二叉树

一个深度为k且有2k -1个节点的二叉树，也就是除了叶子节点，其他的所有节点均有两个子节点（左边、右边）。

图1.3 深度为4的满二叉树

1.3.2、完全二叉树

1、深度为k的有n个节点的二叉树，当且仅当其每一个节点斗鱼深度为k的满二叉树中编号从1到n的节点一一对应。

2、第k-1层和满二叉树一样，最后一层叶子节点尽量靠左，并且左边所有的节点都是2。

3、完全二叉树的特点就是，只有最后一层叶子不满，并且集中在左边。

图1.4 完全二叉树、不是完全二叉树

1.3.3、特点延伸

对于满二叉树和完全二叉树，还具下面的两个特点。

有n个节点的完全二叉树的深度为m = [ log2n ] + 1。

比如下面的这个（满）完全二叉树：

图1.5 根据节点求深度举例

上图中，其中节点个数为 11，那么根据上面的公式转换为 2x=11, 那么 x 的取值范围大概为 3.3 到 3.4 之间，那么向下取整数的话也就是X的值为3，所以此完全二叉树的深度为 3 + 1 = 4，与实际也是符合的。

对于完全二叉树，若从上到下，从左到右的依次编号（从1开始），则编号为i的节点。其左孩子编号必定为2i，其右孩子的编号必定为2i+1，其双亲的编号必定为i/2（如果i=1，则为树根，除外）。

比如下面的这个完全二叉树：

图1.6 二叉树编号示意

二、二叉树储存结构

2.1、顺序结构存储

像前面所言，按照二叉树节点的“从上到下、从左到右”进行编号，用一组连续的存储单元（数组）进行存储。

那么对于顺序存储后能否复原成唯一对应的二叉树形状呢？

1、如果是完全二叉树/满二叉树，根据完全/满二叉树的性质，下标值为i的双亲，其左孩子的下标值必定为2i，其右孩子的下标值必定为2i+1，所以则可以做到唯一的复原。

2、如果不是完全二叉树，那么如果要复原将难上加难，那么想要正确、唯一复原的话，那么可以将这个树转换为完全二叉树，将各层空缺处统统补上“虚节点” ，内容为空。

具体效果如图2.1所示。

图2.1 补"虚节点“示意图

就像咱们看到的一样，这种情况下存在很多的不足。

（1）空间浪费严重

（2）插入、删除等费时费力

2.2、链式结构存储

对于链式结构存储，设计不同的节点结构可以构成不同形式的链式存储结构。

图2.2 二叉树及存储结构（二叉链、三叉链）

2.2.1、二叉链表表示法

一般从根节点开始存储，所以访问树种的节点也只能从根节点开始。

二叉链表表示法的图例如下图2.3所示。

图2.3 二叉链表表示法

二叉链表表示法的结构模型如下面的示例代码。

/* 定义二叉树的节点类型 */typedef int TElemType;/* 二叉链表表示法的结构模型 */typedef struct BiTNode{TElemType data; /* 节点数据 */struct BiTNode *lchild; /* 左孩子 */struct BiTNode *rchild; /* 右孩子 */} BiTNode, *BiTree;

用下面的简单的代码实现二叉树的创建、初始化等操作，代码示例如下。

1、普通变量表示

/*** 功能：*创建并且初始二叉树 - 直接定义* 参数：*无* 返回值：*无**/void BiTree_Create_v(void){// 二叉树的节点定义BiTNode t1, t2, t3, t4, t5, t6;/* 内存初始化为0，这样用"^"表示的区域直接略过不写，就是NULL */memset(&t1, 0, sizeof(BiTNode));memset(&t2, 0, sizeof(BiTNode));memset(&t3, 0, sizeof(BiTNode));memset(&t4, 0, sizeof(BiTNode));memset(&t5, 0, sizeof(BiTNode));memset(&t6, 0, sizeof(BiTNode));/* 二叉树的数据初始化 */t1.data = 'A';t2.data = 'B';t3.data = 'C';t4.data = 'D';t5.data = 'E';t6.data = 'F';/* 二叉树的关系式的创建 */t1.lchild = &t2;t1.rchild = &t3;t2.lchild = &t4;t2.rchild = &t5;t3.lchild = &t6;printf("%s Finished!\n", __func__);}

2、指针表示

/*** 功能：*创建并且初始二叉树 - 指针定义* 参数：*无* 返回值：*无**/void BiTree_Create_p(void){/* 通过指针的形式创建，下面的两种创建方式一样的 */#if 0 BiTNode *p1, *p2, *p3, *p4, *p5, *p6;#elseBiTree p1, p2, p3, p4, p5, p6;#endifp1 = (BiTNode *)malloc(sizeof(BiTNode));p2 = (BiTNode *)malloc(sizeof(BiTNode));p3 = (BiTNode *)malloc(sizeof(BiTNode));p4 = (BiTNode *)malloc(sizeof(BiTNode));p5 = (BiTNode *)malloc(sizeof(BiTNode));p6 = (BiTNode *)malloc(sizeof(BiTNode));memset(p1, 0, sizeof(BiTNode));memset(p2, 0, sizeof(BiTNode));memset(p3, 0, sizeof(BiTNode));memset(p4, 0, sizeof(BiTNode));memset(p5, 0, sizeof(BiTNode));memset(p6, 0, sizeof(BiTNode));p1->data = 'A';p2->data = 'B';p3->data = 'C';p4->data = 'D';p5->data = 'E';p6->data = 'F';/* 二叉树的关系式的创建 */p1->lchild = p2;p1->rchild = p3;p2->lchild = p4;p2->rchild = p5;p3->lchild = p6;printf("%s Finished!\n", __func__);}

2.2.2、三叉链表表示法

在二叉链表的基础上，增加一个双亲域（直接前驱）指针，那么就可倒查某节点的双亲。

三叉链表表示法的图例如下图2.4所示。

图2.4 三叉链表表示

三叉链表表示法的结构模型如下面的示例代码。

/* 定义节点的类型 */typedef int TElemType;/* 三叉链表表示法的结构模型 */typedef struct TriTNode{TElemType data;/* 节点数据 */struct TriTNode *lchild; /* 左孩子 */struct TriTNode *rchild; /* 右孩子 */struct TriTNode *parent; /* 双亲节点 */} TriTNode, *TriTree;

用下面的简单的代码实现三叉链表创建、初始化等操作，代码示例如下。

/*** 功能：*创建并且初始三叉树 - 三叉连表示法* 参数：*无* 返回值：*无**/void TriTree_Create(void){TriTNode tr1, tr2, tr3, tr4, tr5, tr6;/* 内容村初始化为0 */memset(&tr1, 0, sizeof(TriTNode));memset(&tr2, 0, sizeof(TriTNode));memset(&tr3, 0, sizeof(TriTNode));memset(&tr4, 0, sizeof(TriTNode));memset(&tr5, 0, sizeof(TriTNode));memset(&tr6, 0, sizeof(TriTNode));tr1.data = 1;tr2.data = 2;tr3.data = 3;tr4.data = 4;tr5.data = 5;/* 三叉树的关系式的创建 */tr1.lchild = &tr2;tr1.rchild = &tr3;tr2.lchild = &tr4;tr2.rchild = &tr5;tr2.parent = &tr1;tr3.lchild = &tr6;tr3.parent = &tr1;tr4.parent = &tr2;tr5.parent = &tr2;tr6.parent = &tr3;printf("%s Finished!\n", __func__);}

2.2.3、双亲表示法

在子节点中保存了双亲的位置信息。由两个表用来表示，分别为节点表、节点关系表。双亲表示法的图例如下图2.5所示。

图2.5 双亲表示法

双亲表示法的结构模型如下面的示例代码。

/* 定义节点的类型 */typedef int TElemType;/* 双亲表示法的结构模型 */#define TREE_SIZE_MAX 20 /* 树的最大容量 */typedef struct BPTNode{TElemType data; /* 节点数据 */int parentPostion; /* 指向双亲的指针 -- 数组的下标 */char LRFlag; /* 左孩子-右孩子的标志 */} BPTNode;typedef struct BPTree{BPTNode nodes[TREE_SIZE_MAX]; /* 保存节点 */int nodeCnt; /* 节点的数量 */int root; /* 根节点的位置，保存双亲结点的数组下标 */} BPTree;

用下面的简单的代码实现双亲创建、初始化等操作，代码示例如下。

/*** 功能：*创建并且初始二叉树 - 双亲表示法* 参数：*无* 返回值：*无* 说明：*为了方便标识根节点，parentPostion、LRFlag两个元素全部为0标识根节点，当然您可以随意定义的 **/void BPTree_Create(void){BPTree tree;/* 根节点,使用特殊标识来表示根节点 */tree.nodes[0].parentPostion = 0;tree.nodes[0].data = 'A';tree.nodes[0].LRFlag = 0;/* B节点，LRFlag = 1 表示为左孩子节点 */tree.nodes[1].parentPostion = 0;tree.nodes[1].data = 'B';tree.nodes[1].LRFlag = 1;/* C节点，LRFlag = 2 表示为右孩子节点 */tree.nodes[2].parentPostion = 0;tree.nodes[2].data = 'C';tree.nodes[2].LRFlag = 2;/* D节点 */tree.nodes[3].parentPostion = 1;tree.nodes[3].data = 'D';tree.nodes[3].LRFlag = 1;/* E节点 */tree.nodes[4].parentPostion = 1;tree.nodes[4].data = 'E';tree.nodes[4].LRFlag = 2;/* F节点 */tree.nodes[5].parentPostion = 2;tree.nodes[5].data = 'F';tree.nodes[5].LRFlag = 1;printf("%s Finished!\n", __func__);}