《数据结构与算法》——树与二叉树之线索二叉树总结

旧城等待， 2021-10-29 15:08 379阅读 0赞

# 《数据结构与算法》——树与二叉树之线索二叉树总结 #

线索二叉树这部分单独提出来进行一次复习，原因很简单，去年这一块把我搞蒙了，现在回想起来数据结构这门课还有那么几个概念、结构和算法在梦中久久环绕不能离去，恐怖如斯，难瘦如斯，说这些内容给我幼小的心灵造成了一定量的伤害，这一点都不假！

定义

操作方法

算法实现

总结

参考文献

--------------------

## 定义 ##

什么是线索二叉树？字面意思，在二叉树里加入了一些线索。**啥线索？干哈用的？线索放哪里？**（素质三连问）

**啥线索？**在遍历二叉树的时候每个结点都会有一个直接前驱结点和直接后继结点（除首尾两个），线索指的就是前后两个结点。

**干哈用的？**回到上面的一段话，如何在遍历序列中查找两个结点呢？遍历一遍然后再进行查找？太慢了而且不方便，难道查询一个点就遍历一次？如果说我们把前驱结点和后继结点记录下来那么查找速度会不会更快哩？

**线索放哪里？**不难发现原来二叉树的定义是两个指针加一个数据，两个指针分别指向左右两个子树。但是！不是每个结点都有子树，至少不是每个结点都有两个子树，那么它们的指针指向了哪里？NULL。空指针，不就有点浪费了嘛，把空指针指向前后两个结点，正好用上。那问题又来了，有的指针指向的是子树，有的指针指向的前后结点，那不就乱了套了吗？不乱，加上两个标记变量就不乱了，以左标记变量为例，0代表指向左孩子，1代表指向前驱结点，右标记变量同理。

把此时线索二叉树的结点结构图形化如下：

<table> 
 <tbody> 
  <tr> 
   <td style="vertical-align:top;width:82.95pt;"> <p style="margin-left:0cm;">ltag</p> </td> 
   <td style="vertical-align:top;width:82.95pt;"> <p style="margin-left:0cm;">lchild</p> </td> 
   <td style="vertical-align:top;width:82.95pt;"> <p style="margin-left:0cm;">data</p> </td> 
   <td style="vertical-align:top;width:82.95pt;"> <p style="margin-left:0cm;">rchild</p> </td> 
   <td style="vertical-align:top;width:83pt;"> <p style="margin-left:0cm;">rtag</p> </td> 
  </tr> 
 </tbody> 
</table>

代码描述如下：

typedef struct ThreadNode{
    	ElemType data;
    	struct ThreadNode *lchild,rchild;
    	bool ltag,rtag;
    }ThreadNode,*ThreadTree;

## 操作方法 ##

void visit(ThreadTree b);//访问结点
    
    ThreadTree creatBiTree(Elemtype tree[] , int n , int num );//顺序存储·建立·链式二叉树 
    
    /***********************************************************************************/
    
    void InOrder2(ThreadTree T);//中序遍历.普通递归（InOrder）
    
    ThreadTree InThread(ThreadTree tree, ThreadTree pre);//以中序遍历构造线索二叉树 
    
    ThreadTree CreatePreThread(ThreadTree tree);//以前序遍历构造线索二叉树主算法 
    
    ThreadTree CreateInThread(ThreadTree tree);//以中序遍历构造线索二叉树主算法 
    
    ThreadTree FirstNode(ThreadTree tree);//中序·线索化·最左下结点
    
    ThreadTree NextNode(ThreadTree tree);//中序·线索化·下一结点
    
    ThreadTree LastNode(ThreadTree tree);//中序·线索化·最后结点
    
    ThreadTree PreNode(ThreadTree tree);//中序·线索化·前结点
    
    void InOrder(ThreadTree tree);//中序·线索化·遍历 
    
    /***********************************************************************************/
    
    void PreOrder2(ThreadTree T);//先序遍历·普通递归（PreOrder）
    
    ThreadTree PreThread(ThreadTree tree, ThreadTree pre);//先序·线索化·构造
    
    ThreadTree PreNextNode(ThreadTree tree);//先序·线索化·下一结点
    
    ThreadTree PreLastNode(ThreadTree tree);//先序·线索化·尾结点 
    
    ThreadTree PreFirstNode(ThreadTree tree);//先序·线索化·根部结点
    
    ThreadTree PrePreNode(ThreadTree tree);//先序·线索化·前结点
    
    void PreOrder(ThreadTree tree);//先序·线索化·遍历

## 算法实现 ##

void visit(ThreadTree b){//访问结点
    	if(b)
    		cout<<b->data<<"\t";
    	else
    		cout<<"NULL\t";
    }
    
    void InOrder2(ThreadTree T){//中序遍历.递归（InOrder）
    	if(T){
    		InOrder2(T->lchild);
    		visit(T);
    		InOrder2(T->rchild);
    	}
    }
    
    ThreadTree creatBiTree(Elemtype tree[] , int n , int num ){//使用顺序存储结构建立链式存储结构二叉树 
    	if(n<num||tree[num]==0)//超过结点个数限制或该点是空结点
    		return NULL;
    	//该点不是空结点 
    	
    	ThreadTree T = (ThreadTree)malloc(sizeof(ThreadNode));
    	T->data = tree[num];
    	T->lchild =  creatBiTree (tree,n,num*2); 
    	T->rchild =  creatBiTree (tree,n,num*2+1);
    	T->ltag = 0;
    	T->rtag = 0;
    	//cout<<T->data<<endl;
    	return T;	
    }
    
    ThreadTree InThread(ThreadTree tree, ThreadTree pre){//以中序遍历构造线索二叉树 
    	//现在输入的tree初始值为一棵带标记但未初始化标记的二叉树
    	//运行结果为对标记进行初始化 
    	if(tree){//当前结点不是空结点 
    		pre = InThread(tree->lchild,pre); //递归遍历左子树 
    		if(!tree->lchild){//若左子树为空 
    			tree->lchild = pre; 
    			tree->ltag = 1;
    		}
    		if(pre&&!pre->rchild){//添加前结点的右指针 
    			pre->rchild = tree;
    			pre->rtag = 1 ; 
    		}
    		pre = tree ;//当前结点为下一结点的前结点 
    		pre = InThread(tree->rchild,tree);//递归遍历右子树 
    	} 
    	return pre; 
    }
    
    ThreadTree PreThread(ThreadTree tree, ThreadTree pre){//以前序遍历构造线索二叉树 
    	//现在输入的tree初始值为一棵带标记但未初始化标记的二叉树
    	//运行结果为对标记进行初始化 
    	if(tree){//当前结点不是空结点 
    		if(!tree->lchild){//左结点为空 
    			tree->lchild = pre; //把当前结点插入 
    			tree->ltag = 1;	
    		}
    		
    		if(pre&&!pre->rchild){//添加前结点的右指针 
    			pre->rchild = tree;
    			pre->rtag = 1 ; 
    		}
    		pre = tree ;//当前结点为下一结点的前结点 
    		if(tree->ltag==0)
    			pre = PreThread(tree->lchild,pre); //递归遍历左子树 
    		if(tree->rtag==0)
    		pre = PreThread(tree->rchild,pre);//递归遍历右子树 
    	} 
    	return pre; 
    }
    
    ThreadTree CreatePreThread(ThreadTree tree){//以先序遍历构造线索二叉树主算法 
    	ThreadTree pre = NULL;
    	if(tree){
    		pre = PreThread(tree,pre);
    		pre->rchild = tree;//处理尾结点 
    		pre->rtag = 2;
    	}
    	return tree;
    }
    
    ThreadTree CreateInThread(ThreadTree tree){//以中序遍历构造线索二叉树主算法 
    	ThreadTree pre = NULL;
    	if(tree){
    		pre = InThread(tree,pre);
    		pre->rchild = NULL;//处理尾结点 
    		pre->rtag = 1;
    	//	cout<<"Creat Over!!!"<<endl;
    	}
    	return tree;
    }
    
    ThreadTree FirstNode(ThreadTree tree){//查找当前结点的最左下结点
    	//中序遍历顺序左-中-右
    	if(tree->ltag==0)
    		return FirstNode(tree->lchild);
    	else
    		return tree;
    }
    
    ThreadTree NextNode(ThreadTree tree){//查找当前结点的下一结点
    	//中序遍历顺序左-中-右
    	if(tree->rtag==0)
    		return FirstNode(tree->rchild);//右子结点的最左下结点即为当前结点的下一结点 
    	else
    		return tree->rchild;
    }
    
    ThreadTree LastNode(ThreadTree tree){//查找当前结点的最后结点
    	//中序遍历顺序左-中-右
    	ThreadTree temp = FirstNode(tree);
    	ThreadTree t = NextNode(temp);
    	if(!t)
    		return temp; 
    	for( ; t ;temp = t , t = NextNode(temp));//从右向左执行 
    		return temp; 
    }
    
    ThreadTree PreNode(ThreadTree tree){//查找当前结点的最后结点
    	//中序遍历顺序左-中-右
    	if(tree->ltag==0)
    		return NextNode(tree->lchild);
    	else 
    		return tree->lchild; 
    }
    
    void InOrder(ThreadTree tree){//遍历中序线索二叉树 
    	for(ThreadTree temp = FirstNode(tree)  ; temp;temp = NextNode(temp))
    		visit(temp);
    }
    
    /********************************************************************/
    
    ThreadTree PreNextNode(ThreadTree tree){//查找当前结点的下一结点
    	//先序遍历顺序中-左-右
    	if(tree->ltag==0)
    		return tree->lchild;//存在左子树 
    	else 
    		return tree->rchild;//无论rtag的标记是什么，右指针指向的结点总为下一结点 
    }
    
    ThreadTree PreLastNode(ThreadTree tree){//先序·线索化·尾结点 
    	if(tree->rtag!=2)
    		return PreLastNode(tree->rchild);
    	return tree;
    }
    
    ThreadTree PreFirstNode(ThreadTree tree){//查找当前结点的最根部结点
    	//先序遍历顺序中-左-右
    		return PreLastNode(tree)->rchild;//尾结点的rchild被标记为根结点 
    }
    
    ThreadTree PrePreNode(ThreadTree tree){//查找当前结点的最根部结点
    	if(tree->ltag==1)
    		return tree->lchild;
    	ThreadTree temp = (ThreadTree)malloc(sizeof(ThreadNode));
    	ThreadTree pre;
    	temp = PreFirstNode(tree);
    	if(temp==tree)
    		return NULL;
    	pre = temp;
    	temp = PreNextNode(temp);
    	while(temp->data!=tree->data){
    		pre = temp;
    		temp = PreNextNode(temp);
    	}
    	return pre;	
    }
    
    void PreOrder(ThreadTree tree){//先序·线索化·遍历 
    	ThreadTree temp = PreFirstNode(tree);  	
    	for( ;temp->rtag!=2;temp = PreNextNode(temp))
    		visit(temp);
    	visit(temp); 	
    }
    
    void PreOrder2(ThreadTree T){//先序遍历·递归（PreOrder）
    	//cout<<(T==0)<<endl;
    	if(T){
    		visit(T);
    		//cout<<555<<endl;
    		PreOrder2(T->lchild);
    		PreOrder2(T->rchild);
    	}
    }

**测试函数**

/*编译环境：
    win10专业版
    DEV C++ 5.11
    TDM-GCC 4.9.2 64bit
    */
    
    #include<iostream>
    #include "malloc.h"
    #include<queue>
    #include<stack>
    
    using namespace std;
    
    typedef char Elemtype ;
    /*在此处添加结构体定义和各个方法的实现*/
    int main(){
    	ThreadTree T = (ThreadTree)malloc(sizeof(ThreadNode));
    	ThreadTree newT = (ThreadTree)malloc(sizeof(ThreadNode));
    	Elemtype A[30]= {0,'A',
    					 'B','D',
    					 0,'C','E','F',
    					 0,0,0,0,0,0,'G','I',
    					 0,0,0,0,0,0,0,0,0,0,0,0,0,'H'};
    	T = creatBiTree(A,29,1);//构建tag未初始化的二叉树 
    	cout<<endl<<"中序遍历二叉树    :\t";InOrder2(T);
    	T = CreateInThread(T);//构建中序的线索二叉树 
    	cout<<endl<<"访问第一个结点    :\t";visit(FirstNode(T));
    	cout<<endl<<"访问根结点上一结点:\t";visit(PreNode(T));
    	cout<<endl<<"访问根结点下一结点:\t";visit(NextNode(T));
    	cout<<endl<<"访问最后一个结点  :\t";visit(LastNode(T));
    	cout<<endl<<"遍历中序线索二叉树:\t";InOrder(T);//遍历中序线索二叉树 
    	
    	cout<<endl<<endl<<"********************************************************************"<<endl;
    	
    	newT = creatBiTree(A,29,1);//构建tag未初始化的二叉树 
    	cout<<endl<<"前序遍历二叉树    :\t";PreOrder2(newT);
    	newT = CreatePreThread(newT);//构建中序的线索二叉树 
    	cout<<endl<<"访问当前结点的首点:\t";visit(PreFirstNode(newT));
    	cout<<endl<<"访问根结点上一结点:\t";visit(PrePreNode(newT));
    	cout<<endl<<"访问根结点下一结点:\t";visit(PreNextNode(newT));
    	cout<<endl<<"访问最后一个结点  :\t";visit(PreLastNode(newT));
    	cout<<endl<<"遍历前序线索二叉树:\t";PreOrder(newT);//遍历中序线索二叉树
    	return 0;
    }

## 总结 ##

通过一天半的学习，线索化二叉树这一部分难度不是很高，难理解的点就是线索二叉树的结构，当两个标记分别为0/1时代表什么含义，什时候指向的是子树，什么时候是指向的前驱后继结点。而线索化这一操作是分为三种情况的：先序线索化、中序线索化、后续线索化，每种线索化出的二叉树又有各自特定的遍历方法，想象一下，对于一个满二叉树的先序线索化出来的结果，最左下结点的左孩子指向的是它的前驱节点——NULL，而中序线索化出来的结果，其指向的应该为其双亲结点。

原来理解的是任何一种线索化出的结果均可根据线索化的指针关系进行任意一种遍历，这是不能进行的！

但是它又能进行任意一种遍历的，只看tag=0时的结点指针，对于线索化的指针不予理会，那这就是普通的二叉树遍历。

## 参考文献 ##

1.  严蔚敏，吴伟民. 数据结构（C语言版）\[M\]. 北京： 清华大学出版社，2013.
2.  王道论坛 2019年数据结构考研复习指导\[M\]. 北京： 电子工业出版社，2018.