C语言-数据结构-线索二叉树

谁践踏了优雅 2022-12-26 14:26 164阅读 0赞

### C语言-数据结构-线索二叉树 ###

*  线索二叉树的定义
 *  线索二叉树建立
 *   *  定义结构体类型
     *  创建线索二叉树
     *  将二叉树中序线索化
 *  中序线索化二叉树的部分操作
 *   *  查找结点p的前驱
     *  查找结点p的直接后继
     *  ~~插入右结点~~
     *  ~~插入左结点~~
     *  ~~删除节点~~
 *  结语

# 线索二叉树的定义 #

若一个二叉树中含有n个结点,则它的二叉链表必有2n个指针域，其中必有n+1个空的链域（除根节点外每个结点提供2个结链域 消耗1个链域，而根节点只提供2个链域( n - 1 ) \* 1 + 2 = n + 1 ）  
利用二叉链表中的空链表，记录结点的前驱和后继.

# 线索二叉树建立 #

## 定义结构体类型 ##

typedef struct Node
    {
        
    	char data;
    	struct Node* LChild;
    	struct Node* RChild;
    	int Ltag;  //=1时记录的为结点前驱  否则为其左子树
    	int Rtag;  //=1时记录的为结点后继  否则为其右子树
    }BiTNode, * BiTree;

## 创建线索二叉树 ##

这部分程序应用了二叉树的中序遍历算法，与之前文章中的的创建方法类似

int exitdata = 0;//用于记录链表是否建立完
    void CreatBitree(BiTree* bt)      //基于遍历序列建立二叉链表
    {
        
    	char ch;
    
    	if (exitdata == 1)
    		return;
    	ch = getchar();
    
    	if (ch == '.')
    		*bt = NULL;
    	else if (ch == '\n')
    	{
        
    		*bt = NULL;
    		exitdata = 1;
    	}
    	else
    	{
        
    		*bt = (BiTree)malloc(sizeof(BiTNode));
    		(*bt)->data = ch;
    		(*bt)->LChild = NULL;
    		(*bt)->Ltag = 0;
    		(*bt)->RChild = NULL;
    		(*bt)->Rtag = 0;
    		CreatBitree(&((*bt)->LChild));
    		CreatBitree(&((*bt)->RChild));
    	}
    
    }

## 将二叉树中序线索化 ##

BiTNode* pred = NULL;     //用于指向前一结点 初始为空
    void Inthread(BiTree root)   //利用中序遍历线索化二叉树
    {
        
    	if (root != NULL)
    	{
        
    		Inthread(root->LChild);
    		if (root->LChild == NULL) //如果左节点为空，则将他指向前一结点
    		{
        
    			root->Ltag = 1;
    			root->LChild = pred;
    		}
    		if (pred != NULL && pred->RChild == NULL)
    		//如果pred结点的右节点为空,则将其指向pred的后一结点即root结点
    		{
        
    			pred->Rtag = 1;
    			pred->RChild = root;
    		}
    		pred = root;
    		Inthread(root->RChild);
    	}
    }

其他遍历方式线索化二叉树 程序类似;

# 中序线索化二叉树的部分操作 #

## 查找结点p的前驱 ##

BiTNode* Inpre(BiTNode* p)   //在中序线索二叉树中查找p的前驱
    {
        
    	BiTNode* q, * pre;
    	if (p->Ltag == 1)
    		pre = p->LChild;
    	else
    	{
        
    		for (q = p->LChild; q->Rtag == 0; q = q->RChild);
    		pre = q;
    	}
    	return pre;
    }

## 查找结点p的直接后继 ##

BiTNode* InSucc(BiTNode* p)  //在中序线索二叉树中查找p的后驱
    {
        
    	BiTNode* q, * succ;
    	if (p->Rtag==1)
    	{
        
    		succ = p->RChild;
    	}
    	else
    	{
        
    		for (q = p->RChild; (q != NULL) && (q->Ltag == 0); q = q->LChild);
    		succ = q;
    	}
    	return succ;
    
    }

## 插入右结点 ##

## 插入左结点 ##

## 删除节点 ##

# 结语 #

先留几个坑，有空来填。  
还有二叉搜索树，平衡搜索树，树，森林太难了.

[C语言-数据结构-二叉树-遍历][C_-_-_-]

[C_-_-_-]: https://blog.csdn.net/qq_49122758/article/details/110247296