DataStructure4（树和二叉树）

zhangzhang2025-11-062025-11-06

树和二叉树

1.树的定义

树(Tree)是n(n>=0)个结点的有限集，它或为空树(n= 0); 或为非空树，对于非空树T:

(1)有且仅有一个称之为根的结点；
(2)除根结点以外的其余结点可分为 m(m>O）个互不相交的有限集 T1 T2 , …Tm，其中每一个集合本身又是一棵树，并且称为根的子树(SubTree)。

2.树的基本术语

在这里插入图片描述

(1)结点:树中的一个独立单元。包含一个数据元素及若于指向其子树的分支，如图 (b) 中的 A 、 B 、 C 、 D 等.（下面术语中均以图 (b) 为例来说明）

(2)结点的度：结点拥有的子树数称为结点的度。例如，A的度为 3, C的度为l, F的度为0。

(3)树的度：树的度是树内各结点度的最大值。图 (b) 所示的树的度为3。

(4) 叶子：度为 0 的结点称为叶子或终端结点。结点 K 、 L 、 F 、 G 、 M 、 I 、 J都是树的叶子。

(5) 非终端结点：度不为 0 的结点称为非终端结点或分支结点。除根结点之外，非终端结点也称为内部结点。

(6)双亲和孩子：结点的子树的根称为该结点的孩子，相应地，该结点称为孩子的双亲。例如，B的双亲为A, B的孩子有E和F。

(7) 兄弟：同一个双亲的孩子之间互称兄弟。例如，H 、 I 和J互为兄弟。

(8) 祖先：从根到该结点所经分支上的所有结点。例如， M 的祖先为 A 、 D 和H。

(9) 子孙：以某结点为根的子树中的任一结点都称为该结点的子孙。如 B 的子孙为E 、 K 、 L 和F。

(10) 层次：结点的层次从根开始定义起，根为第一层，根的孩子为第二层。树中任一结点的层次等千其双亲结点的层次加 l。

(11)堂兄弟：双亲在同一层的结点互为堂兄弟。例如，结点 G 与E 、 F、 H 、 I 、 J互为堂兄弟。

(12)树的深度：树中结点的最大层次称为树的深度或高度。图(b)所示的树的深度为4。

(13)有序树和无序树：如果将树中结点的各子树看成从左至右是有次序的（即不能互换），则称该树为有序树，否则称为无序树。在有序树中最左边的子树的根称为第一个孩子，最右边的称为最后一个孩子。

(14)森林：是 m (m>=0)棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。由此，也可以用森林和树相互递归的定义来描述树

3.二叉树的定义

二叉树(Binary Tree)是n(n>=O)个结点所构成的集合，它或为空树(n= 0); 或为非空树，对于非空树T:

(1) 有且仅有一个称之为根的结点；
(2)除根结点以外的其余结点分为两个互不相交的子集T1和T2, 分别称为T的左子树和右子树，且T1和T2本身又都是二叉树。

二叉树与树一样具有递归性质，二叉树与树的区别主要有以下两点：

(1 )二叉树每个结点至多只有两棵子树（即二叉树中不存在度大于2 的结点）；
(2.)二叉树的子树有左右之分，其次序不能任意颠倒。

二叉树的递归定义表明二叉树或为空，或是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。由于这两棵子树也是二叉树，则由二叉树的定义，它们也可以是空树。由此，二叉树可以有5种基本形态，如图所示。

在这里插入图片描述

4.二叉树的性质和存储结构

二叉树的性质

性质1 在二叉树的第i层上至多有2^i-1^个结点（i>=1)。

性质2 深度为K的二叉树至多有 2^k^-1个结点 (k>=1)。

性质3 对任何一棵二叉树T, 如果其终端结点数为n0，度为2的结点数为n2,则n0 = n2+1

介绍两种特殊形态的二叉树，它们是满二叉树和完全二叉树
在这里插入图片描述

满二叉树：深度为 K且含有2k-1个结点的二叉树。图(a)所示是一棵深度为4 的满二叉树

满二叉树的特点是：

每一层上的结点数都是最大结点数，即每一层i的结点数都具有最大值 2i-l.

可以对满二叉树的结点进行连续编号，约定编号从根结点起，自上而下，自左至右。由此可引出完全二叉树的定义。

完全二叉树：深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树。图 (b)所示为一棵深度为4的完全二叉树。

完全二叉树的特点是：

(1)叶子结点只可能在层次最大的两层上出现；
(2)对任一结点，若其右分支下的子孙的最大层次为L, 则其左分支下的子孙的最大层次必为 L 或L+ 1。图中（c）和(d) 不是完全二叉树

性质 4 具有 n 个结点的完全二叉树的深度为log2n+ 1 。

二叉树的存储结构

类似线性表，二叉树的存储结构也可采用顺序存储和链式存储两种方式

顺序存储结构

//-----二叉树的顺序存储表示－－－－－
#define MAXTSIZE 100 
typedef TElemType SqBiTree [MAXTSIZE]; //二叉树的最大结点数
SqBiTree bt; //0 号单元存储根结点

顺序存储结构使用一组地址连续的存储单元来存储数据元素，为了能够在存储结构中反映出结点之间的逻辑关系，必须将二叉树中的结点依照一定的规律安排在这组单元中。

在这里插入图片描述

对于完全二叉树，只要从根起按层序存储即可，依次自上而下、自左至右存储结点元素，即将完全二叉树上编号为i 的结点元素存储在如上定义的一维数组中下标为i-1的分量中。例如，图(a)所示为图(b)所示完全二叉树的顺序存储结构。

对于一般二叉树，则应将其每个结点与完全二叉树上的结点相对照，存储在一维数组的相应分量中，图 ©所示二叉树的顺序存储结构如图 (b)所示，图中以”0”表示不存在此结点。

链式存储结构

在这里插入图片描述

//- - - - -二叉树的二叉链表存储表示－ －－－－
typedef struct BiTNode{ 
TElemType data; 
struct BiTNode *lchild,*rchild; //结点数据域
) BiTNode,*BiTree; //左右孩子指针

在这里插入图片描述

5.遍历二叉树和线索二叉树

线索二叉树是在第一次遍历时将结点的前驱、后继信息存储下来，便于再次遍历二叉树

遍历二叉树

遍历二叉树(traversing binary tree)是指按某条搜索路径巡访树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。访间的含义很广，可以是对结点做各种处理，包括输出结点的信息，对结点进行运算和修改等。遍历二叉树是二叉树最基本的操作，也是二叉树其他各种操作的基础，遍历的实质是对二叉树进行线性化的过程，即遍历的结果是将非线性结构的树中结点排成一个线性序列。由于二叉树的每个结点都可能有两棵子树，因而需要寻找一种规律，以便使二叉树上的结点能排列在一个线性队列上，从而便于遍历

回顾二叉树的递归定义可知，二叉树是由3个基本单元组成：根结点、左子树和右子树。因此，若能依次遍历这三部分，便是遍历了整个二叉树。假如从 L、D、R 分别表示遍历左子树、访问根结点和遍历右子树，则可有DLR、LDR、LRD、DRL、RDL、RLD这6种遍历二叉树的方案。

若限定先左后右，则只有前3种情况，分别称之为先（根）序遍历、中（根）序遍历和后（根）序遍历。

基于二叉树的递归定义，可得下述遍历二叉树的递归算法定义
先序遍历二叉树的操作定义如下：

若二叉树为空，则空操作；否则
(I)访问根结点；
(2)先序遍历左子树；
(3)先序遍历右子树。

中序遍历二叉树的操作定义如下：

若二叉树为空，则空操作；否则
(I)中序遍历左子树；
(2)访问根结点；
(3)中序遍历右子树。

后序遍历二叉树的操作定义如下：

若二叉树为空，则空操作；否则
(I)后序遍历左子树；
(2)后序遍历右子树；
(3)访问根结点。

递归与非递归遍历二叉树

中序递归遍历二叉树

void InOrderTraverse{BiTree T) 
{//中序遍历二叉树T的递归算法
	if(T)//若二叉树非空
	{ 
	InOrderTraverse {T-> lchild) ; //中序遍历左子树
	cout<<T->data; //访问根结点
	InOrderTraverse {T-> rchild); //中序遍历右子树
	}
}

只需交换访问根节点的顺序即可是前序后序
3种遍历算法不同处仅在于访问根结点和遍历左、右子树的先后关系
可利用栈将递归算法改写成非递归算法

中序非递归遍历二叉树
算法思路：

1.初始化一个空栈 s, 指针p指向根结点。
3.当p非空或者栈S非空时，循环执行以下操作：
• 如果p非空，则将p进栈，p指向该结点的左孩子；
• 如果p为空，则弹出栈顶元素并访问，将p指向该结点的右孩子

void InOrderTraverse(BiTree T) 
{//中序遍历二叉树T的非递归算法
	InitStack(S);p=T; 
	q=new BiTNode; 
	while (p ||! StackEmpty (S)) 
	{
		if(p) 
		{ 
		Push(S,p);//根指针进栈
		p=p-> lchild;//根指针进栈， 遍历左子树
		}
		else //p非空
		{
		Pop (S, q);//退栈
		cout<<q->data//访问根结点
		p=q-> rchild;//遍历右子树
		}
	}
}

无论是递归还是非递归遍历二叉树，因为每个结点被访问一次，则不论按哪一种次序进行遍历，对含 n 个结点的二叉树，其时间复杂度均为 O(n)。所需辅助空间为遍历过程中栈的最大容量，即树的深度，最坏情况下为 n, 则空间复杂度也为 O(n)。

二叉树的先序、中序和后序遍历是最常用的三种遍历方式。此外，还有一种按层次遍历二叉树的方式，这种方式按照 “从上到下，从左到右＂的顺序遍历二叉树，即先遍历二叉树第一层的结点，然后是第二层的结点，直到最底层的结点，对每一层的遍历按照从左到右的次序进行

遍历序列确定二叉树

若二叉树中各结点的值均不相同，任意一棵二叉树结点的先序序列、中序序列和后序序列都是唯一的。反过来，若已知二叉树遍历的任意两种序列，能否确定这棵二叉树呢？这样确定的二叉树是否是唯一的呢？

由二叉树的先序序列和中序序列，或由其后序序列和中序序列均能唯一地确定一棵二叉树

前中后缀表达式（波兰式表达式）

二叉树表示下述表达式

a+b*(c-d)一e/f

若先序遍历此二叉树，按访间结点的先后如字将结点排列起来，可得到二叉树的先序序列为

-+ a * b -cd /ef

中序遍历此二叉树，可得此二叉树的中序序列为

a + b * c - d - e/f

后序遍历此二叉树，可得此二叉树的后序序列为

abed-*+ ef/-

遍历算法的应用

1.先序遍历的顺序建立二叉链表

算法思路：
1.扫描字符序列，读入字符ch。
2.如果ch是一个 “#” 字符，则表明该二叉树为空树，即T为NULL; 否则执行以下操作：

申请一个结点空间T;
• 将ch赋给T-> data;
• 递归创建T的左子树；
• 递归创建T的右子树

void CreateBiTree(BiTree &T) 
{//按先序次序输入二叉树中结点的值（ 一个字符）， 创建二叉链表表示的二叉树T
    cin>>ch; 
    if(ch== '#') T=NULL; //递归结束， 建空树
    else //递归创建二叉树
        {
        T=new BiTNode; //生成根结点
        T-> data=ch; //根结点数据域置为 ch
        CreateBiTree (T-> lchild); //递归创建左子树
        CreateBiTree (T-> rchild); //递归创建右子树
        }
｝

2.复制二叉树

算法思路：

如果是空树，递归结束，否则执行以下操作：
• 申请一个新结点空间，复制根结点；
• 递归复制左子树；
• 递归复制右子树

void Copy(BiTree T,BiTree &NewT) 
{//复制一棵和T完全相同的二叉树
	if(T==NULL) //如果是空树， 递归结束
	{
        NewT=NULL; 
        return; 
	else 
	{
        NewT=new BiTNode; 
        NewT-> data=T->data; //复制根结点
        Copy (T-> lchild, NewT-> lchild); //递归复制左子树
        Copy (T-> rchild, NewT-> rchild); //递归复制右子树
	}
}

3.计算二叉树的深度

算法思路：

如果是空树，递归结束，深度为0, 否则执行以下操作：
• 递归计算左子树的深度记为m;
• 递归计算右子树的深度记为n;
• 如果 m 大于 n, 二叉树的深度为 m+1, 否则为 n+1。

int Depth(BiTree T) 
{//计算二叉树T的深度
	if(T==NULL) return 0; //如果是空树，深度为0, 递归结束
	else 
	{
        m=Depth(T->lchild); //递归计算左子树的深度记为m
        n=Depth(T->rchild) ; //递归计算右子树的深度记为n
        if{m>n) return{m+l); //二叉树的深度为m与n的较大者加1
        else return(n+l); 
	}
}

4.统计二叉树中结点的个数

int NodeCount(BiTree T) 
{//统计二叉树T中结点的个数
	if (T==NULL) return 0; //如果是空树，则结点个数为0, 递归结束
	else return NodeCount (T->lchild) +Node Count (T->rchild) +1;
	//否则结点个数为左子树的结点个数＋右子树的结点个数+1
}

线索二叉树

在上述二叉树中每个节点包含左右子树信息。但无法知道结点在任意序列中的前驱和后继，这种信息只有在遍历二叉树后得到，线索二叉树就是来解决该问题；由于有n个结点的二叉链表中必定有n+1个空链域，因此我们可以充分利用空链域来存放结点的前驱和后继信息。防止混淆，我们在二叉树的结点增加两个标志域。

若标志域是0表示的是指向该结点的左（右）孩子，标志域是1表示的是前驱（后继）

二叉树的二叉线索类型定义如下：

以这种结点结构构成的二叉链表作为二叉树的存储结构，叫做线索链表，其中指向结点前驱和后继的指针叫做线索；加上线索的二叉树称之为线索二叉树

线索二叉树的实质就是把二叉链表中的空指针改为指向前驱或者后继的线索，而前驱或后继的信息只有在遍历时才能得到。

以结点p为根的子树中序线索化

带头结点的二叉树中序线索化

遍历中序线索二叉树：

6.树和森林

树的存储结构

双亲表示法

该方法以一组连续的存储单元存储树的结点，每个结点除了数据域data外，还附有一个parent域用以指示双亲结点在数组中的位置。

C语言类型描述：

优点：找双亲方便

缺点：找孩子不方便

在这里插入图片描述

这种存储结构利用了每个结点（除根以外)只有唯一的双亲的性质。在这种存储结构下，求结点的双亲十分方便，也很容易求树的根，但求结点的孩子时需要遍历整个结构

孩子表示法

由于树中每个结点可能有多棵子树，则可用多重链表，即每个结点有多个指针域，其中每个指针指向一棵子树的根结点
在这里插入图片描述

把每个结点的孩子结点排列起来，看成是一个线性表，且以单链表做存储结构，则n个结点有n个孩子链表(叶子的孩子链表为空表)；而n个头指针又组成一个线性表，为了便于查找，可采用顺序存储结构。
1
2
3
4
5
6
7
8
9
typedef struct CTNode{
    int child;
    struct CTNode *next;}*ChildPtr;
typedef struct{
    TElemType data;
    ChildPtr firstchild;}CTBox;
typedef struct{
    CTBox nodes[MAX_TREE_SIZE];
    int n,r;}CTree;
找孩子方便，找父母麻烦

孩子兄弟表示法

又称二叉树表示法，或二叉链表表示法，即以二叉链表做树的存储结构；链表中结点的两个链域分别指向该节点的第一个孩子结点和该结点的下一个兄弟结点，分别命名为firstchild域和nextsibling域

树和森林的转换

从树的二叉链表表示的定义可知，任何一棵和树对应的二叉树，其根结点的右子树必空。若把森林中第二棵树的根结点看成是第一棵树的根结点的兄弟，则同样可导出森林和二叉树的对应关系
在这里插入图片描述

树与二叉树的转换（利用的就是把二叉树和树表示成相同的二叉链表）：

树转换成二叉树的思路（口诀：兄弟相连留长子）：

加线：在兄弟之间加一连线

抹线：对每个结点，除了其左孩子外，去除其与其孩子之间的关系

旋转：以树的根节点为轴心，将整树顺时针转 $45^{\circ}$

给定一棵树，可以找到唯一的一棵二叉树与之对应

二叉树转换成树思路：

加线：若p结点是双亲结点的左孩子，则将p的右孩子、右孩子的右孩子……沿分支找到的所有右孩子，都与p的双亲用线连接起来

抹线：抹掉原二叉树中双亲与右孩子之间的连线

调整：将结点按层次排列，形成树结构

森林与二叉树的转换：

森林转换成二叉树思路：（口诀：树变二叉根相连）

将各棵树分别转换成二叉树

将每棵树的根结点用线相连

以第一棵树根节点为二叉树的根，再以根节点为轴心，顺时针旋转，构成二叉树型结构

二叉树转换成森林思路：（口诀：去掉全部右孩线，孤立二叉再还原）

抹线：将二叉树中根节点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树

还原：将孤立的二叉树还原

树和森林的遍历：

树的遍历：

先根(次序)遍历：若树不空，则先访问根节点，然后依次先根遍历各棵子树

后根(次序)遍历：若树不空，则先依次后根遍历各棵子树，然后访问根节点

按层次遍历：若树不空，则自上而下自左至右访问树中每个结点

将森林看作三部分构成：

森林中第一棵树的根节点

森林中第一棵树的子树森林

森林中其它树构成的森林

森林的遍历：

先序遍历：若森林不空，则访问森林中第一棵树的根节点；然后先序遍历森林中第一棵树的子树森林；最后先序遍历森林中（除第一棵树之外）其余树构成的森林（即从左至右对森林中的每一棵树进行先根遍历）

中序遍历：若森林不空，则中序遍历森林中第一棵树的子树森林；然后访问森林中第一棵树的根节点；最后中序遍历森林中（除第一棵树之外）其余树构成的森林（依次从左至右对森林中的每一棵树进行后根遍历）