中序线索二叉树（构建，遍历和找前驱后继节点）附c++详细解释代码！

￡神魔★判官ぃ 2023-05-30 06:30 4阅读 0赞

在二叉树的结点上加上线索的二叉树称为**线索二叉树**，对二叉树以某种遍历方式（如先序、中序、后序或层次等）进行遍历，使其**变为线索二叉树**的过程称为对**二叉树进行线索化**

**线索化二叉树的本质**，实际上是对原始二叉树中的指向为空（NULL）的指针域进行利用，我们让其指向为NULL的指针域指向前驱（左孩子）或者是后继（右孩子），但是我们**怎么来辨别是树节点还是指向其前驱还是后继呢**？

**核心思想：**

我们**为每一个树节点增加两个标志域lThread和rThread**，如果左子树是指向的**是线索（前驱），那么lThread为true**,如果**指向的是树节点，那么lThread为false 。同理，如果右子树指向的**是线索（后继），那么rThread为true\*\*,如果**指向的树节点，那么rThread为false。**

**在了解了线索化二叉树的核心思想之后，我们怎么来构建一颗线索化二叉树呢？**

*  1、我们先构建一颗树，然后再按某种遍历来线索化它，我们这里实现的是**中序遍历** 来线索化这棵二叉树。
 *  2、构建完成之后，我们将这棵树线索化的同时，给这棵树加一个头结点head，目的是为了方便操作。
 *  3、最后**遍历的输出线索化二叉树**，以及**查找节点的前驱后继**

##### 代码实现及详细解释如下： #####

**1、定义树的节点：**

class binThiTree {
    public:
    	char value;//树节点的值
    	binThiTree* lchild;//左子树
    	binThiTree* rchild;//右子树
    	bool lThread;//等于true，说明是左线索，等于false,说明是左孩子
    	bool rThread;//等于true，说明是右线索，等于false，说明是右孩子
    	binThiTree() {};
    	binThiTree(char value) {
    		//构造函数，初始化
    		this->value = value;
    		this->lchild = NULL;
    		this->rchild = NULL;
    		this->lThread = false;//初始值为false
    		this->rThread = false;//初始值为false
    	}
    };

**2、我们用先序遍历顺序来构建一颗二叉树**:  
**这里需要注意的是，传入的根节点是指针引用！**  
*指针引用和指针是不一样的，是有区别的！*

/*
    我们用先序遍历的方法来创建一颗二叉树,以#符号结束，此时将根节点复制为NULL,即可
    */
    void creatBinTree(binThiTree* &root) {
    	char ch = '0';
    	cin >> ch;
    	if (ch == '#') {
    		//递归的结束条件
    		root = NULL;
    		return;
    	}
    	else {
    		root = new binThiTree(ch);
    		//递归创建左子树
    		creatBinTree(root->lchild);
    		//递归创建右子树
    		creatBinTree(root->rchild);
    	}
    }

**3、创建好二叉树之后，我们先来讲讲如何将一颗二叉树按中序遍历的顺序来线索化**  
*线索化的过程实际上找那些左右子树为空的前驱后继，我定义了一个全局变量pre来指向上一次访问的节点，还有一个指向当前节点的指针cur,这样线索化的过程就转化成了cur 和 pre之间的指向关系：*

**代码实现的核心思路：**  
**当当前节点cur没有左子树的时候，那么cur->lchird应该指向前驱，而前驱就是上一次访问的节点，也就是\*pre.**  
**当上一次访问的节点没有右孩子的时候，那么此时pre->rchild应该指向其后继，也就是\*cur.**

**线索化的时候，我们先线索化左子树，然后在线索化右子树**

//创建一个指向上一个访问的节点的指针
    binThiTree* pre = NULL; // 需要是全局变量，永远指向上一次访问的节点
    
    void traverThiLDR(binThiTree* root) {
    
    	//中序线索化的过程其实是对树的每一个节点找前驱和后继的一个过程，
    	
    	binThiTree* cur = root;//创建一个指向当前节点的指针，并且赋值为root
    
    	if (cur != NULL) {
    		//先线索化左子树
    		traverThiLDR(cur->lchild);
    		
    		if (cur->lchild == NULL) {//当前结点没有左孩子
    			cur->lThread = true;
    			cur->lchild = pre;//左子树指向前驱
    		}
    
    		if (pre->rchild == NULL) {//上一次访问的节点没有右孩子
    			pre->rThread = true;
    			pre->rchild = cur;//右子树指向后继
    		}
    		
    		pre = cur;//pre永远指向上一次访问的节点
    		
    		//然后线索化右子树
    		traverThiLDR(cur->rchild);
    	}
    }

**4、我们创建一个头结点将线索化二叉树链接起来，形成一个“环形链表”**

/*
    我们设置一个头结点，让头结点的左孩子指向二叉树的根节点，左子树的lflag为false
    然后让头结点head的右子树指向二叉树的最右的左子树。右子树的rflag为true.
    同时我们让二叉树的最左边的节点的左子树指向头结点，最右边的右子树指向头结点，
    这样就形成了一个环形的线索化二叉树了。方便查找前驱和后继
    */

void creatThiTree(binThiTree* root,binThiTree* &head) {
    	head->rThread = true;//有指针指向线索
    	if (root == NULL) {
    		//如果二叉树为NULL,说明无法线索化
    		head->lchild = head;
    		head->lThread = false;
    		head->lchild = NULL;
    	}
    	else {
    		pre = head;//目的是：在中序线索化二叉树的时候，将二叉树的最左边的节点指向head
    		head->lThread = false;
    		head->lchild = root;
    		
    		traverThiLDR(root);//中序线索化二叉树
    
    		pre->rThread = true;
    		pre->rchild = head;//二叉树的最右边的节点
    
    		head->rchild = pre;
    	}//这样就实现了中序二叉树的构建。
    }

**这样就构建成功了中序线索化二叉树。**

**5、接下来是中序线索二叉树的遍历**  
*遍历的总体思路就是：*  
先找到最左边的节点，然后判断其右子树是否为线索，如果是线索，那么就遍历它，如果右子树是右孩子，那么就进入到右孩子的最左边的节点，进行同样的判断，知道遍历完了整棵树为止。  
**代码实现如下：**

void traverThiTree(binThiTree* head) {
    
    	binThiTree* p = head->lchild;//指向头结点的左子树，就是二叉树的根节点
    	
    	while (p != head) {//循环停止条件是遍历完整棵树回到头结点的时候。
    		
    		while (p->lThread == false) {  //目的是为了找打二叉树的最左边的点
    
    			p = p->lchild;
    		}
    
    		cout << " " << p->value;//此时p指向最左边的节点
    
    		//然后开始读取后继
    		while (p->rThread == true && p->rchild != head) {//当节点的右子树为线索时说明为后继，如果不为线索，就是右子树退出循环
    			
    			p = p->rchild;
    
    			cout << " " << p->value;
    		}
    		
    		p = p->rchild;
    	}
    
    }

**6、在生成了线索化二叉树之后，查找某个结点的前驱或者是后继都变的简单起来**  
如果是普通二叉树，我们就需要遍历整颗树才能找到某个结点的前驱和后继，线索化二叉树之后，查找前驱和后继都变得简单起来

**查找某个结点的前驱代码如下：**

binThiTree* preTreeNode(binThiTree* q) {
    	binThiTree* cur;
    	cur = q;
    	if (cur->lThread == true) {
    		cur = cur->lchild;
    		return cur;
    	}else{
    		//进入*cur的左子树
    		cur = cur->lchild;
    
    		while (cur->rThread == false) {
    			cur = cur->rchild;
    		}
    		return cur;
    	}
    }

**查找某个结点的后继代码如下：**

binThiTree* rearTreeNode(binThiTree* q) {
    	binThiTree* cur = q;
    	if (cur->rThread == true) {
    		cur = cur->rchild;
    		return cur;
    	}
    	else {
    		//进入到*cur的右子树
    		cur = cur->rchild;
    
    		while (cur->lThread == false) {
    			cur = cur->lchild;
    		}
    		return cur;
    	}
    }

**可以看出，在二叉树进行线索化之后，对于遍历和查找的操作都简单了不少！**

有问题欢迎在评论留言！