网络知识 娱乐 数据结构:树(Tree)【详解】

数据结构:树(Tree)【详解】

友情链接:数据结构专栏

目录

    • 【知识框架】
    • 一、树的基本概念
      • 1、树的定义
      • 2、基本术语
      • 3、树的性质
    • 二、树的存储结构
      • 1、双亲表示法
      • 2、孩子表示法
      • 3、孩子兄弟表示法
  • 二叉树
    • 一、二叉树的概念
      • 1、二叉树的定义
      • 2、几个特殊的二叉树
        • (1)斜树
        • (2)满二叉树
        • (3)完全二叉树
        • (4)二叉排序树
        • (5)平衡二叉树
      • 3、二叉树的性质
      • 4、二叉树的存储结构
        • (1)顺序存储结构
        • (2)链式存储结构
    • 二、遍历二叉树
      • 1、先序遍历
      • 2、中序遍历
      • 3、后序遍历
      • 4、递归算法和非递归算法的转换
        • (1)中序遍历的非递归算法
        • (2)先序遍历的非递归算法
        • (3)后序遍历的非递归算法
      • 5、层次遍历
      • 6、由遍历序列构造二叉树
    • 三、线索二叉树
      • 1、线索二叉树原理
      • 2、线索二叉树的结构实现
      • 3、二叉树的线索化
        • (1)中序线索二叉树
        • (2)先序和后序线索二叉树
    • 四、树、森林与二叉树的转化
      • 1、树转换为二叉树
      • 2、森林转化为二叉树
    • 五、树和森林的遍历
      • 1、树的遍历
      • 2、森林的遍历
  • 树与二叉树的应用
    • 一、二叉排序树
      • 1、定义
      • 2、二叉排序树的常见操作
        • (1)查找操作
        • (2)插入操作
        • (3)删除操作
      • 3、小结(引申出平衡二叉树)
    • 二、平衡二叉树
      • 1、定义
      • 2、平衡二叉树的查找
      • 3、平衡二叉树的插入
    • 三、哈夫曼树和哈夫曼编码
      • 1、哈夫曼树的定义和原理
      • 2、哈夫曼树的构造
      • 3、哈夫曼编码
  • 附录
    • 上文链接
    • 下文链接
    • 专栏
    • 参考资料

【知识框架】

在这里插入图片描述

一、树的基本概念

1、树的定义

树是n(n>=0)个结点的有限集。当n = 0时,称为空树。在任意一棵非空树中应满足:

  1. 有且仅有一个特定的称为根的结点。
  2. 当n>1时,其余节点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm,其中每个集合本身又是一棵树,并且称为根的子树。

显然,树的定义是递归的,即在树的定义中又用到了自身,树是一种递归的数据结构。树作为一种逻辑结构,同时也是一种分层结构,具有以下两个特点:

  1. 树的根结点没有前驱,除根结点外的所有结点有且只有一个前驱。
  2. 树中所有结点可以有零个或多个后继。

因此n个结点的树中有n-1条边。

2、基本术语

下面结合图示来说明一下树的一些基本术语和概念。
在这里插入图片描述

  1. 考虑结点K。根A到结点K的唯一路径上的任意结点,称为结点K的祖先。如结点B是结点K的祖先,而结点K是结点B的子孙。路径上最接近结点K的结点E称为K的双亲,而K为结点E的孩子。根A是树中唯一没有双亲的结点。有相同双亲的结点称为兄弟,如结点K和结点L有相同的双亲E,即K和L为兄弟。
  2. 树中一个结点的孩子个数称为该结点的度,树中结点的最大度数称为树的度。如结点B的度为2,结点D的度为3,树的度为3。
  3. 度大于0的结点称为分支结点(又称非终端结点);度为0(没有子女结点)的结点称为叶子结点(又称终端结点)。在分支结点中,每个结点的分支数就是该结点的度。
  4. 结点的深度、高度和层次。
    结点的层次从树根开始定义,根结点为第1层,它的子结点为第2层,以此类推。双亲在同一层的结点互为堂兄弟,图中结点G与E,F,H,I,J互为堂兄弟。
    结点的深度是从根结点开始自顶向下逐层累加的。
    结点的高度是从叶结点开始自底向上逐层累加的。
    树的高度(或深度)是树中结点的最大层数。图中树的高度为4。
  5. 有序树和无序树。树中结点的各子树从左到右是有次序的,不能互换,称该树为有序树,否则称为无序树。假设图为有序树,若将子结点位置互换,则变成一棵不同的树。
  6. 路径和路径长度。树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的,而路径长度是路径上所经过的边的个数。
    注意:由于树中的分支是有向的,即从双亲指向孩子,所以树中的路径是从上向下的,同一双亲的两个孩子之间不存在路径。
  7. 森林。森林是m (m≥0)棵互不相交的树的集合。森林的概念与树的概念十分相近,因为只要把树的根结点删去就成了森林。反之,只要给m棵独立的树加上一个结点,并把这m棵树作为该结点的子树,则森林就变成了树。

注意:上述概念无须刻意记忆, 根据实例理解即可。

3、树的性质

树具有如下最基本的性质:

  1. 树中的结点数等于所有结点的度数加1.
  2. 度为 m m m的树中第 i i i层上至多有 m i − 1 m^{i-1} mi1个结点( i > = 1 i>=1 i>=1
  3. 高度为 h h h m m m叉树至多有 ( m h − 1 ) / ( m − 1 ) (m^h-1)/(m-1) (mh1)/(m1)个结点。
  4. 具有 n n n个结点的 m m m叉树的最小高度为 [ l o g m ( n ( m − 1 ) + 1 ) ] [log_m(n(m-1)+1)] [logm(n(m1)+1)]

二、树的存储结构

在介绍以下三种存储结构的过程中,我们都以下面这个树为例子。
在这里插入图片描述

1、双亲表示法

我们假设以一组连续空间存储树的结点,同时在每个结点中,附设一个指示器指示其双亲结点到链表中的位置。也就是说,每个结点除了知道自已是谁以外,还知道它的双亲在哪里。
在这里插入图片描述
其中data是数据域,存储结点的数据信息。而parent是指针域,存储该结点的双亲在数组中的下标。
以下是我们的双亲表示法的结点结构定义代码。

/*树的双亲表示法结点结构定义*/
#define MAX_TREE_SIZE 100
typedef int TElemType;	//树结点的数据类型,目前暂定为整型
/*结点结构*/
typedef struct PTNode{
	TElemType data;	//结点数据
	int parent;	//双亲位置
}PTNode;
/*树结构*/
typedef struct{
	PTNode nodes[MAX_TREE_SIZE];	//结点数组
	int r, n;	//根的位置和结点数
}PTree;

这样的存储结构,我们可以根据结点的parent 指针很容易找到它的双亲结点,所用的时间复杂度为0(1),直到parent为-1时,表示找到了树结点的根。可如果我们要知道结点的孩子是什么,对不起,请遍历整个结构才行。

2、孩子表示法

具体办法是,把每个结点的孩子结点排列起来,以单链表作存储结构,则n个结点有n个孩子链表,如果是叶子结点则此单链表为空。然后n个头指针又组成-一个线性表,采用顺序存储结构,存放进一个一维数组中,如图所示。
在这里插入图片描述
为此,设计两种结点结构,一个是孩子链表的孩子结点。
在这里插入图片描述
其中child是数据域,用来存储某个结点在表头数组中的下标。next 是指针域,用来存储指向某结点的下一个孩子结点的指针。

另一个是表头数组的表头结点。
在这里插入图片描述
其中data是数据域,存储某结点的数据信息。firstchild 是头指针域,存储该结点的孩子链表的头指针。

以下是我们的孩子表示法的结构定义代码。

/*树的孩子表示法结构定义*/
#define MAX_TREE_SIZE 100
/*孩子结点*/
typedef struct CTNode{
	int child;
	struct CTNode *next;
}*ChildPtr;
/*表头结点*/
typedef struct{
	TElemType data;
	ChildPtr firstchild;
}CTBox;
/*树结构*/
typedef struct{
	CTBox nodes[MAX_TREE_SIZE];	//结点数组
	int r, n;	//根的位置和结点数
}

这样的结构对于我们要查找某个结点的某个孩子,或者找某个结点的兄弟,只需要查找这个结点的孩子单链表即可。对于遍历整棵树也是很方便的,对头结点的数组循环即可。
但是,这也存在着问题,我如何知道某个结点的双亲是谁呢?比较麻烦,需要整棵树遍历才行,难道就不可以把双亲表示法和孩子表示法综合一下吗? 当然是可以,这个读者可自己尝试结合一下,在次不做赘述。

3、孩子兄弟表示法

刚才我们分别从双亲的角度和从孩子的角度研究树的存储结构,如果我们从树结点的兄弟的角度又会如何呢?当然,对于树这样的层级结构来说,只研究结点的兄弟是不行的,我们观察后发现,任意一棵树, 它的结点的第一个孩子如果存在就是唯一的,它的右兄弟如果存在也是唯一的。 因此,我们设置两个指针,分别指向该结点的第一个孩子和此结点的右兄弟
结点的结构如下:
在这里插入图片描述
其中data是数据域,firstchild 为指针域,存储该结点的第一个孩子结点的存储地址,rightsib 是指针域,存储该结点的右兄弟结点的存储地址。
这种表示法,给查找某个结点的某个孩子带来了方便。
结构定义代码如下。

/*树的孩子兄弟表示法结构定义*/
typedef struct CSNode{
	TElemtype data;
	struct CSNode *firstchild, *rightsib;
} CSNode, *CSTree;

于是通过这种结构,我们就把原来的树变成了这个样子:
在这里插入图片描述

这不就是个二叉树么?
没错,其实这个表示法的最大好处就是它把一棵复杂的树变成了一棵二叉树
接下来,我们详细介绍二叉树。

二叉树

一、二叉树的概念

1、二叉树的定义

二叉树是另一种树形结构,其特点是每个结点至多只有两棵子树( 即二叉树中不存在度大于2的结点),并且二叉树的子树有左右之分,其次序不能任意颠倒。
与树相似,二叉树也以递归的形式定义。二叉树是n (n≥0) 个结点的有限集合:

  1. 或者为空二叉树,即n=0。
  2. 或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。

二叉树是有序树,若将其左、右子树颠倒,则成为另一棵不同的二叉树。即使树中结点只有一棵子树,也要区分它是左子树还是右子树。二叉树的5种基本形态如图所示。
在这里插入图片描述

2、几个特殊的二叉树

(1)斜树

所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树。

(2)满二叉树

一棵高度为 h h h,且含有 2 h − 1 2^h-1 2h1个结点的二叉树称为满二叉树,即树中的每层都含有最多的结点。满二叉树的叶子结点都集中在二叉树的最下一层,并且除叶子结点之外的每个结点度数均为 2 2 2。可以对满二叉树按层序编号:约定编号从根结点(根结点编号为 1 1 1)起,自上而下,自左向右。这样,每个结点对应一个编号,对于编号为i的结点,若有双亲,则其双亲为 i / 2 i/2 i/2,若有左孩子,则左孩子为 2 i 2i 2i;若有右孩子,则右孩子为 2 i + 1 2i+1 2i+1
在这里插入图片描述

(3)完全二叉树

高度为 h h h、有 n n n个结点的二叉树,当且仅当其每个结点都与高度为 h h h的满二叉树中编号为1~n的结点一一对应时,称为完全二叉树,如图所示。其特点如下:
在这里插入图片描述

  1. i ≤ n / 2 i≤n/2 in/2, 则结点 i i i为分支结点,否则为叶子结点。
  2. 叶子结点只可能在层次最大的两层上出现。对于最大层次中的叶子结点,都依次排列在该层最左边的位置上。
  3. 若有度为 1 1 1的结点,则只可能有一个,且该结点只有左孩子而无右孩子(重要特征)。
  4. 按层序编号后,一旦出现某结点(编号为 i i i)为叶子结点或只有左孩子,则编号大于 i i i的结点均为叶子结点。
  5. n n n为奇数,则每个分支结点都有左孩子和右孩子;若 n n n为偶数,则编号最大的分支结点(编号为 n / 2 n/2 n/2)只有左孩子,没有右孩子,其余分支结点左、右孩子都有。

(4)二叉排序树

左子树上所有结点的关键字均小于根结点的关键字;右子树上的所有结点的关键字均大于根结点的关键字;左子树和右子树又各是一棵二叉排序树。

(5)平衡二叉树

树上任一结点的左子树和右子树的深度之差不超过1。

3、二叉树的性质

  1. 任意一棵树,若结点数量为 n n n,则边的数量为 n − 1 n-1 n1
  2. 非空二叉树上的叶子结点数等于度为 2 2 2的结点数加 1 1 1,即 n o = n 2 + 1 n_o=n_2+ 1 no=n2+1
  3. 非空二叉树上第 k k k层上至多有 2 k − 1 2^{k-1} 2k1个结点 ( k ≥ 1 ) (k≥1) (k1)
  4. 高度为 h h h的二叉树至多有 2 h − 1 2^h-1 2h1个结点 ( h ≥ 1 ) (h≥1) (h1)
  5. 对完全二叉树按从上到下、从左到右的顺序依次编号 1 , 2.. ∗ , n 1,2..*,n 1,2..,n,则有以下关系:
    • i > 1 i>1 i>1时,结点 i i i的双亲的编号为 i / 2 i/2 i/2,即当 i i i为偶数时, 它是双亲的左孩子;当i为奇数时,它是双亲的右孩子。
    • 2 i ≤ n 2i≤n 2in时,结点 i i i的左孩子编号为 2 i 2i 2i, 否则无左孩子。
    • 2 i + 1 ≤ n 2i+1≤n 2i+1n时,结点 i i i的右孩子编号为 2 i + 1 2i+1 2i+1,否则无右孩子。
    • 结点 i i i所在层次(深度)为 { l o g 2 i } + 1 {log_2i}+ 1 {log2i}+1
  6. 具有 n n n ( n > 0 ) (n>0) (n>0)结点的完全二叉树的高度为 { l o g 2 n } + 1 {log_2n}+1 {log2n}+1

4、二叉树的存储结构

(1)顺序存储结构

二叉树的顺序存储是指用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素,即将完全二叉树上编号为 i i i的结点元素存储在一维数组下标为 i − 1 i-1 i1的分量中。
依据二叉树的性质,完全二叉树和满二叉树采用顺序存储比较合适,树中结点的序号可以唯一地反映结点之间的逻辑关系,这样既能最大可能地节省存储空间,又能利用数组元素的下标值确定结点在二叉树中的位置,以及结点之间的关系。
但对于一般的二叉树,为了让数组下标能反映二叉树中结点之间的逻辑关系,只能添加一些并不存在的空结点,让其每个结点与完全二叉树上的结点相对照,再存储到一维数组的相应分量中。然而,在最坏情况下,一个高度为 h h h且只有 h h h个结点的单支树却需要占据近 2 h − 1 2h-1 2h1个存储单元。二叉树的顺序存储结构如图所示,其中0表示并不存在的空结点。
在这里插入图片描述

(2)链式存储结构

既然顺序存储适用性不强,我们就要考虑链式存储结构。二叉树每个结点最多有两个孩子,所以为它设计一个数据域和两个指针域是比较自然的想法,我们称这样的链表叫做二叉链表
在这里插入图片描述
其中data是数据域,lchild 和rchild都是指针域,分别存放指向左孩子和右孩子的指针。
以下是我们的二叉链表的结点结构定义代码。

/*二叉树的二叉链表结点构造定义*/
/*结点结构*/
typedef struct BiTNode{
	TElemType data;	//结点数据
	struct BiTNode *lchild, *rchild;	//左右孩子指针
} BiTNode, *BiTree;

在这里插入图片描述
容易验证,在含有 n n n个结点的二叉链表中,含有 n + 1 n + 1 n+1个空链域


二、遍历二叉树

二叉树的遍历( traversing binary tree )是指从根结点出发,按照某种次序依次访问二叉树中所有结点,使得每个结点被访问一次且仅被访问一次。

1、先序遍历

先序遍历(PreOrder) 的操作过程如下:
若二叉树为空,则什么也不做,否则,
1)访问根结点;
2)先序遍历左子树;
3)先序遍历右子树。

在这里插入图片描述
对应的递归算法如下:

void PreOrder(BiTree T){
	if