1.1 二叉树遍历

1.1 前提

二叉树遍历我将围绕诸多概念问题进行展开。

问题1： 什么叫二叉树的遍历？

​ 答： 这个问题看似简单，但实际上有很多坑，我们知道二叉树的遍历分为三种分别是“ 先序遍历”，“中序遍历”。“后续遍历”

​ 这里我再次重申什么叫做二叉树的遍历？请认真思考，或者看书找答案。

二叉树的三种遍历：

​ 先序遍历 ： 根遍历 、 左子树遍历、右子树遍历

​ 中序遍历 ： 左子树遍历、 根遍历 、右子树遍历

​ 后序遍历 ： 左子树遍历、右子树遍历、根遍历

注意：我这里为什么要重复三次遍历？

三个概念：遍历 和 访问 和 经过

​ 遍历是相对于树而言的；

​ 访问是相对于节点和树而言的；

​ 经过也是相对于节点而言的；

重要概念：遍历过程中的经过节点，不代表访问节点

​ 当我用中序来遍历子树时：遍历过程中我正在 访问的是节点是 A节点，但我能不能确定我下一个访问谁？

​ 答：可以，我下一个访问的是A节点的右子树遍历过程中最左的节点！注意是最左的节点，这个概念是不是很少提及，这些过程都是在递归中完成的自然就会被虚化，导致你将遍历中的下一个访问和遍历中当前访问节点的左右子树搞混。 这有点深如探讨了。先不如此深入等我们讲到二叉线索树再继续探讨。

​ 通过这个概念是不是明白了 遍历 访问 经过的概念的细微差别。

问题2：遍历和访问的联系？

​ 遍历二叉树的过程就是访问二叉树每一个节点的过程，且每一个节点只访问一次；

​ 遍历中访问节点的顺序根据二叉树的形态以及你选择怎么样遍历（三种遍历选择）是有关联的；

​ 并且遍历过程中你会得到一串有顺序的二叉树节点的编号。

问题3：这个有顺序的编号的意义是什么？

这个有顺序的编号就是 你访问二叉树节点的先后顺序，注意是访问顺序，要和经过顺序区分开。

问题4：什么是访问？如何对节点进行访问？

其实你获得这串顺序编号就是通过访问操作而来的

假设访问操作是 visit（p） #p是指向被访问的节点

只需要你将visit函数编写为：“输出参数p所指向地址的节点的编号

void visit(二叉树结构的指针类型 p)
{
	printf("%c",p->data)  #我们在遍历中默认：二叉树结构中data存储的是二叉树的编号。
}

通过上述代码你在用遍历过程中根据visit添加位置的不同就能确定二次树的访问顺序

到这里你应该已经能明白大部分的问题了，我们开始通过代码对知识的巩固。

1.2 二叉树遍历代码：二叉树的遍历

1.递归类型的二叉树遍历：

1.先序遍历

void PreOrder(BiTree p)
{
	visit(p);                 # 访问节点p
	PreOrder(p->plchild);     # 遍历节点p的左子树
	PreOrder(p->prchild);     # 遍历节点p的右子树
}
注：BiTree是二叉树的结构体的指针类型，所以p就是二叉树类型的指针。
只有visit(p)操作是在访问p，而其他两个操作相当于在访问p的左右子树。

2.中序遍历

void InOrder(BiTree p)
{
	
	PreOrder(p->plchild);     # 遍历节点p的左子树
	visit(p);                 # 访问节点p
	PreOrder(p->prchild);     # 遍历节点p的右子树
}
注：BiTree是二叉树的结构体的指针类型，所以p就是二叉树类型的指针。
只有visit(p)操作是在访问p，而其他两个操作相当于在访问p的左右子树。

3.后续遍历

void PostOrder(BiTree p)
{
	
	PreOrder(p->plchild);     # 遍历节点p的左子树，也可以理解这一步是在访问该函数p节点之前的那些节点。
	PreOrder(p->prchild);     # 遍历节点p的右子树
	visit(p);                 # 访问节点p
	
}
注：BiTree是二叉树的结构体的指针类型，所以p就是二叉树类型的指针。
只有visit(p)操作是在访问p，而其他两个操作相当于在访问p的左右子树。

通过对三种遍历的代码的书写，是不是就有开始晕递归了！！！！！

哈哈哈，慢慢来，let’s go！！！

概念一：

​ 上述三个遍历如果都没有visit§这个操作是不是都是一样的了

void Order(BiTree p)
{
	
	PreOrder(p->plchild);     # 遍历节点p的左子树
	PreOrder(p->prchild);     # 遍历节点p的右子树	
}

​ 这个过程是不是就是但单纯的**”经过“一遍二叉树，注意这里是经过，单单是经过的顺序是和先序遍历是一样的**。

​ 然而我们的编写 先序、中序、后续其实并没有”节点改变“经过顺序，而是通过对**“节点访问” 进行了限定**，此时访问对象被分为三个对象：当前树的根节点，当前树左子树、当前树的右子树。

​ 当我们想先按照先序访问：我们就把访问根节点放在访问另外两位的前面就会确保当前这颗树的三个访问对象按照先序的设定进行访问，注意此时我们把访问左右子树分别看作一个整体。然而左子树右子树都是我们访问这个根节点所在的二叉树是一个结构，所以让左子树和右子树上的节点进行了相同模式的访问。

概念二：visit（）函数是访问当前节点，PreOrder()这个函数是按照先序访问树节点（也称作遍历）;

两个操作都是访问 一个是对节点的访问，一个是对树的访问（也叫遍历）

2.非递归类型的二叉树遍历

​ 其实非递归类型的二叉树遍历就是线索二叉树，我们从根节点按照先序（中序/后序）一直找当前访问节点的后继的过程，然后将其进行数学归纳后的结果。

这里我感觉王道书上也写的比较笼统，能看懂书上分析的逻辑，但是要按照线索二叉树求节点后继的那种方法去做才能理解更加透彻。

1.3：通过遍历序列构造二叉树

思路： 通过（先序 + 中序） / （ 后序 + 中序） / （ 层次 + 中序） 三种组合构建二叉树；

其中三种组合特点是 ： 有一个遍历能很简单的提供根节点，中序能根据根节点划分左右子树，然后根据中序划分的左右子树的长度，再去找提供根节点那个序列中的左右子树，进行迭代；

如下图是先序：

2.1 线索二叉树

2.1.1 建立线索二叉树

通过学习线索二叉树我得到的一些感悟：

前提1：线索二叉树说的直接前驱（前驱节点），直接后继（后继节点）是 将二叉树遍历后得到的访问顺序中 每个节点在该顺序中的前后继：

例如 中序遍历二叉树得到一个访问顺序 ： A S D F G H J

则G的前驱是F，G的后继是H。

这个前驱和后继 就是访问过程中该点之前访问的节点和该店之后要访问的节点。

前提2：建立二叉线索树的过程本质是在进行一次 二叉树遍历过程中完成的。

​ 中序线索二叉树建立就是进行中序遍历节点过程中建立线索

​ 先序线索二叉树建立就是进行先序遍历节点过程中建立线索

​ 后序线索二叉树建立就是进行后序遍历节点过程中建立线索

代码讲解：王道配套视频讲解的很好，但是有一些细节视频里面没有细讲。我们通过代码讲解

中序建立线索二叉树

中序遍历根据二叉树线索化的条件对访问操作的改进

注：这里pre和p传进来的是引用。
void InThread(ThreadTree &p,ThreadTree &pre)
{

	if(P!=null)
	{
		InThread(p-lchild,pre)   这里相当于访问当前节点前的所以节点
		
		{
		#这里面的代码相当于中序遍历的 visit()
		我们在遍历的过程中进行了建立线索的进行的操作如下；
		1：当“真在遍历节点的左子树为空我们将他的左指针指向刚刚访问过的那个节点”
		2：如果正在访问节点的前一个节点不为空，且前一个节点的右子树为空，就让前一个节点的右子树指针指向当前节点。
		3：当前节点访问操作以及实现，但是要将当前节点变成 下一个访问的节点的上一个节点，也就是将p赋值给pre指针。
			if(p->lclild==null)
			{
				p -> lchild = pre;
				p -> ltag = 1;
			}
		
			if(pre->rclild==null && pre!= null )
            {
                pre -> rchild = p;
                pre -> rtag = 1;
            }
            将当前节点设置为前
            pre = p;
		}
		
        Inthread(p->rchild,pre)  这里相当于访问当前节点前的所以节点
	}

}

void createInthread(ThreadTree T)
{	
	ThreadTree pre = null;
	if(t!=null)
	{	
		InThread(T,pre);
		{
			#注意我这是在这里加了代码块{}，并没有递进结构
			pre->rchild = null;
			pre - rtag=1;
			#这一块代码有讲究：
				我们这里是中序遍历，InThread结束后 p是指向null的，pre指向最后一个被访问的节点；
				为什么能直接最后一个将其设置为空 而且 将rtag设置为1（表明最后一个几点没有右子树）
                证明：当pre指向最后一个节点时，根据中序遍历的特点，若此节点在树结构中后有右子树，则这个节点一定不是最后一个节点，最后一个访问的节点应该在这个节点的右子树，因为题目中中序已经访问完毕，所以pre指向一定是最后一个节点，所以这个节点的右子树一定是空，也即是说p要指向空，从而根据线索化中的设定，当pre的右子树为空让pre的右子树等于p，所以才有pre->rchild = null(p)		
       }
		
	}


}

这里我们有一个点需要证明解释一下：为什么在createInthread（）函数中，InThread（）函数执行后我们直接将pre当前指向的节点的右孩子指向了空？

解释：关于先序线索二叉树建立createInthread（）函数中的代码{ pre->rchild = null; }解释

问：为什么能直接最后一个节点的右指针设置为空，且将rtag设为1？

​ 第一步：我们从执行的角度分析：当结束InThread（）函数执行结束后的pre指针是指向最后一个节点的，这里是无可置疑的，既然pre是指向最后一个遍历的节点所以最后一个节点的后边是空节点，因此 p 也就一定指向null。

​ 第二步：我们分析中序遍历：中序遍历是先遍历左子树，再遍历根节点，再遍历右子树，如果最后一个节点有右子树的情况下，这个节点能成为最后一个被遍历的节点？这里很容易理解当存在右子树是时，该节点是不能成为最后一个节点的，所有我们能够证明中序遍历最后一个节点一定是没有右子树的，所有我们可以直接将pre所指向的节点的右子树指向空。

​ 第三步：我们将pre设置为空，其实就是将他线索到p了，所以将rtag设为1

当我们用先序和后续建立线索二叉树有什么区别？

先序建立线索二叉树：

1：则需要更改OrdThread（）遍历二叉树函数中 遍历当前节点和左右子树对象的顺序，代码如下

注：这里pre和p传进来的是引用。
void PreThread(ThreadTree &p,ThreadTree &pre)
{

	if(P!=null)
	{
		{
		#这里面的代码相当于先序遍历的 visit()
		我们在遍历的过程中进行了建立线索的进行的操作如下；
		1：当“真在遍历节点的左子树为空我们将他的左指针指向刚刚访问过的那个节点”
		2：如果正在访问节点的前一个节点不为空，且前一个节点的右子树为空，就让前一个节点的右子树指针指向当前节点。
		3：当前节点访问操作以及实现，但是要将当前节点变成 下一个访问的节点的上一个节点，也就是将p赋值给pre指针。
			if(p->lclild==null)
			{
				p -> lchild = pre;
				p -> ltag = 1;
			}
		
			if(pre->rclild==null && pre!= null )
            {
                pre -> rchild = p;
                pre -> rtag = 1;
            }
            将当前节点设置为前
            pre = p;
		}
		#这里我们明白这些子树的访问都是在该节点之后进行的
		*******重点，讲解在下边
		if(p-ltag==0)
		{
			InThread(p-lchild,pre)   这里相当于访问当前节点左子树的所有节点
		}
		
		
        Inthread(p->rchild,pre)  这里相当于访问当前节点右子树的所以节点
	}

}

2：修改createInthread（）函数，因为createtthread（）中{ pre->rchild = null; }这个步骤是因为中序遍历的特点才能这样直接写，先序遍历我们没有证明，其实先序也是可以这样写，如下证明：

void createInthread(ThreadTree T)
{	
	ThreadTree pre = null;
	if(t!=null)
	{	
		PreThread(T,pre);
		{
			pre->rchild = null;
			pre - rtag=1;
       }
	}
}

解释：关于先序遍历createInthread（）函数中在PreThread（）函数执行后 { pre->rchild = null; }能够直接这样设定的原因

​ 我们这里是先序遍历，OrdThread结束后 p是指向null的，pre指向最后一个被访问的节点；

问：为什么能直接最后一个节点的右指针设置为空，且将rtag设为1？

​ 第一步：我们从执行的角度分析：当结束OrdThread（）函数后的，pre指针是指向最后一个节点的，这里是无可置疑的，既然pre是指向最后一个遍历的节点所以最后一个节点的后边是空节点，因此 p 也就一定指向null。

​ 第二步：我们分析先序遍历：先序遍历是先遍历根节点，在遍历它的两个子树，如果最后一个节点有右子树的情况下，这个节点能成为最后一个被遍历的节点？这里很容易理解是不能的，所有我们能够证明先序遍历最后一个节点一定是没有子孙（包括没有右子树）的，所有我们可以直接将pre所指向的节点的右子树指向空。

​ 第三步：我们将pre设置为空，其实就是将他线索到p了，所以将rtag设为1

解释：关于PreThread()函数中，当我们访问完当前节点我们需要判断当前节点左子树是否是空，才能决定是否让其左子树进行遍历而右子树却不需要判定。

​ 前提：在线索化过程中 ，每一次访问节点时，只会对当前被访问节点的左子树指针进行线索化 和 被访问节点的前一个节点的右子树指针进行线索化，当前访问的节点的右子树指针是没有发生改变的。

​ 关于这个点王道视频讲的很清楚：我们用图和文字也进行解释如下：

​

用图举例，如果我们当前访问的是D节点时：

​ 我们会进行两步操作：第一：判断D节点的左子树是否为空，当D节点左子树为空时，将D节点的左指针线索化到pre所指向的B节点。

​ 第二：判断D节点的前一个节点B的右子树是否为空，若B节点右子树为空时，我们将其右子树线索化到D节点。

​ 当访问完D节点，正常我们该进行PreThread(p->lchild);

​ 于是变引发了问题！ 如上图：当我们进行PreThread(p->lchild); 此时D节点的左子树指向B节点，当对B节点进行访问，当我们访问完B节点就开始对他的左子树进行访问，我们就又回到了D节点，从而无线循环下去，所以我们限定：只有当被访问节点左子树不空的时候我们才对其访问也就是ltag==0时。

疑问点：当访问节点结束时为什么不用判断该节点右指针指向的是线索还是儿子,只用对当前节点左子树进行判空？

​ 答：根据前提可知，我们访问当前节点时并不会对右指针进行线索化，所以不会造成这样的问题。

疑问点：为什么只有先序用进行这样的判断：

​ 答：因为只有先序遍历，在根节点访问完成后会去访问左子树，而中序和后序在根节点访问完成后不会对其左子树访问，因此不会造成这种情况。

后序建立线索二叉树

后序建立线索二叉树的遍历过程到这里应该能够很简单是理解

注：这里pre和p传进来的是引用。
void OrdThread(ThreadTree &p,ThreadTree &pre)
{

	if(P!=null)
	{
		#这里我们明白这些子树的访问都是在该节点之前进行的
		InThread(p-lchild,pre)   这里相当于访问当前节点左子树的所有节点
		
        Inthread(p->rchild,pre)  这里相当于访问当前节点右子树的所以节点
        
        {
		#这里面的代码相当于先序遍历的 visit()
		我们在遍历的过程中进行了建立线索的进行的操作如下；
		1：当“真在遍历节点的左子树为空我们将他的左指针指向刚刚访问过的那个节点”
		2：如果正在访问节点的前一个节点不为空，且前一个节点的右子树为空，就让前一个节点的右子树指针指向当前节点。
		3：当前节点访问操作以及实现，但是要将当前节点变成 下一个访问的节点的上一个节点，也就是将p赋值给pre指针。
			if(p->lclild==null)
			{
				p -> lchild = pre;
				p -> ltag = 1;
			}
		
			if(pre->rclild==null && pre!= null )
            {
                pre -> rchild = p;
                pre -> rtag = 1;
            }
            将当前节点设置为前
            pre = p;
		}
	}

}

2：修改createInthread（）函数，因为createtthread（）中{ pre->rchild = null; }这个步骤在后序中是不能直接使用的了，前边通过先序和中序的证明，也能够大致理解，如下证明后序线索二叉树：

void createInthread(ThreadTree T)
{	
	ThreadTree pre = null;
	if(T!=null)
	{	
		PostThread(T,pre);
		if(pre - > rtag == 1)
   	 	{
            pre->rchild = null;
       	}
	}
}

解释：关于{ pre->rchild = null; } 这里我们加了 if(pre - > rtag == 1)判断！！！！

问：为什么后序不能呢？

​ 第一步：我们从执行的角度分析：当结束PostThread（）函数执行后，pre指针是指向最后一个节点的，这里是无可置疑的，既然pre是指向最后一个遍历的节点所以最后一个节点的后边是空节点，因此 p 也就一定指向null。

​ 第二步：我们分析后序遍历：后序遍历是先遍历两个子树，再遍历根节点，如果最后一个节点有右子树的情况下，这个节点能成为最后一个被遍历的节点？这里很容易理解是可以的，无论有没有右子树后序遍历时我都是最后一个，所以我们需要通过最后一个节点的右子树被线索化的标注rtag来进行判断是否根节点右子树为空。

​ 第三步：当右子树为空时，pre->rtag 是等于1的，此时我们将pre指向的最后一个节点设置为空，将他线索化

​

pre的改进：

​ 我们发现，当我们遍历二叉树的时候pre一直是一个引用的存在，引用的意思可以理解为实参的别名，和实参实际是一个变量，所以这里pre做形参和实参表示相同含义，所以可以直接将pre声明为全局变量并初始化赋值为null。

2.1.2 遍历线索二叉树

​ 这一部分王道讲的很好，我只对中序进行讲解：

遍历中序线索二叉树

两个概念：

第一个概念：访问中序线索二叉树的中序序列下的第一个节点：

​

            ThreadNode *Firstnode(ThreadNode *p)   
            {	
                while(p->ltag == 0) p=p->lchild;  #
                return p;
            }

解释：p->ltag == 0，表示p的左子树非空，所以树p中访问的第一个节点是树p中最左的节点，树p中最左的节点的特征就是p的左子树的左子树的左子树…中第一个出现p->ltag==1的节点，在众多嵌套左子树中第一个没有左子树的节点。

第二个概念：求中序线索二叉树中节点P在中序序列下的后继：

            ThreadNode *Nextnode(ThreadNode *p)
            {
                if(p->rtag==0) return Firstnode(p->plchild);
                else return p->rchild;
            }

解释:求当前节点的p的后继节点；

​ 当他右子树不空的时候就找他右子树中最左的节点，也就是 他右子树的左子树的左子树的左子树…n层嵌套左子树中第一个左子树为空的左子树，刚好Firstnode（）函数就是在做这个操作。

​ 当他右子树空的时候，rchild就是代表指向后继的线索。

​

遍历给定根节点的中序线索二叉树按照中序线索遍历二叉树：

            void Inorder(ThreadNode *T)
            {
                for(ThreadNode *p = Firstode(t);p!=null;p=Nextnode(p))	
                        visit(p);
            }

解释：我们知道一颗树的根节点的时候遍历树的中序

​ 就是先找到这个树的第一个被访问的节点然后，然后对第一个访问到的节点求该节点后继的过程，以及求该节点后继的后继的过程，从而就可以用for循环加上上边的两个概念实现。