数据结构(七)---树

目录

一.树的基本概念

二.树的性质

三.二叉树

1.二叉树的基本概念

2.特殊的二叉树

(1)满二叉树

(2)完全二叉树

(3)二叉排序树

(4)平衡二叉树

3.二叉树的性质

4.完全二叉树的性质 

5.二叉树的存储结构

(1)顺序存储

(2)链式存储

6.二叉树的遍历

7.二叉树的层序遍历

8.由遍历序列构造二叉树

考法1:前序+中序遍历序列

考法2:后序+中序遍历序列

考法3:层序+中序遍历序列

9.线索二叉树

(1)线索二叉树的作用

(2)线索二叉树的存储结构

线索二叉树的定义:

中序线索化:

先序线索化:

后序线索化:

10.根据线索二叉树找前驱/后继

(1)中序线索二叉树

•找中序后继

•找中序前驱

(2)先序线索二叉树

•找先序后继

•找先序前驱

(3)后序线索二叉树

•找后序前驱

•找后序后继


如有错误,还望佬们指正!!💖💖💖

一.树的基本概念

1.空树:结点数为0的树

2.非空树:至少有一个结点的树

•有且仅有一个根节点

•没有后继的结点称为“叶子结点”(或终端结点)

•有后继的结点称为“分支结点”(或非终端结点)

•除了根节点外,任何一个结点都有且仅有一个前驱

•每个结点可以有0个或多个后继

•除了跟节点外,其余结点可以分为互不相交的有限集合,其中每个集合又是一棵树,并且称为根结点的子树

同理,子树也可以划分为多个互不相交的集合,所以树是一种递归定义的数据结构

结点之间的关系:

祖先结点:从该结点出发到根节点路径上所有的结点都是祖先结点。

例如上图,F的祖先结点为"父亲","爷爷"
子孙结点:从该结点出发,其所有的分支结点。

例如上图,“父亲”的子孙结点为:"你","F","K","L"
双亲结点(父节点):一个结点的直接前驱。

例如,“F”和“你”的父结点都是“父亲”
孩子结点:一个结点的直接后继。

例如,“父亲”的孩子结点是“F”和“你”
兄弟结点:“F”和“你”互为兄弟结点。

路径与路径长度:

路径是某个结点到达另一个结点的路径,只能从上往下,例如“爷爷”结点到"你"结点时有路径的,而"你"到"爷爷"结点是没有路径的。

路径长度就是经过了几条边:“爷爷”结点到"你"结点的路径长度为2

结点、树的属性描述:

结点的层次(深度)--从上往下数(默认从1开始)

例如,B的深度为2
结点的高度--从下往上数

例如,B的高度为3
树的高度(深度)--总共多少层

例如,上图树的高度为4
结点的度--有几个孩子(分支)

例如,D结点的度为3
树的度--各结点的度的最大值

例如,上图的树的度为3

有序树:从逻辑上看,树中结点的各子树从左至右是有次序的,不能互换。

无序树:从逻辑上看,树中结点的各子树从左至右是无次序的,可以互换

树和森林:

森林是m(m>=0)棵互不相交的树的集合。

二.树的性质

1.结点数=总度数+1

总的结点数等于各个结点的度数之和+1,由于根结点是没有前驱结点的,所以各个结点的度数相加后还需+1。

2.度为m的数与m叉树的区别

树的度--各结点的度的最大值
m叉树--每个结点最多只能有m个孩子的树

例如,度为3的树,表示这棵树中至少有一个结点的度数为3,而3叉树则规定了每个结点至多有3个孩子,就算所有结点度数都小于3,也是一个合法的三叉树,当然也可以有3叉空树。

所以对于一个度为m的树而言,其至少有m+1个结点。

总结如下:

3.度为 m 的树第 i 层至多有 m^{i-1} 个结点(i>=1)

如图,这是一棵度为3的树,第一层只能有根结点,由于树的度为3,所以他最多有3个孩子,也就是第二层最多为3,第二层的每个结点又最多各有3个孩子,以此类推:

m叉树第 i 层至多有 m^{i-1} 个结点(i>=1)

由于m叉树也规定了每一个结点至多有m个孩子,所以结论和度为m的树是一样的

4.高度为 h 的 m 叉树至多有 \frac{m^h-1}{m-1} 个结点。

将每一层至多的结点数相加即可。等比数列求和就可以得到\frac{m^h-1}{m-1}

5.高度为 h 的m叉树至少有 h 个结点

m叉树只规定了每个结点孩子数量的上限是多少,没有规定下限,所以高度为h的m叉树至少有h个结点。

而对于度为m的数而言,高度为h、度为m的树至少有 h+m-1 个结点。

度为m的树中,至少要保证一个结点的孩子结点的数量为m,所以度为m的树至少有h+m-1个结点

6.具有n个结点的m叉树的最小高度为\left \lceil log_{m}(n(m-1)+1) \right \rceil

整理一下得到:

m^h-1<n(m-1)+1\leq m^h

对三个部分分别取对数:

h-1< log_{m}(n(m-1)+1) \leq h

由于中间部分要大于h-1,所以h最小为

h= \left \lceil log_{m}(n(m-1)+1) \right \rceil

三.二叉树

1.二叉树的基本概念

二叉树是n(n>=0)个结点的有限集合:
①或者为空二叉树,即n=0。
②或者由一个根结点和两个互不相交的被称为根的左子树右子树组成。左子树和右子树又分别是一棵二叉树。

①每个结点至多只有两棵子树

②左右子树不能颠倒(二叉树是有序树)

注意二叉树和度为2的有序树的区别:度为2的有序树表示这棵树中至少有一个结点他的孩子结点有两个。二叉树则是每个结点最多只能有2个孩子结点。

二叉树的五种状态如下图所示:

2.特殊的二叉树
(1)满二叉树

一棵高度为h,且含有2^h-1个结点的二叉树。通俗来讲就是,除了最下面的叶子结点外,其他结点都有两个分支。

例如下图,第一层有1个结点,第二层有2个结点,第三层有4个结点,第四层有8个结点,高度为4的满二叉树,含有的结点个数就为:2^4-1=15个结点(等比数列求和)。

满二叉树的特点:

①只有最后一层有叶子结点

②不存在度为1的结点

③按层序从1开始编号,结点i的左孩子为2i,右孩子为2i+1;结点 i 的父节点为 \left \lfloor i/2 \right \rfloor (如果有的话)

(2)完全二叉树

当且仅当其每个结点都与高度为 h 的满二叉树中编号为 1~n 的结点一一对应时,称为完全二叉树。也就是说可以在满二叉树的基础上,将一些编号更大的结点去掉。

假若现在只去掉13号结点,那么按照层次的编号规则,7号结点的孩子结点编号分别为13,14,但是在满二叉树中,对应结点的编号为14,15,不能一一对应,所以这棵树不是完全二叉树。

所以如果某个结点只有一个孩子,那么一定是左孩子

:满二叉树是一种特殊的完全二叉树,但是完全二叉树未必是满二叉树。

完全二叉树的特点:

①只有最后两层可能有叶子结点。

②最多只有一个度为1的结点。
③按层序从1开始编号,结点i的左孩子为2i,右孩子为2i+1;结点 i 的父节点为 \left \lfloor i/2 \right \rfloor (如果有的话),这一点和满二叉树一样。

④总共有n个结点,i\leq \left \lfloor n/2 \right \rfloor为分支结点,i> \left \lfloor n/2 \right \rfloor为叶子结点。

(3)二叉排序树

二叉排序树。一棵二叉树或者是空二叉树,或者是具有如下性质的二叉树:

1.左子树上所有结点的关键字均小于根结点的关键字;

2.右子树上所有结点的关键字均大于根结点的关键字。

3.左子树和右子树又各是一棵二叉排序树。

例如想要插入新元素68,那么可以与结点依次比较,最终确定插入的位置:

① 68>19,与其右孩子进行比较,② 68>50,与其右孩子进行比较,③ 68>66,继续与其右孩子进行比较,④ 68<70,将其作为70的左孩子。

二叉排序树可用于元素的排序和搜索。

(4)平衡二叉树

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

例如下图,对于根结点而言,其左子树深度为2,右子树深度为3,那么对于根结点,满足平衡二叉树的条件。

同理,以66作为根节点的子树也满足这一条件。所有的结点都满足这一条件,那么这棵树是平衡二叉树。

而下图所示的二叉树,对于根结点而言,其左子树深度为1,右子树深度为6,深度之差超过1了,所以这棵树不是平衡二叉树。

对于平衡二叉树而言,其搜索效率是较高的。例如,寻找70结点,对于左边的平衡二叉树而言,只需要2步,对于右边的树而言,则需要6步。

3.二叉树的性质

(1)设非空二叉树中度为0、1和2的结点个数分别为n0、n1和n2,则n0=n2+1,即叶子结点比二分支结点多一个。

假设树中结点总数为n,则

①n=n0 + n1 + n2(二叉树中只可能有度为0,1,2的结点)

n=n_1+2n_2+1(树的结点树=总度数+1)

度为1的结点有n1个,度为2的结点有n2个,由于度为2的每个结点又有两个孩子结点所以为2n_2,再加上一个根结点:n=n_1+2n_2+1

② - ① 得到:n0=n2+1

可以用下面两个图验证一下:

(2)二叉树第 i 层至多有 2^{i-1} 个结点(i>=1),之前讲过m叉树第 i 层至多有 m^{i-1} 个结点(i>=1)

(3)高度为 h 的二叉树至多有 2^h-1 个结点( 满二叉树 ),之前讲过高度为h的m叉树至多有\frac{m^h-1}{m-1}个结点,把m=2,即可得到2^h-1

4.完全二叉树的性质 

(1)具有n个( n >0 )结点的完全二叉树的高度h为\left \lceil log_2(n+1) \right \rceil 或 \left \lfloor log_2n \right \rfloor+1

解法1

高为 h 的满二叉树共有 2^h-1 个结点

高为 h-1的满二叉树共有 2^{h-1}-1个结点

推出:2^{h-1}-1<n\leq 2^h-1

进一步地:2^{h-1}<n+1\leq 2^h

得到:h-1<log_2(n+1)\leq h

最后得到 :h=\left \lceil log_2(n+1) \right \rceil

解法2

高为 h-1的满二叉树共有 2^{h-1}-1个结点,完全二叉树要比这样的满二叉树至少多一个结点

也就是:2^{h-1}个结点

高为 h 的满二叉树共有 2^h-1 个结点,若在此基础上+1,这样的完全二叉树的高度为h+1,所以完全二叉树高度的范围:

2^{h-1}\leq n< 2^h

同时取对数:h-1\leq log_2n<h

刚好小于等于则:h-1=\left \lfloor log_2n \right \rfloor

最后得到:h=\left \lfloor log_2n \right \rfloor+1

同理,第i个结点所在层次为\left \lceil log_2(n+1) \right \rceil 或 \left \lfloor log_2n \right \rfloor+1

(2)对于完全二叉树,可以由结点数n推出度为0、1和2的结点个数为n0、n1和n2

完全二叉树最多只有一个度为1的结点,即:n1=0或1

二叉树中,n0=n2+1,那么n0+n2一定是奇数

若完全二叉树有 2k 个(偶数)个结点,则必有n1=1, n0=k,n2=k-1

若完全二叉树有 2k-1 个(奇数)个结点,则必有n1=0,n0=k,n2=k-1

总结:

5.二叉树的存储结构
(1)顺序存储
#define MaxSize 100
struct TreeNode{ElemType value;    //结点中的数据元素bool isEmpty;    //结点是否为空
};TreeNode t[MaxSize];
//定义一个长度为 MaxSize 的数组t,按照从上至下、从左至右的顺序依次存储完全二叉树中的各个结点

如下图所示:可以让第一个位置空缺,保证数组下标和结点编号一致。由于使用静态数组存储结点,所以二叉树中的结点数量是有限的。

根据完全二叉树的性质:

•i 的左孩子为2i

•i 的右孩子为2i+1

•i 的父节点为\left \lfloor i+2 \right \rfloor

•i 所在的层次为\left \lceil log_2(n+1) \right \rceil 或 \left \lfloor log_2n \right \rfloor+1

若完全二叉树中共有n个结点,则:

•判断 i是否有左孩子:2i<=n,因为i的左孩子为2i,若2i存在(2i<=n),则说明有左孩子

•判断 i是否有右孩子:与左孩子同理,判断2i+1<=n

•判断 i是否有叶子/分支结点:判断 i>\left \lfloor n/2 \right \rfloor

对于普通二叉树而言,结点的编号不能反映出结点的逻辑关系,所以可以把二叉树的结点编号与完全二叉树对应起来。并放到数组的相应位置中。

对于普通二叉树,就不能采用之前完全二叉树中判断是否有左右孩子 或 是否是叶子结点的方法了: 只能通过isEmpty字段判断,例如5号结点的左孩子为10(2i),那么就检查10的isEmpty字段,若isEmpty为true,那么5号没有左孩子。

采用顺序存储的方式存储二叉树,可能导致大量空间的浪费。例如,最坏的情况:高度为h且只有 h 个结点的单支树 (所有结点只有右孩子),也至少需要2^h-1个存储单元。

所以二叉树的顺序存储结构,只适合存储完全二叉树。

(2)链式存储
//二叉树的结点
typedef struct BiTNode{ElemType data;struct BiTNode *lchild,*rchild;     //数据域
}BiTNode, *BiTree;    //左,右孩子指针

 

由于每个结点有2个指针域,那么n个结点就会对应2n个指针域,除了头结点外,其他结点都有前驱结点,所以n个结点的二叉链表共有 n+1(2n-(n-1)) 个空链域。这些空链域可以用于构造线索二叉树。

•定义一个二叉树:

struct ElemType{int value;
};typedef struct BiTNode{ElemType data;struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;// 定义一棵空树
BiTree root = NULL;// 插入根节点
root = (BiTree)malloc(sizeof(BiTNode));
root->data.value = 0; // 假设根节点的值为 0,你可以根据实际情况修改
root->lchild = root->rchild = NULL;// 插入新结点
BiTNode *p = (BiTNode *)malloc(sizeof(BiTNode));
p->data.value = 2;
p->lchild = NULL;
p->rchild = NULL;
root->lchild = p;    // 作为根节点的左孩子

对于二叉树的链式存储而言,找到指定结点p的左/右孩子非常容易,但是找到其父结点,则只能从根开始遍历寻找。如果需要经常访问某结点的父节点,可以再创建一个父节点指针:

//三叉链表
typedef struct BiTNode{ElemType data;    //数据域struct BiTNode *lchild,*rchild;    //左、右孩子指针struct BiTNode *parent;    //父节点指针
}BiTNode,*BiTree;

6.二叉树的遍历

二叉树的遍历规则

先序/根遍历:根左右(NLR)

中序/根遍历:左根右(LNR)

后序/根遍历:左右根(LRN)

例如下面这棵二叉树,其先序,中序,后序遍历分别为: 

对于做题方法,我之前有写过一篇:http://t.csdnimg.cn/kQQIg 

对于算数表达式的“分析树”,进行先序遍历,中序遍历和后序遍历的结果分别对应的是这个算数序列的前缀表达式,中缀表达式和后缀表达式。

先序遍历,中序遍历和后序遍历代码实现如下:

struct ElemType{int value;
};typedef struct BiTNode{ElemType data;struct BiTNode *lchild,*rchild;    
}BiTNode,*BiTree;void visit(BiTree node) {printf("%d ", node->data.value);
}//先序遍历
void PreOrder(BiTree T){if(T!=NULL){visit(T);    //访问根结点PreOrder(T->lchild);    //递归遍历左子树PreOrder(T->rchild);    //递归遍历右子树}
}//中序遍历
void PreOrder(BiTree T){if(T!=NULL){InOrder(T->lchild);    //递归遍历左子树visit(T);    //访问根结点InOrder(T->rchild);    //递归遍历右子树}
}//后序遍历
void PreOrder(BiTree T){if(T!=NULL){PostOrder(T->lchild);    //递归遍历左子树PostOrder(T->rchild);    //递归遍历右子树visit(T);    //访问根结点}
}

这样递归实现的算法,空间复杂度(h+1),h指的是2叉树的高度,+1是因为最后一层的叶子结点下面还有空结点需要处理,也就是说空结点的信息也需要压入栈中进行处理。

如图所示,从根节点出发,一条路如果左边还有没走的路,优先往左边走,走到路的尽头(空结点)就往回走如果左边没路了,就往右边走,如果左、右都没路了,则往上面走。

可以观察到,从根结点出发的路径,会依次路过每个结点3次:

若第1次路过时就访问访问结点,则为先序遍历上图的灰色字表示访问顺序)。

若第2次路过时访问访问结点,则为中序遍历

若在第3次路过时访问结点,则为后序遍历

以上也是一种求遍历序列的方法,但是不如上面讲的方法简单。

求树的深度:

int treeDepth(BiTree T){if(T == NULL){return 0;}else {int l=treeDepth(T->lchild);int r=treeDepth(T->rchild);//树的深度=Max(左子树深度,右子树深度)+1return l>r ? l+1 : r+1;}
}

7.二叉树的层序遍历

二叉树的层序队列,需要一个队列辅助

① 根结点入队。

② 若队列非空,则队头结点出队,访问该结点,并将其左、右孩子插入队尾(如果有的话)。

③ 重复②直至队列为空。

以下图为例:

① 根结点入队:

② 队列非空,队头结点出队,访问该结点,并将其左、右孩子插入队尾:

③ B出队,访问B,并将B结点的左右孩子入队:

④ 不断重复上面步骤,直至队列为空:

代码如下:

//二叉树的结点(链式存储)
typedef struct BiTNode{char data;struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;//链式队列结点
typedef struct LinkNode{BiTNode *data;    //存指针struct LinkNode *next;
}LinkNode;typedef struct{    LinkNode *front,*rear;    //队头队尾
}LinkQueue;//层序遍历
void LevelOrder(BiTree T){LinkQueue Q;InitQueue(Q);    //初始化辅助队列BiTree p;    EnQueue(Q,T);    //根结点入队while(!IsEmpty(Q)){    //队列不为空则循环DeQueue(Q,p);visit(p);    //访问出队结点if(p->lchild!=NULL)EnQueue(Q,p->lchild);    //左孩子入队if(p->rchild!=NULL)    EnQueue(Q,p->rchild);    //右孩子入队}}

如果对队列的基本操作不熟悉可以看:

队列的基本操作

8.由遍历序列构造二叉树

在这篇博客中,我也有讲到:http://t.csdnimg.cn/foLhQ

在这里针对考研的题型做补充:

对于前序遍历,中序遍历,后序遍历或层次遍历任何一种遍历序列而言,都对应着多种二叉树形态,例如:

所以,若只给出一棵二叉树的前/中/后/层序遍历序列中的一种,不能唯一确定一棵二叉树。只有给出其中两种,才能唯一确定一棵二叉树,并且其中一种必须为中序遍历。因为需要根据中序遍历序列,划分左右子树,再根据其他的遍历序列确定左右子树的根节点。若是前序、后序、层序序列两两组合,一定不能推出一棵唯一的二叉树。例如:

考法1:前序+中序遍历序列

分析:

① 前序遍历中,第一个是根节点,所以A是根节点。

② 再看中序遍历序列,A确定为根节点,那么他左边的就是左子树对应的中序遍历序列,右边就是右子树对应的中序遍历序列(这里只有E一个节点)。

对应下图:

③ 先序遍历中根节点后面的三个对应节点,就是左子树的前序遍历序列。

根据相同的逻辑,D一定是根节点,再根据中序遍历序列,B一定是他的左孩子,C是他的右孩子。对应下图:

考法2:后序+中序遍历序列

跟后序+中序遍历原理类似。

分析:

①根据后序遍历的最后一个节点,判断根节点为“D”。

②那么中序遍历中,D的左边为左子树,D的右边为右子树。

③再看左子树"EAF",左子树在后序遍历的顺序为"EFA",那么左子树的根节点为"A",E为左孩子,F为右孩子。

④右子树"HCBGI"在后序遍历中的顺序为"HCIGB",同理B是根节点。

⑤由于"HC"的后序遍历序列为"HC",所以C是根节点,中序遍历中"H"在“C”的左边,所以"H"是"C"的左孩子。"GI"同理。

考法3:层序+中序遍历序列

分析

① 根据层序遍历序列的第一个节点,判断"D"是根节点。

② 在层序遍历中,访问完第一层之后,继续访问第二层的两个节点,即“AB”,所以"A","B"都是根节点。

从中序遍历可以看出,若A是根节点,那么“E”“F”分别是其左右孩子。同理,B的下一层,左边是HC,右边是GI。

③根据层序遍历序列,第三层为“EFCG”四个,再中序遍历序列可知C的左孩子为H,G的右孩子是I

再看一个例子:

根据上面的步骤得到树为:

9.线索二叉树
(1)线索二叉树的作用

对二叉树进行先序/中序/后序遍历之后,会得到一个遍历序列,虽然二叉树的数据元素是非线性的关系,但是通过遍历序列可以使二叉树的元素之间存在线性关系,例如下图中,B的前驱元素是G,后继元素是E。

注:一个二叉树中的数据元素只有1个前驱,0~2个后继。而上面说的前驱和后继是基于遍历序列的。

普通二叉树的缺点:

① 对二叉树而言,能否从G节点开始遍历整棵树呢?不能,因为G节点的只有指向其孩子的指针,没有指向双亲的指针。而对于线性的遍历序列而言,是可以从G开始遍历的。

② 对二叉树而言,要找到指定节点的前驱,必须从头进行一次完整的中序遍历,例如下图,想找到p的前驱,用指针q记录当前访问的结点,指针 pre 记录上一个被访问的结点。

按照中序遍历序列的顺序依次遍历,直到q==p,那么pre指向的就是p的前驱。

找p的后继同理,只需要让指针再移动依次,当pre=p时,q就为后继。

void findPre(BiTree T){if(T!=NULL)InOrder(T—>lchild);visit(T);InOrder(T->rchild);
}//访问结点q
void visit(BiTNode *q){if (q==p)      //当前访问结点刚好是结点pfinal = pre;    //找到p的前驱elsepre = q;    //pre指向当前访问的结点}
//辅助全局变量,用于查找结点p的前驱
BiTNode *p;    //p指向目标结点
BiTNode * pre=NULL;    //指向当前访问结点的前驱
BiTNode * final=NULL;    //用于记录最终结果

若某些应用场景中,找前驱,找后继或者遍历操作十分频繁,那么就可以用线索二叉树

如何将普通二叉树转变为线索二叉树

之前说过n个结点的二叉树,有n+1个空链域。可用来记录前驱、后继的信息,例如G节点,可以将其左孩子指针指向D(前驱),右孩子指针指向B(后继)。再例如,D节点,他是中序遍历中第一个被访问的节点,所以其左孩子指针指向NULL,表示其没有前驱。

其他节点同理,线索化后就能得到中序线索二叉树:

指向前驱、后继的指针称为“线索”

线索指向中序前驱,即指定节点在中序遍历序列中的前驱,中序后继,指定节点在中序遍历序列中的后继。(后面所讲的“先序前驱”,“先序后继”,“后序前驱”,“后序后继”同理)

现在想找到某个节点的前驱和后继,只需要根据其前驱线索和后继线索就能找到了。但是若某个节点的右孩子指针指向的是他的右孩子,而不是后继,例如上图B,要怎么找后继呢?

(2)线索二叉树的存储结构
线索二叉树的定义:
//二叉树的结点(链式存储)
typedef struct BiTNode{ElemType data;struct BiTNode*lchild,*rchild;
}BiTNode,*BiTree;
//二叉链表//线索二叉树结点
typedef struct ThreadNode{ElemType data;struct ThreadNode *lchild,*rchild;int ltag,rtag;    //左、右线索标志
}ThreadNode,*ThreadTree;
//线索链表

当tag=0时,说明指针指向的是孩子,ltag=0,指针指向左孩子,rtag=0,指针指向右孩子。当tag=1时,说明指针指向的是线索,ltag=1,前驱线索,rtag=1,后继线索。 

同理,先序线索二叉树为:

增加tag值后为:

后序线索二叉树为:

增加tag后:

中序线索化:
typedef struct ThreadNode{ElemType data;struct ThreadNode *lchild,*rchild;int ltag,rteg;    //左、右线索标志}ThreadNode, *ThreadTree;//全局变量,指向当前访问结点的前驱    
ThreadNode *pre =NULL;//中序遍历二叉树,一边遍历一边线索化
void InThread(ThreadTree T){if(T!=NULL){InThread(T->lchild);  visit(T);InThread(T->rchild);}
}void visit(ThreadNode *g){if(q->lchild==NULL){    //左子树为空,建立前驱线索q->lchild=pre;q->ltag=1;}if(pre!=NULL && pre->rchild==NULL){pre->rchild=q;   //建立前驱结点的后继线索pre->rtag=1;}pre=q;
}

① 若当前结点的左孩子为空,那么建立前驱线索,刚开始前驱为pre=NULL。

② 由于pre ==NULL,跳过第二个循环,并且将pre指向下一个节点。

③ 接下来访问G节点,由于G节点左指针为空,所以将其左指针指向pre。并将pre指向下一个节点。

④接下来访问B节点,B节点左孩子非空,但他的pre指针指向的节点G,右孩子是空的,那么就将G节点的右孩子指针线索化,指向其后继,也就是q(pre->rchild=q,第2个循环)。

其他节点的线索化同理,当访问到最后一个节点后,pre=q指向最后一个节点。之后就不会再访问其他节点了,那最后一个节点的右孩子也是空的,应该也要将其线索化才对,怎么做呢?

检查pre 的 rchild 是否为 NULL,如果是,则令rtag=1。

即:

if(pre->rchild==NULL)

        pre->rtag=1;

typedef struct ThreadNode{ElemType data;struct ThreadNode *lchild,*rchild;int ltag,rtag;
}//全局变量
ThreadNode *pre=NULL;void CreateInThread(ThreadNode *T){pre=NULL;if(T!=NULL){InThread(T);if(pre->rchild==NULL)pre->rtag=1; //处理遍历的最后一个节点}
}//中序遍历二叉树,一边遍历一边线索化
void InThread(ThreadTree T){if(T!=NULL){InThread(T->lchild);  visit(T);InThread(T->rchild);}
}void visit(ThreadNode *g){if(q->lchild==NULL){    //左子树为空,建立前驱线索q->lchild=pre;q->ltag=1;}if(pre!=NULL && pre->rchild==NULL){pre->rchild=q;   //建立前驱结点的后继线索pre->rtag=1;}pre=q;
}

王道书中的代码:

//pre设为引用类型,就相当于在函数外设置了一个全局变量
void InThread(ThreadTree p,ThreadTree &pre){if(p!=NULL){//递归线索化左子树InThread(p->lchild,pre);if(p->lchild==NULL){p->lchild=pre;p->ltag=1;}if(pre!=NULL && pre->rchild==NULL){pre->rchild=p;pre->rtag=1;}pre=p;//递归线索化右子树InThread(p->rchild,pre);}   
}void CreateInThread(Thread T){ThreadTree pre=NULL;if(T!=NULL){InThread(T,pre);pre->rchild=NULL;pre->rtag=1;}
}

上面的代码在处理最后一个节点时,为什么没有判断rchild=NULL:

因为中序遍历中,访问顺序为"左根右",最后一个被访问的节点一定没有右孩子。 

先序线索化:
//全局变量
ThreadNode *pre=NULL;//先序遍历二叉树,一边遍历一遍线索化
void PreThread(ThreadTree T){if(T!=NULL)visit(T);PreThread(T->rchild);    PreThread(T->lchild);}void visit(ThreadNode *q){if(q->lchild==NULL){q->lchild=pre;q->ltag=1;if(pre!=NULL && pre->rchild==NULL)pre->rchild=q;pre->rtag=1;}pre=q;
}

这个代码有一个问题:

在访问完第3个节点后,D的前驱线索指向B,接下来会继续处理这个节点的左子树,但是我们已经把D的左孩子指针指向了B,所以处理左子树时,q指针会再次指回B,这样访问节点会进入死循环。

所以修改PreThread函数,通过ltag来判断lchild是左孩子还是前驱线索:

void PreThread(ThreadTree T){if(T!=NULL)visit(T);if(T->ltag==0)    //lchild不是前驱线索PreThread(T->lchild);    PreThread(T->rchild);
}

完整代码如下:

//全局变量
ThreadNode *pre=NULL;//先序遍历二叉树,一边遍历一遍线索化
void PreThread(ThreadTree T){if(T!=NULL)visit(T);if(T->ltag==0)    //lchild不是前驱线索PreThread(T->lchild);    PreThread(T->rchild);
}void visit(ThreadNode *q){if(q->lchild==NULL){q->lchild=pre;q->ltag=1;if(pre!=NULL && pre->rchild==NULL)pre->rchild=q;pre->rtag=1;}pre=q;
}void CreatePreThread(ThreadTree T){pre=NULL;if(T!=NULL){PreThread(T);if(pre->rchild==NULL)pre->rtag=1;    //处理遍历的最后一个节点}
}

王道书中的先序线索化,处理逻辑是相同的:

void PreThread(Threadtree p,ThreadTree &pre){
//访问根节点if(p!=NULL){if(p->rchild==NULL)p->lchild=pre;p->ltag=1;}if(pre!=NULL && pre->rchild==NULL){pre->rchild=p;pre->rtag=1;}pre=p;
//访问左子树if(p->ltag==0)PreThread(p->lchild,pre);
//访问右子树PreThread(p->rchild,pre);
}void CreatePreThread(ThreadTree T){ThreadTree pre=NULL;if(T!=NULL){PreThread(T,pre);if(pre->rchild==NULL)    pre->rtag=1;}
}

后序线索化:
//全局变量
ThreadNode *pre=NULL;void CreatePostThread(ThreadTree T){pre=NULL;if(T!=NULL){PostThread(T);if(pre->rchild==NULL)pre->rtag=1;}
}//后遍历二叉树,一边遍历一边线索化
void PostThread(ThreadTree T){if(T!=NULL){PostThread(T);PostThread(T);visit(T);}
}void visit(ThreadNode *q){if(q->lchild==NULL){q->lchild=pre;q->ltag=1;}if(pre!=NULL && pre->rchild==NULL){pre->rchild=q;pre->rtag=1;}pre=q;
}

在王道书中的后续线索化:

//后序线索化
void PostThread(ThreadTree p,ThreadTree &pre){if(p!=NULL){PostThread(p->lchild,pre);//递归,线索化左子树PostThread(p->rchild,pre);//递归,线索化右子树//访问根节点if(p->lchild==NULL){p->lchild=pre;p->ltag=1;}if(pre!=NULL && pre->rchild==NULL){pre->rchild=p;pre->rtag=1;}pre=p;}
}void CreatePostThread(ThreadTree T){ThreadTree pre=NULL;if(T!=NULL){PostThread(T,pre);
//一定不要忘记处理最后一个节点if(pre->rchild==NULL)pre->rtag==1;}
}

为什么在先序遍历中会出现死循环问题,而在后序遍历和中序遍历中不会:

因为后序遍历(左右根),中序遍历(左根右)中,在处理根节点时,其左孩子一定已经处理完了。而在先序遍历(根左右)中,需要先处理根节点,再处理左孩子。处理根节点时,会将其左孩子指针指向前驱,那么再处理左孩子时,则当前又访问回前驱节点,从而导致节点的遍历陷入死循环。

10.根据线索二叉树找前驱/后继
(1)中序线索二叉树
•找中序后继

在中序线索二叉树中找到指定结点*p的中序后继 next:

① 若p->rtag==1,则next=p->rchid;

② 若p->rtag==0,那么指定节点一定有右孩子,也就是右子树非空。按照“左根右”的规则,右子树中第一个被访问的结点,就是p的后继。也就是p的右子树中最左下角的结点。

//找到以p为根的子树中,第一个被中序遍历的结点
ThreadNode *Firstnode(ThreadNode *p){//循环找到最左下结点(不一定是叶节点)while(p->ltag==0)p=p->lchild;return p;
}//在中序线索二叉树中找到结点p的后继结点
ThreadNode *Nextnode(ThreadNode *p){if(p->rtag=0)return Firstnode(p->rchild);elsereturn p->rchild;    //rtag=1直接返回后继线索
}//对中序线索二叉树进行中序遍历(利用线索实现的非递归算法)
void Inorder(ThreadNode *T){for(ThreadNode *p=Firstnode; p!=NULL; p=Nextnode(p))visit(p);
}
•找中序前驱

在中序线索二叉树中找到指定结点*p的中序前驱 pre:

①若 p->ltag==1,则 pre= p->lchild
②若 p->ltag==0,则p一定左孩子,按照"左根右"的规则,结点p的前驱一定是左子树中按照中序遍历最后被访问的结点,即pre=p的左子树中最右下的结点

//找到以p为根的子树中,最后一个被中序遍历的结点
ThreadNode *Lastnode(ThreadNode *p){//循环找到最右下结点(不一定是叶子节点)while(p->rtag==0)p=p->rchild;return p;
}//在中序线索二叉树中找到结点p的前驱结点
ThreadNode *Prenode(ThreadNode *p){//左子树中最右下结点if(p->ltag==0)return Lastnode(p->lchild);else return p->lchild;    //ltag==1直接返回前驱线索//对中序线索二叉树进行中序遍历
void RevInorder(ThreadNode *T){for(ThreadNode *p=Lastnode(T); p!=NULL; p=Prenode(p))visit(p);
}
(2)先序线索二叉树
•找先序后继

在先序线索二叉树中找到指定结点*p的先序后继next

①若 p->rtag==1,则next = p->rchild
②若 p->rtag==0,则说明p一定有右孩子,假设p结点有左孩子,那么按照”根左右“的规则,p的后继一定是左子树中第一个被访问的结点 ,即左孩子。

假设没有左孩子,那么按照"根右"的规则,p的后继是右子树中第一个被访问的结点,即右孩子。

// 在先序线索二叉树中找到结点p的后继结点
ThreadNode *Nextnode(ThreadNode *p) {if (p->rtag == 0){if(p->lchild!=NULL)        // 如果p有左孩子return p->lchild;else        // 如果p没有左孩子,返回右孩子return p->rchild;}elsereturn p->rchild;    //rtag=1直接返回后继线索    
}// 对先序线索二叉树进行先序遍历
void Preorder(ThreadNode *T) {ThreadNode *p = T;while (p != NULL) {visit(p);  // 访问当前节点p = Nextnode(p); // 移动到下一个节点}
}
•找先序前驱

在先序线索二叉树中找到指定结点*p的先序前驱 pre

① 若 p->ltag==1,则next = p->lchild
② 若 p->ltag==0,那么p结点一定有左孩子,但是按照"根左右"的规则,p左右子树的所有结点只可能是p的后继,不可能是p的前驱。所以不可能在其左右子树中找到p的前驱。

所以在先序线索中找先序前驱,只能从头开始进行先序遍历。

这个结论是建立在二叉链表的基础上的,如果是三叉链表,也就是有指向父节点的指针,那么:

如果能找到p的父结点,且p是左孩子,按照"根左右"的规则,p结点一定是在父节点之后就被访问的结点。所以p的父节点一定是其前驱。

如果能找到p的父节点,且p是右孩子,其左兄弟为空。按照"根右"的规则,p的父节点一定为p的前驱。

 如果能找到p的父节点,且p是右孩子,其左兄弟非空。按照"根左右"的规则,p的前驱为 左兄弟子树中最后一个被先序遍历的结点。

想要找左兄弟子树中最后一个被先序遍历的结点,则对于左子树而言,一定要优先往有右边的路走,走到尽头,再往左子树走;若没有右边的路,先往左子树走,左子树中一旦碰到有右边的路,就往右边走。例如下图,C的前驱结点为H。

如果p是根节点,则p没有先序前驱。

//找到以p为根的子树中,最后一个被先序遍历的结点
ThreadNode *Lastnode(ThreadNode *p){//循环找到最右下结点(不一定是叶子节点)while(p->rtag==0)p=p->rchild;return p;
}//在先序线索二叉树中找到结点p的前驱结点
ThreadNode *Prenode(ThreadNode *p){if (p->rtag == 0){if (p->parent == NULL) {printf("p为根结点,没有前驱!");return NULL;} else if (p->parent->lchild == p) {// p是父节点的左孩子,返回父节点return p->parent;} else {// p是父节点的右孩子,且父节点没有左孩子,返回父节点if (p->parent->lchild == NULL) {return p->parent;} else {// p是父节点的右孩子,且父节点有左孩子,返回左孩子为根的子树中最后一个被先序遍历的结点return Lastnode(p->parent->lchild);}}}elsereturn p->rchild;    //rtag=1直接返回后继线索    
}//对先序线索二叉树进行先序遍历
void RevPreorder(ThreadNode *T){for(ThreadNode *p=Lastnode(T); p!=NULL; p=Prenode(p))visit(p);
}
(3)后序线索二叉树
•找后序前驱

在后序线索二叉树中找到指定结点*p的后序前驱 pre

①若 p->ltag==1,则 pre = p->lchild
②若 p->ltag==0,则p结点一定有左孩子,假设有右孩子,按照后序遍历中"左右根"的规则,p结点的后序前驱一定是右子树中按照后序遍历最后一个被访问到的结点。那么p的右孩子就是p的后序前驱。

若p结点没有右孩子,按照"左根"的规则,p结点的前驱是左子树当中按照后序遍历最后一个被访问的结点,也就是p的左孩子

//在后序线索二叉树中找到结点p的前驱结点
ThreadNode *Prenode(ThreadNode *p){if(p->ltag==0){//如果有右孩子,那么右孩子就是p的前驱if(p->rchild!=NULL)return p->rchild;elsereturn p->lchild;    //如果没有右孩子,那么左孩子就是p的前驱}else return p->lchild;    //ltag==1直接返回前驱线索
}//对后序线索二叉树进行后序遍历
void RevPostorder(ThreadNode *T){ThreadNode *p = T;while (p != NULL) {visit(p);  // 访问当前节点p = Prenode(p); // 移动到下一个节点}
}
•找后序后继

在后序线索二叉树中找到指定结点*p的后序后继 next

①若 p->rtag==1,则next = p->rchild
②若 p->rtag==0,说明p结点一定有右孩子,按照"左右根"的规则,p的左右子树中所有结点只可能是他的前驱,不可能是他的后继结点,所以不能在p的左右子树中找到后序后继。

若想要在后序线索二叉树中找到后序后继,只能从头开始先序遍历。

同理,如果用三叉链表,即可以找到p节点的父节点:

如果能找到p的父节点,且p是右孩子。那么p的后序后继一定是其父节点。

如果能找到p的父节点,且p是左孩子,其右兄弟为空。那么p的后序后继也是p的父节点。

如果能找到p的父节点,且p是左孩子,其右兄弟非空,p的后序后继为右兄弟子树中第一个被后序遍历的节点。

如何找到右兄弟子树中第一个被后序遍历的节点?

对于右子树而言,一定要优先走左边的路,如果左边的路走到尽头,就走右子树,如果没有左子树,就先走右边的路,遇到左子树就走左边。如下图所示可知,B的后序后继为G。

如果p是根节点,则p没有后序后继。因为在后序遍历中,根节点一定是最后一个被访问的。

// 找到以p为根的子树中,第一个被后序遍历的结点
ThreadNode *Firstnode(ThreadNode *p){// 循环找到最左下结点(不一定是叶节点)while(p->ltag == 0)p = p->lchild;return p;
}// 在后序线索二叉树中找到结点 p 的后继结点
ThreadNode *Nextnode(ThreadNode *p){if(p->rtag == 0){  if(p->parent == NULL){  printf("p为根结点,没有后继!");return NULL;} else if(p->parent->rchild == p){    //如果p为父结点的右结点return p->parent;} else{if(p->parent->lchild == p && p->parent->rchild == NULL){    //如果p为父结点的左结点,且p的父结点的右结点为空return p->parent;} else{//如果p为父结点的左结点,且p的父结点的右结点不为空return Firstnode(p->rchild);   }}} else{return p->rchild;    // rtag=1 直接返回后继线索}
}// 对后序线索二叉树进行后序遍历
void Postorder(ThreadNode *T){for(ThreadNode *p = Firstnode(T); p != NULL; p = Nextnode(p))visit(p);
}

总结:

中序线索二叉树找前驱和后继都是可以的,但在先序线索二叉树中不能找到前驱,只能从头开始进行先序遍历,除非使用三叉链表。同理,后序线索二叉树不能找到后继,只能从头开十四进行后序遍历,除非使用三叉链表。


最后,不懂*和&的区别及应用场景的可以看看这篇:http://t.csdnimg.cn/6eprE

不懂.和->的区别的话,推荐看看这篇:http://t.csdnimg.cn/l5oL2

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://xiahunao.cn/news/2981674.html

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

Maven:配置与使用指南1

https://mvnrepository.com Maven 1.maven简介 不同模块的jar包以及同时设计的功能的微小变化版本&#xff1b; 真实的开发环境&#xff1a;我们将我们的源代码在服务器上重新编译重新打包&#xff0c;工程升级维护过程繁琐 1.Maven是一个项目管理工具&#xff0c;将项目开…

WebSocket的原理、作用、API、常见注解和生命周期的简单介绍,附带SpringBoot示例

文章目录 原理作用客户端 API服务端 API生命周期常见注解SpringBoot示例 WebSocket是一种 通信协议 &#xff0c;它在 客户端和服务器之间建立了一个双向通信的网络连接 。WebSocket是一种基于TCP连接上进行 全双工通信 的 协议 。 WebSocket允许客户端和服务器在 单个TCP连接上…

【音视频服务】VoIP 推送转 APNs 推送如何设置?

融云控制台 VoIP 设置入口&#xff1a; VoIP 设置 功能说明 针对苹果官方要求收到 VoIP 推送后必须通知给系统 CallKit 框架&#xff0c;如果收到 VoIP 推送后没有报告给 CallKit&#xff0c;iOS 将终止该应用程序&#xff08;目前只影响用 Xcode 11 打包的 App 运行在 iOS 13 …

Springboot实现国际化以及部署Linux不生效问题

1、在application.properties 添加以下配置&#xff1a; #国际化配置 spring.messages.basenamei18n/messages/messages spring.messages.fallback-to-system-localefalse 2、添加配置文件在 resources目录下 如下图所示&#xff1a; 这个国际化文件命名有个坑&#xff0c;必须…

伙伴匹配(后端)-- 前端初始化

文章目录 用脚手架初始化项目安装依赖启动项目image.png整合组件库Vant 用脚手架初始化项目 Vite官网&#xff1a;https://www.vitejs.net/guide/#scaffolding-your-first-vite-project cmd切换到项目目录下初始化项目 npm init vitelatest安装依赖 npm install启动项目 整…

Axure实现tab页面切换功能

1. 实现效果 2. 实现原理 创建两个标签&#xff0c;并实现点击时选中状态点击时&#xff0c;设置面板状态 3. 实现步骤 3.1 实现可切换的标签 在页面上拖拽两个矩形作为两个tab标签&#xff0c;并命名 tab1 和 tab2 设置每个矩形的边框显示&#xff0c;只显示下边框即可 …

2万字长文:Docker必知必会系列

安装docker 安装&#xff1a; Docker 分为 CE 和 EE 两大版本。CE 即社区版&#xff08;免费&#xff0c;支持周期 7 个月&#xff09;&#xff0c;EE 即企业版&#xff0c;强调安全&#xff0c;付费使用&#xff0c;支持周期 24 个月。 **Docker CE 分为 **stable&grav…

Python | Leetcode Python题解之第46题全排列

题目&#xff1a; 题解&#xff1a; class Solution:def permute(self, nums):""":type nums: List[int]:rtype: List[List[int]]"""def backtrack(first 0):# 所有数都填完了if first n: res.append(nums[:])for i in range(first, n):# 动…

抽象工厂模式设计实验

【实验内容】 楚锋软件公司欲开发一套界面皮肤库&#xff0c;可以对 Java 桌面软件进行界面美化。为了保护版权&#xff0c;该皮肤库源代码不打算公开&#xff0c;而只向用户提供已打包为 jar 文件的 class 字节码文件。用户在使用时可以通过菜单来选择皮肤&#xff0c;不同的…

【C++】C++的四种类型转换

一、C语言中的类型转换 在C语言中有两种类型转换&#xff0c;隐式类型转换和显示类型转换。 如果赋值运算符左右两侧类型不同&#xff0c;或者形参与实参类型不匹配&#xff0c;或者返回值类型与接收返回值类型不一致时&#xff0c;就需要发生类型转化。 隐式类型转换&#…

Unity系统学习笔记

文章目录 1.基础组件的认识1.0.组件继承关系图1.1.项目工程文件结构&#xff0c;各个文件夹都是做什么的&#xff1f;1.2.物体变化组件1.2.3.三维向量表示方向1.2.4.移动物体位置附录&#xff1a;使用变换组件实现物体WASD移动 1.3.游戏物体和组件的显示和禁用1.3.1.界面上的操…

C语言入门课程学习笔记2

C语言入门课程学习笔记2 第8课 - 四则运算与关系运算第9课 - 逻辑运算与位运算第10课 - 深度剖析位运算第11课 - 程序中的选择结构 本文学习自狄泰软件学院 唐佐林老师的 C语言入门课程&#xff0c;图片全部来源于课程PPT&#xff0c;仅用于个人学习记录 第8课 - 四则运算与关系…

共享汽车管理|基于SprinBoot+vue的共享汽车管理系统(源码+数据库+文档)

共享汽车管理目录 基于SprinBootvue的共享汽车管理系统 一、前言 二、系统设计 三、系统功能设计 1 管理员模块的实现 1.1 用户信息管理 1.2 投放地区管理 1.3 汽车信息管理 1.4 汽车入库管理 2 用户模块的实现 2.1 汽车投放 2.2 使用订单管理 2.3 汽车归还 四、…

为AI电脑生态注入强悍动力,安耐美PlatiGemini 1200W高性能电源

在DIY攒机的过程中&#xff0c;电源是非常重要的一环&#xff0c;现在高性能的硬件功耗往往很高&#xff0c;因此一款优秀的电源整个系统稳定运行的基石。最近&#xff0c;我发现一款由安耐美&#xff08;Enermax&#xff09;推出的PlatiGemini 1200W电源&#xff0c;它不仅满足…

刷代码随想录有感(45):二叉树的最大深度

题干&#xff1a; 力扣这里给了定义&#xff1a;二叉树的最大深度指的是从根节点开始&#xff0c;到最远叶子所经过的节点数。 代码&#xff1a; class Solution {//递归实现 public:int maxDepth(TreeNode* root) {if(root NULL)return NULL;int leftheight maxDepth(root…

离散数学之命题逻辑思维导图+大纲笔记(预习、期末复习,考研,)

大纲笔记&#xff1a; 命题逻辑的基本概念 命题与联结词 命题 命题是推理的基本单位 真命题&#xff0c;假命题 特征 陈述句 唯一的真值 是非真即假的陈述句 非命题 疑问句 祈使句 可真可假 悖论 模糊性 三个基本概念 复合命题 真值取决于原子命题的值和逻辑联结词 原子命题 逻…

【leetcode面试经典150题】71. 对称二叉树(C++)

【leetcode面试经典150题】专栏系列将为准备暑期实习生以及秋招的同学们提高在面试时的经典面试算法题的思路和想法。本专栏将以一题多解和精简算法思路为主&#xff0c;题解使用C语言。&#xff08;若有使用其他语言的同学也可了解题解思路&#xff0c;本质上语法内容一致&…

Mybatis框架怎么查看执行的sql语句

文章目录 一、打开idea搜索mybatis SimpleExecutor类二、找到类中doQuery方法&#xff0c;并打断点二、发请求后&#xff0c;查看boundSql 一、打开idea搜索mybatis SimpleExecutor类 org.apache.ibatis.executor.SimpleExecutor二、找到类中doQuery方法&#xff0c;并打断点 …

外贸订单从初始到成交,都涉及哪些环节?

前言 经常听到这个言论&#xff1a;做外贸不就是找到国外客户&#xff0c;用英文把产品推荐给他们&#xff0c;然后收款。就这么easy&#xff0c;能有多复杂&#xff1f; 没那么简单&#xff0c;外贸是和内销有相通之处&#xff0c;但是过程却完全不同。涉及到的环节还是挺复杂…

为什么要分库分表?(设计高并发系统的时候,数据库层面该如何设计?)

目录 1.分表 2.分库 说白了&#xff0c;分库分表是两回事儿&#xff0c;大家可别搞混了&#xff0c;可能是光分库不分表&#xff0c;也可能是光分表不分库&#xff0c;都有可能。 我先给大家抛出来一个场景。 假如我们现在是一个小创业公司(或者是一个 BAT …