中序线索二叉树

不念不忘少年蓝@ 2023-03-01 05:50 90阅读 0赞

线索化二叉树，实质上就是将空闲指针充分利用起来，使其保存二叉树的某种遍历序列，而中序线索二叉树则保存的是中序遍历  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjAxMzM4_size_16_color_FFFFFF_t_70][]  
为了实现这一操作，我们对二叉树的节点结构做了一点改变，加入左右标志Ltag,Rtag，用来标志节点左右孩子是否为空

template<typename T>
    struct Binode {
        
    	T data;
    	Binode<T>* Lchild;
    	Binode<T>* Rchild;
    	int Ltag, Rtag;
    };

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjAxMzM4_size_16_color_FFFFFF_t_70 1][]  
在遍历过程中，访问当前结点bt的操作为：  
⑴如果bt的左、右指针域为空，则将相应标志置1；  
⑵若root的左指针域为空，则令其指向它的前驱，这需要设指针pre始终指向刚刚访问过的结点，显然pre的初值为NULL；若pre的右指针域为空，则令其指向它的后继，即当前访问的结点root;  
⑶ 令pre指向刚刚访问过的结点root；  
接下来是具体的线索化函数代码：

template<typename T>
    void BiTree<T>::InTread(Binode<T>* bt)
    {
        
    	Binode<T>* root = bt;
    	if (root)
    	{
        
    		InTread(root->Lchild);
    		if (!root->Lchild)   //没有左子树
    		{
        
    			root->Ltag = 1;  //给该节点加上线索
    			root->Lchild = pre<T>;  //左孩子指向前驱节点pre
    		}
    		else
    			root->Ltag = 0;
    		if (!pre<T>->Rchild)//没有右子树
    		{
        
    			pre<T>->Rtag = 1;//给该节点加上线索
    			pre<T>->Rchild = root;//右孩子指向后继root
    		}
    		else
    			root->Rtag = 0;
    		pre<T> = root;//更新Pre
    		InTread(root->Rchild);//右子树线索化
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjAxMzM4_size_16_color_FFFFFF_t_70]: /images/20230209/86007e1860b349019e4d1349fbae5ab6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjAxMzM4_size_16_color_FFFFFF_t_70 1]: /images/20230209/a4d93c5324894f6bb3492af2c2138a5b.png