0

化解数据结构----树与二叉树 知识梳理 + 习题详解

 2 years ago
source link: https://blog.51cto.com/u_15492594/5544067
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

📢📢📢📣📣📣
🌻🌻🌻Hello，大家好我叫是Dream呀，一个有趣的Python博主，多多关照😜😜😜
💕 入门须知：这片乐园从不缺乏天才，努力才是你的最终入场券！🚀🚀🚀
💓最后，愿我们都能在看不到的地方闪闪发光，一起加油进步🍺🍺🍺
🍉🍉🍉“一万次悲伤，依然会有Dream，我一直在最温暖的地方等你”，唱的就是我！哈哈哈~🌈🌈🌈
🌟🌟🌟✨✨✨

化解数据结构----树与二叉树 知识梳理 + 习题详解_结点

🔍树与二叉树 知识梳理 + 习题详解

一、树🔍

1.基本定义

🎯 树：是N(N≥0)个结点的有限集合
N=0时，称为空树，这是一种特殊情况。在任意一棵非空树中应满足：
1.有且仅有一个特定的称为根的结点；😎😎😎
2.当N>1时，又会从根结点分出若干个结点，这些节点又构成了若干个树，这些树称为根结点的子树。😎😎😎

2.基本术语

  • 结点：根的数据元素
  • 结点的度：结点挂接的子树数
  • 结点的层次：从根到该结点的层数
  • 终端结点：即度为0的节点，即叶子
  • 分支结点：度不为0的结点（内部结点）
  • 树的度：所有结点中的最大值
  • 树的深度（高度）：所有结点中的最大层数，即我们所说的高度

🎯 树的定义是递归的，是一种递归的数据结构。
树作为一种逻辑结构，同时也是一种分层结构，具有以下两个特点：
1.树的根结点没有前驱结点，除根结点之外的所有结点有且仅有一个前驱结点。
2.树中所有结点可以有零个或者多个后继结点。
🍉 🍉 🍉 n个结点的树中最多只有n-1条边。

3.实例分析树

化解数据结构----树与二叉树 知识梳理 + 习题详解_二叉树_02

3.1祖先节点&双亲节点：

💌根结点A到K的唯一路径上的任意结点，称为K的祖先结点。 如结点B是K的祖先节点，K是B的子孙结点。
🍉 🍉 🍉 路径上最接近K的结点E称为K的双亲结点，K是E的孩子结点。

3.2兄弟节点：

💎根A是树中唯一没有双亲的结点。有相同双亲的结点称为兄弟节点，如K和L有相同的双亲结点E，即K和L是兄弟结点。

3.3结点的度&树的度：

💎树中一个结点的子结点个数称为该结点的度，树中结点最大度数称为树的度。 如B的度为2，但是D的度为3，所以该树的度为3.（简单来说，就是结点的度中最大的值就是树的度）

3.4分支结点&叶子结点

💎度大于0的结点称为分支结点（又称为非终端结点）；度为0（没有子女结点）的结点称为叶子结点（又称终端结点）。在分支结点中，每个结点的分支数就是该节点的度。

3.5结点的深度、高度、层次

💎结点的深度是从根节点开始自顶向下逐层累加的。
💎结点的高度是从叶节点开始自底向上逐层累加的。
💎结点的层次从树根开始定义，根节点为第一层（有些教材将根节点定义为第0层），它的子结点为第2层，以此类推。

4.有序树和无序树

💎有序树：树中结点的子树从左到右是有次序的，不能交换。有序树中，一个结点其子结点从左到右顺序出现是有关联的。反之称为无序树。在上图中，如果将子结点的位置互换，则变为一棵不同的树。

5.路径和路径长度

💎树中两个结点之间的路径是由这两个节点之间所经过的结点序列构成的，而路径长度是路径上所经过的边的个数。A和K的路径长度为3.路径为B，E。

💎森林是m棵互不相交的树的集合。森林的概念和树的概念十分相近，因为只要把树的根节点删掉之后就变成了森林。反之，只要给n棵独立的树加上一个结点，并且把这n棵树作为该结点的子树，那么森林就变成了树。

7.树的基本性质（必看）

🚀1.树中结点数等于所有结点的度数+1（+1加的是根结点）

🚀2.度为m的树中第i层上至多有m^(i - 1)个结点（i >=1）

化解数据结构----树与二叉树 知识梳理 + 习题详解_结点_03

🚀3.高度为h的m叉树至多有（m^h - 1）/(m - 1)个结点。

化解数据结构----树与二叉树 知识梳理 + 习题详解_二叉树_04

🚀4.具有n个结点的m次树的最小高度为logm(n(m - 1) + 1)。

化解数据结构----树与二叉树 知识梳理 + 习题详解_二叉树_05

二、二叉树🔍

💌定义：把满足以下两个条件的树型结构叫做二叉树（Binary Tree）：
（1） 每个结点的度都不大于 2；
（2） 每个结点的孩子结点次序不能任意颠倒。
💌由此定义可看出，一个二叉树中的每个结点只能含有 0、1 或 2 个孩子，而且每个孩子有左右之分。位于左边的孩子叫做左孩子，位于右边的孩子叫做右孩子。

2.二叉树的五种形态

🍻图（a）所示为一棵空的二叉树；
🍻图（b）所示为一棵只有根结点的二叉树；
🍻图（c）所示为一 棵只有左子树的二叉树（左子树仍是一棵二叉树）；
🍻图（d）所示为左、右子树均非空的二叉树（左、右子树均为二叉树）；
🍻图（e）所示为一棵只有右子树的二叉树（右子树也是一棵二叉树）。二叉树也是树，故前面所介绍的有关树的术语都适用于二叉树。

化解数据结构----树与二叉树 知识梳理 + 习题详解_子树_06

3.满二叉树&完全二叉树&非完全二叉树

💌满二叉树： 深度为 k 且有 2^k -1 个结点的二叉树。在满二叉树中，每层结点都是满的， 即每层结点都具有最大结点数。如下图(a)所示的二叉树即为一棵满二叉树。
💌满二叉树的顺序表示，即从二叉树的根开始，层间从上到下，层内从左到右，逐层进行 编号（1，2，··· ，n）。例如下图(a)所示的满二叉树的顺序表示为**(1，2，3，4，5，6，7，8， 9，10，11，12，13，14，15)。**

💌完全二叉树: 深度为 k，结点数为 n 的二叉树，如果其结点 1～n 的位置序号分别与满 二叉树的结点 1～n 的位置序号一一对应，则为完全二叉树，如下图(b)所示。
可见:
满二叉树必为完全二叉树，而完全二叉树不一定是满二叉树。
一棵完全二叉树有5000个结点，可以计算出其叶结点的个数是（ 2500）。

非完全二叉树： 序号不和满二叉树的序号一一对应。如下图（c）和（d）

化解数据结构----树与二叉树 知识梳理 + 习题详解_结点_07

4. 二叉树的基本操作

二叉树（Binary Tree），以下我们简称为bt💌💌💌
🎉⑴ Initiate（bt）：将 bt 初始化为空二叉树。
🎉⑵ Create(bt)：创建一棵非空二叉树 bt。
🎉⑶ Destory（bt）： 销毁二叉树 bt。
🎉⑷ Empty（bt）： 若 bt 为空，则返回 TRUE，否则返回 FALSE。
🎉⑸ Root(bt)： 求二叉树 bt 的根结点。若 bt 为空二叉树，则函数返回“空”
🎉⑹ Parent（bt，x）：求双亲函数。求二叉树 bt 中结点 x 的双亲结点。若结点 x 是二叉 树的根结点或二叉树 bt 中无结点 x，则返回“空” 。
🎉⑺ LeftChild（bt，x）：求左孩子。返回结点 x 的左孩子，若结点 x 无左孩子或 x 不在 bt 中，则返回“空”。
🎉⑻ RightChild（bt，x）：求右孩子。返回结点 x 的右孩子，若结点 x 无右孩子或 x 不 在 bt 中，则返回“空” 。
🎉⑼ Traverse（bt）: 遍历操作。按某个次序依次访问二叉树中每个结点一次且仅一次。
🎉⑽ Clear（bt）：清除操作。将二叉树 bt 置为空树。

4.二叉树的存储结构

4.1 顺序存储

按满二叉树的结点层次编号，依次存放二叉树中的数据元素。
特点：
结点间关系蕴含在其存储位置中
浪费空间，适于存满二叉树和完全二叉树

4.2 链式存储

对于任意的二叉树来说，每个结点只有两个孩子，一个双亲结点。可以设计每个结点至少包 括三个域：数据域、左孩子域和右孩子域，如下图所示。

化解数据结构----树与二叉树 知识梳理 + 习题详解_子树_08

其中，LChild 域指向该结点的左孩子，Data 域记录该结点的信息，RChild 域指向该结点的 右孩子。
也就是说，在n个结点的二叉链表中，必定有2n个链域，除了根结点外，每个结点有且仅有一个双亲，所以只会有n-1个结点的链域存放指针，故空指针的个数为n+1

化解数据结构----树与二叉树 知识梳理 + 习题详解_子树_09

C语言实现：

typedef struct Node 
{ 
	DataType data; 
	struct Node * LChild; 
	struct Node * RChild; 
}BiTNode, *BiTree;`

5.二叉树的性质

🏆性质 1:在二叉树的第 i 层上至多有 2^(i-1)个结点(i≥1)。

化解数据结构----树与二叉树 知识梳理 + 习题详解_子树_10

🏆性质 2:深度为 k 的二叉树至多有 2^k-1 个结点（k≥1）
(类比上面树的，就是等比数列求和)

化解数据结构----树与二叉树 知识梳理 + 习题详解_二叉树_04

🏆性质 3:对任意一棵二叉树 T，若终端结点数为 n0，而其度数为 2 的结点数为 n2，则 n0= n2+1

化解数据结构----树与二叉树 知识梳理 + 习题详解_二叉树_12

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

化解数据结构----树与二叉树 知识梳理 + 习题详解_二叉树_13

🏆性质 5: 对于具有 n 个结点的完全二叉树，如果按照从上到下和从左到右的顺序对二叉树中的所有结点从 1 开始顺序编号，则对于任意的序号为 i 的结点有：
（1）如 i=1，则序号为 i 的结点是根结点，无双亲结点；如 i>1，则序号为 i 的结点的 双亲结点序号为[2/i ]。
（2）如 2×i>n，则序号为 i 的结点无左孩子；如 2×i≤n，则序号为 i 的结点的左孩 子结点的序号为 2×i。
（3）如 2×i＋1>n，则序号为 i 的结点无右孩子；如 2×i＋1≤n，则序号为 i 的结点 的右孩子结点的序号为 2×i＋1。

化解数据结构----树与二叉树 知识梳理 + 习题详解_子树_14

三、树的遍历（二叉树）🔍

遍历定义：指按某条搜索路线遍访每个结点且不重复（又称周游）。

  • 先(前)序遍历: 先访问根结点,然后是左结点,然后是右结点。

  • 中序遍历: 先访问左结点,然后是根结点,然后是右结点。

  • 后序遍历: 先访问左结点,然后是右结点,然后是根结点。

    化解数据结构----树与二叉树 知识梳理 + 习题详解_二叉树_15

1.先序遍历

C实现代码：
递归写法：

void PreOrder(BitTree T)
{
    if(T!=NULL)
    {
        cout<<T->val<<"  ";
        PreOrder(T->l);
        PreOrder(T->r);
    }
}

非递归写法：

void PreOrder (BitTree T)
{
　　stack<BitTree>s;
　　BitTree p = T;
　　while(p || !s.empty)
　　{
　　　　if(p)
　　　　{
　　　　　　cout<<p->val<<"  ";
　　　　　　s.push(p);
　　　　　　p = p->l;
　　　　}else
　　　　{
　　　　　　p = s.top();
　　　　　　p = p->r;
　　　　　　p = p.pop();
　　　　}
　　}
}

2.中序遍历

C实现代码：

void InOrder(BitTree T)
{
    if(T!=NULL)
    {
        InOrder(T->l);
        printf("%d\n",T->val);
        InOrder(T->r)
    }
}

3.后序遍历

后序遍历的性质：对于一颗树，最后的那一个结点是根节点
C实现代码：

void PostOrder(BitTree T)
{
    if(T!=NULL)
    {
        PostOrder(T->l);
        PostOrder(T->r);
        printf("%d\n",T->val);
    }
}

4.二叉树的建立

void CreateBiTree(BiTree &T）{
	cin>>ch;
	if (ch==’#’)   
		T=NULL;  	//递归结束，建空树
	else {
	    T=new BiTNode;    
	    T-＞data=ch; 	//生成根结点
	    CreateBiTree(T-＞lchild);  //递归创建左子树
 	    CreateBiTree(T-＞rchild); //递归创建右子树
  }									
}

5.计算二叉树结点总数

如果是空树，则结点个数为0；
否则，结点个数为左子树的结点个数+右子树的结点个数再+1。

int NodeCount(BiTree T){
	if(T == NULL ) return 0;  			    
	else return NodeCount(T->lchild)+NodeCount(T->rchild)+1;
}

6.计算二叉树叶子结点总数

如果是空树，则叶子结点个数为0； 否则，为左子树的叶子结点个数+右子树的叶子结点个数。

int LeadCount(BiTree T){
 	if(T==NULL) 	//如果是空树返回0
		return 0;
	if (T->lchild == NULL && T->rchild == NULL)
		return 1; //如果是叶子结点返回1
	else return LeafCount(T->lchild) + LeafCount(T->rchild);
}

7.计算二叉树深度

如果是空树，则深度为0；
否则，递归计算左子树的深度记为m，递归计算右子树的深度记为n，二叉树的深度则为m与n的较大者加1。


int get_deep(tree *p){
    if(p == NULL)
        return 0;
    return max(deep(p->l),deep(p->r))+1;
}

8.线索二叉树

对于一个二叉树来说，其二叉链表表示形式中正好有两个指针域，一个左子树指针域，一个右子树指针域。并且对于一个有 n 个节点的二叉链表， 每个节点有指向左右孩子的两个指针域，所以共是 2n 个指针域。而 n 个节点的二叉树一共有 n-1 条分支数，也就是说，其实是存在 2n-(n-1) = n+1个空指针域。
们已经知道了，二叉树的遍历有四种方式：先序遍历、中序遍历、后序遍历、层序遍历。

那么根据遍历来进行线索化的方式也就有四种方式：先序线索化、中序线索化、后序线索化、层序线索化，其实严格意义上来说，除了遍历的顺序不同，其他的没什么太大的区别。对于线索化来将也是一样的。

所以，如果这个节点的左指针域是空的，那么就让其指向前驱，如果这个节点的右指针域为空，那么就让其指向后继， 所以，四种线索化的示意图可以表示为下图这样。(其中 红色线条 表示前驱、 蓝色线条 表示为后继，均称为 线索。)

化解数据结构----树与二叉树 知识梳理 + 习题详解_子树_16

 ops_request_misc=%257B%2522request%255Fid%2522%253A%2522165199698416781818796756%2522%252C%2522scm%2522%253A%252220140713.130102334…%2522%257D&request_id=165199698416781818796756&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2blogtop_positive~default-1-106551499-null-null.nonecase&utm_term=%E7%BA%BF%E7%B4%A2%E4%BA%8C%E5%8F%89%E6%A0%91&spm=1018.2226.3001.4450)

四、森林🔍

二叉树转森林：左指针指的是左孩子，右指针指的是兄弟，这样就避免了一颗多叉树需要像二叉树一样的每一个结点使用多个指针的情况了。

化解数据结构----树与二叉树 知识梳理 + 习题详解_子树_17
化解数据结构----树与二叉树 知识梳理 + 习题详解_结点_18

五、Huffman树🔍

哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。
所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的带权路径长度记为WPL=(W1L1+W2L2+W3L3+…+WnLn)，N个权值Wi(i=1,2,…n)构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li(i=1,2,…n)。可以证明哈夫曼树的WPL是最小的。

六 作业练习🔍

（1）把一棵树转换为二叉树后，这棵二叉树的形态是（ ）。

A．唯一的 Ｂ．有多种

C．有多种，但根结点都没有左孩子 Ｄ．有多种，但根结点都没有右孩子

解释：因为二叉树有左孩子、右孩子之分，故一棵树转换为二叉树后，这棵二叉树的形态是唯一的。

（2）由3个结点可以构造出多少种不同的二叉树？（ ）

A．2 B．3 C．4 D．5

（3）一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ）。

A．250 B． 500 C．254 D．501

解释：设度为0结点（叶子结点）个数为A，度为1的结点个数为B，度为2的结点个数为C，有A=C+1，A+B+C=1001，可得2C+B=1000，由完全二叉树的性质可得B=0或1，又因为C为整数，所以B=0，C=500，A=501，即有501个叶子结点。

（4）一个具有1025个结点的二叉树的高h为（ ）。

A．11 B．10 C．11至1025之间 D．10至1024之间

解释：若每层仅有一个结点，则树高h为1025；且其最小树高为 ëlog21025û + 1=11，即h在11至1025之间。

（5）深度为h的满m叉树的第k层有（ ）个结点。(1=<k=<h)

A．mk-1 B．mk-1 C．mh-1 D．mh-1

解释：深度为h的满m叉树共有mh-1个结点，第k层有mk-1个结点。

（6）利用二叉链表存储树，则根结点的右指针是（ ）。

A．指向最左孩子 B．指向最右孩子 C．空 D．非空

解释：利用二叉链表存储树时，右指针指向兄弟结点，因为根节点没有兄弟结点，故根节点的右指针指向空。

（7）对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用（ ）遍历实现编号。

A．先序 B. 中序 C. 后序 D. 从根开始按层次遍历

解释：根据题意可知按照先左孩子、再右孩子、最后双亲结点的顺序遍历二叉树，即后序遍历二叉树。

（8）若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用（ ）遍历方法最合适。

A．前序 B．中序 C．后序 D．按层次

解释：后续遍历和层次遍历均可实现左右子树的交换，不过层次遍历的实现消耗比后续大，后序遍历方法最合适。

（9）在下列存储形式中，（ ）不是树的存储形式？

A．双亲表示法 B．孩子链表表示法 C．孩子兄弟表示法 D．顺序存储表示法

解释：树的存储结构有三种：双亲表示法、孩子表示法、孩子兄弟表示法， 其中孩子兄弟表示法是常用的表示法，任意一棵树都能通过孩子兄弟表示法转换为二叉树进行存储。

（10）一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（ ）。

A．所有的结点均无左孩子 B．所有的结点均无右孩子

C．只有一个叶子结点 D．是任意一棵二叉树

解释：因为先序遍历结果是“中左右”，后序遍历结果是“左右中”，当没有左子树时，就是“中右”和“右中”；当没有右子树时，就是“中左”和“左中”。则所有的结点均无左孩子或所有的结点均无右孩子均可，所以A、B不能选，又所有的结点均无左孩子与所有的结点均无右孩子时，均只有一个叶子结点，故选C。

（11）设哈夫曼树中有199个结点，则该哈夫曼树中有（ ）个叶子结点。

A．99 B．100

C．101 D．102

解释：在哈夫曼树中没有度为1的结点，只有度为0（叶子结点）和度为2的结点。设叶子结点的个数为n0，度为2的结点的个数为n2，由二叉树的性质n0=n2+1，则总结点数n= n0+n2=2*n0-1，得到n0=100。

（12）若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则X的前驱为（ ）。

A．X的双亲 B．X的右子树中最左的结点

C．X的左子树中最右结点 D．X的左子树中最右叶结点

（13）引入二叉线索树的目的是（ ）。

A．加快查找结点的前驱或后继的速度 B．为了能在二叉树中方便的进行插入与删除

C．为了能方便的找到双亲 D．使二叉树的遍历结果唯一

（14）设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有（ ）个。

A．n−1 B．n C．n + 1 D．n + 2

（15）n（n≥2）个权值均不相同的字符构成哈夫曼树，关于该树的叙述中，错误的是（ ）。

A．该树一定是一棵完全二叉树

B．树中一定没有度为1的结点

C．树中两个权值最小的结点一定是兄弟结点

D．树中任一非叶结点的权值一定不小于下一层任一结点的权值

解释：哈夫曼树的构造过程是每次都选取权值最小的树作为左右子树构造一棵新的二叉树，所以树中一定没有度为1的结点、两个权值最小的结点一定是兄弟结点、任一非叶结点的权值一定不小于下一层任一结点的权值。

🌲🌲🌲 好啦，这就是今天要分享给大家的全部内容了
❤️❤️❤️如果你喜欢的话，就不要吝惜你的一键三连了~

化解数据结构----树与二叉树 知识梳理 + 习题详解_结点_19

化解数据结构----树与二叉树 知识梳理 + 习题详解_子树_20

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK