线索二叉树的建立与遍历（C语言）

以你之姓@ 2023-01-17 10:40 123阅读 0赞

当我们建立普通的二叉树时，无法找到它的前驱与后继结点，而通过线索化二叉树，我们则可以轻松实现以上算法。

此处通过建立中序线索二叉树而实现了中序遍历。

代码如下：

#include<stdio.h>
    #include<stdlib.h>
    
    typedef struct Node
    {
        
    	char data;
    	struct  Node* LChild, * RChild;
    	int Ltag, Rtag;  //1表示前驱或后继
    }BiNode, * BiTree;
    
    BiTree CreateTree();      //建立二叉树
    void Inthread(BiTree T, BiTree& pre);  //中序线索化二叉树
    void PreThread(BiTree T, BiTree& pre);   //先序线索化二叉树
    void PostThread(BiTree T, BiTree& pre);   //后序线索化二叉树
    BiTree InPre(BiTree T);   //在中序二叉树寻找特定结点T前驱
    BiTree InNext(BiTree T);  //在中序二叉树寻找特定结点T后继
    BiTree InFirst(BiTree T); //找到中序线索化二叉树的第一个遍历结点
    void InOrder(BiTree T);   //遍历中序线索化二叉树
    
    
    
    int main()
    {
        
    	BiTree T;
    	T = CreateTree();
    	InOrder(T);
    	return 0;
    }
    
    BiTree CreateTree()
    {
           //建立二叉树
    	char ch;
    	ch = getchar();
    	BiTree T;
    	if (ch == '#') {
        
    		return NULL;
    	}
    	else {
        
    		T = (BiTree)malloc(sizeof(BiNode));
    		if (T == NULL) {
        
    			printf("error1\n");
    			return NULL;
    		}
    		T->data = ch;
    		T->Ltag = 0;
    		T->LChild = CreateTree();
    		T->Rtag = 0;
    		T->RChild = CreateTree();
    	}
    	return T;
    }
    
    void Inthread(BiTree T, BiTree& pre)
    {
           //中序线索化二叉树
    	//与中序遍历普通二叉树做法基本一致
    	if (T != NULL) {
        
    		Inthread(T->LChild, pre);
    		if (T->LChild == NULL) {
        
    			T->Ltag = 1;
    			T->LChild = pre;
    		}
    		if (pre != NULL && pre->RChild == NULL) {
        
    			pre->RChild = T;
    			pre->Rtag = 1;
    		}
    		pre = T;
    		Inthread(T->RChild,pre);
    	}
    }
    
    void PreThread(BiTree T, BiTree &pre)
    {
           //先序线索化二叉树
    	if (T != NULL) {
        
    		if (T->LChild == NULL) {
        
    			T->Ltag = 1;
    			T->LChild = pre;
    		}
    		if (pre != NULL && pre->RChild == NULL) {
        
    			pre->RChild = T;
    			pre->Rtag = 1;
    		}
    		pre = T;
    		PreThread(T->LChild, pre);
    		PreThread(T->RChild, pre);
    	}
    }
    
    void PostThread(BiTree T, BiTree &pre)
    {
           //后序线索化二叉树
    	if (T != NULL) {
        
    		PostThread(T->LChild, pre);
    		PostThread(T->RChild, pre);
    		if (T->LChild == NULL) {
        
    			T->Ltag = 1;
    			T->LChild = pre;
    		}
    		if (pre != NULL && pre->RChild == NULL) {
        
    			pre->RChild = T;
    			pre->Rtag = 1;
    		}
    		pre = T;
    	}
    }
    
    BiTree InPre(BiTree T)
    {
           //在中序二叉树寻找特定结点T前驱
    	//对中序线索化二叉树，其前驱结点一定在其左子树方向
    	BiTree pre, tmp;
    	if (T->Ltag == 1) {
        
    		pre = T->LChild;
    	}
    	else {
        
    		for (tmp = T->LChild; tmp->Rtag == 0; tmp = tmp->RChild);
    		pre = tmp;
    	}
    	return pre;
    }
    
    BiTree InNext(BiTree T)
    {
           //在中序二叉树寻找特定结点T后继
    	//中序线索化二叉树，其后继结点一定是其右子树或其右子树的左子树方向
    	BiTree next, tmp;
    	if (T->Rtag == 1) {
        
    		next = T->RChild;
    	}
    	else {
        
    		if (T->RChild == NULL) {
        
    			return NULL;
    		}
    		for (tmp = T->RChild; tmp->Ltag == 0; tmp = tmp->LChild);
    		next = tmp;
    	}
    	return next;
    }
    
    BiTree InFirst(BiTree T)
    {
           //找到中序线索化二叉树的第一个遍历结点
    	BiTree tmp;
    	tmp = T;
    	if (!tmp) {
        
    		return NULL;
    	}
    	while (tmp->Ltag == 0) {
        
    		tmp = tmp->LChild;
    	}
    	return tmp;
    }
    
    void InOrder(BiTree T)
    {
           //遍历中序线索化二叉树
    	BiTree pre = NULL;
    	Inthread(T, pre);
    	BiTree tmp;
    	tmp = InFirst(T);
    	while (tmp) {
        
    		printf("%c", tmp->data);
    		tmp = InNext(tmp);
    	}
    }

运行截图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MzA2ODI2OQ_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MzA2ODI2OQ_size_16_color_FFFFFF_t_70]: /images/20221021/2b90653957aa4fb4800fd53f3d49ec84.png