c/c++数据结构线索二叉树(408)

发布于：2023-01-18 ⋅ 阅读:(492) ⋅ 点赞:(0)

提示：下面案例可供参考

一、线索二叉树

        遍历二叉树是以一定的规则将二叉树中的结点排列成一个线性序列。从而得到几种遍历序列，使得该序列中的每个结点(第一个和最后一 个结点除外) 都有一个直接前驱和直接后继。

        传统的二叉链表存储仅能体现一种父子关系，不能直接得到结点在遍历中的前驱或后继。在含n个结点的二叉树中，有n+1个空指针。这是因为每个叶结点有2个空指针，每个度为1的结点有1个空指针，空指针总数为2n0+n1, 又no=n2+1,所以空指针总数为n0+n1+n2+1=n+1。由此设想能否利用这些空指针来存放指向其前驱或后继的指针?

        这样就可以像遍历单链表那样方便地遍历二叉树。所以引入线索叉树正是为了 加快查找结点前驱和后继的速度。规定:若无左子树，令lchild指向其前驱结点；若无右子树，令rchild指向其后继结点。

二、线索二叉树的实现

1.存储结构和一些必要的函数基础

 线索二叉树的存储结构（这里用的编译环境是devc++）

#include<bits/stdc++.h>
using namespace std;
typedef struct ThreadTNode{ // 线索二叉树 struct 
    char data;
    int ltag;  //0 表示指向的是 左 右 结点  1 表示指向的是 前驱 后继 
    int rtag;
    struct ThreadTNode * lchild;    
    struct ThreadTNode * rchild;
}ThreadNode,*ThreadTree; 
ThreadTree prebuild(){         //先序建立二叉树 (不是线索)
    char s; scanf("%c",&s);
    if(s!='#'){
        ThreadTNode *p=(ThreadTNode *)malloc(sizeof(ThreadNode)); //c++用new
        p->data=s;  p->lchild=prebuild();    p->rchild=prebuild();
        p->ltag=0;p->rtag=0; 
        return p;    }
    return NULL;   
}
void PreOrder(ThreadTree t){  //先序遍历 
    if(t!=NULL){
        printf("%c",t->data);
        if(t->ltag==0)    PreOrder(t->lchild);
        if(t->rtag==0)    PreOrder(t->rchild);
    }
}
void LevelOrder(ThreadTree t){   //层序遍历 
    queue<ThreadTree> q;
    q.push(t);
    ThreadTNode *s;
    while(!q.empty()){
        s=q.front();
        if(s->ltag==0&&s->lchild!=NULL) q.push(s->lchild);
        if(s->rtag==0&&s->rchild!=NULL) q.push(s->rchild);    
        cout<<s->data<<s->ltag<<s->rtag<<" ";  //用于查看线索二叉树
        q.pop();
    }
    printf("\n");
}
void deletetree(ThreadTree t){  //后序的思想 销毁 树
    if(!t){
        if(t->ltag==0) deletetree(t->lchild);
        if(t->rtag==0) deletetree(t->rchild);
        free(t);
    }
}

创建一个二叉树 :

int main(){
	ThreadTree T;   T=prebuild();
	PreOrder(T);printf("\n");
	LevelOrder(T);
	deletetree(T);	
	return 0;
}

 输入：ABD##E##CF###

 输出：

2.线索二叉树的实现

先序线索二叉树的实现：

/先序 线索化
void PreThread(ThreadTree t,ThreadTree &pre) {
    if(t!=NULL){
        if(t->lchild==NULL){  //前驱 
            t->lchild=pre;
            t->ltag=1;
        }
        if(pre!=NULL&&pre->rchild==NULL){
            pre->rchild=t;     //后继 
            pre->rtag=1;
        }
        pre=t;
        if(t->ltag==0)    PreThread(t->lchild,pre);
        if(t->rtag==0)    PreThread(t->rchild,pre); 
    }
}
void CreatePreThread(ThreadTree t){
    ThreadTree pre=NULL;//指针 
    if(t!=NULL){ 
        PreThread(t,pre);
        pre->rchild=NULL;   //处理最后一个结点
        pre->rtag=1;
    }
        cout<<"先序线索化完成--------\n"; 
}

 中序线索二叉树的实现：

//中序 线索化
void InThread(ThreadTree t,ThreadTree &pre) {   
    if(t!=NULL){
        InThread(t->lchild,pre);
        if(t->lchild==NULL){  //前驱 
            t->lchild=pre;
            t->ltag=1;
        }
        if(pre!=NULL&&pre->rchild==NULL){
            pre->rchild=t;     //后继 
            pre->rtag=1;
        }
        pre=t;
        InThread(t->rchild,pre); 
    }
}
void CreateInThread(ThreadTree t){
    ThreadTree pre=NULL;//指针 
    if(t!=NULL){ 
        InThread(t,pre);
        pre->rchild=NULL;
        pre->rtag=1;
    }
    cout<<"中序线索化完成--------\n"; 
}

 后序线索二叉树的实现

/后序 线索化 
void PostThread(ThreadTree t,ThreadTree &pre) {
    if(t!=NULL){
        if(t->ltag==0)    //这里的if是没必要的  只是写了强调一下 
            PostThread(t->lchild,pre);
        if(t->rtag==0)  PostThread(t->rchild,pre);
        if(t->lchild==NULL){  //前驱 
            t->lchild=pre;
            t->ltag=1;  }
        if(pre!=NULL&&pre->rchild==NULL){
            pre->rchild=t;     //后继 
            pre->rtag=1;    }
        pre=t;
    }
}
void CreatePostThread(ThreadTree t){
    ThreadTree pre=NULL;//指针 
    if(t!=NULL){ 
        PostThread(t,pre);
        //最后的是指向根节点  根节点没有空余的指针 
    }
        cout<<"后序线索化完成--------\n"; 
}

C语言不支持参数&   所以用常量代替。后序线索为例：

ThreadTree pre2=NULL;
void PostThread2(ThreadTree t) { 
	if(t!=NULL){
			PostThread2(t->lchild);
			PostThread2(t->rchild);
		if(t->lchild==NULL){  //前驱 
			t->lchild=pre2;
			t->ltag=1;
		}
		if(pre2!=NULL&&pre2->rchild==NULL){
			pre2->rchild=t;     //后继 
			pre2->rtag=1;
		}
		pre2=t;
	}
}
void CreatePostThread2(ThreadTree t){
	if(t!=NULL){ 
		PostThread2(t);
	}
    printf("后序线索化2完成--------\n")
}

3.中序线索化为例深入讨论前驱后继

线索化完成，下一步的任务就是查找前驱后继。

以下面的二叉树为例子：ABD##E##CF###

 中序线索化后：

有蓝色箭头的结点很明显就能判断出它的前驱和后继，也就是左指针与右指针。

没有蓝色箭头的呢？

对于A结点来说它的中序前驱，就是左子树的最右下的结点，也就是E。

对于A结点来说它的中序后继，就是右子树的最左下的结点，也就是F。同样适用于其他的结点

有了这样的思想，就可以写出代码

ThreadNode *Firstnode(ThreadNode *p){  //第一个结点 
	while(p->ltag==0) p=p->lchild;    //该结点 最左下
	return p;
} 
ThreadNode *Nextnode(ThreadNode *p){
	if(p->rtag==1)   return p->rchild;
	else   return Firstnode(p->rchild); //右孩子 最左下的
}
ThreadNode *Priornode(ThreadNode *p){ 
	if(p->ltag==1) return p->lchild;
	else{
		p=p->lchild;  //左孩子 最右边的是 前驱
		while(p->rtag==0) p=p->rchild;
		return p;   }
} 
void Inorder(ThreadNode *t){
	for(ThreadNode *p=Firstnode(t);p!=NULL;p=Nextnode(p)){
		printf("%c",p->data);
	}printf("\n");
}

主函数调试

int main(){
	ThreadTree T;
	T=prebuild();

	//中序线索化
	CreateInThread(T);
	LevelOrder(T);  //层序查看 
	cout<<T->data<<"的后继是"<<Nextnode(T)->data<<endl;
	cout<<T->data<<"的前驱是"<<Priornode(T)->data<<endl;
	
	cout<<"中序线索遍历：";
	Inorder(T);   //遍历 
	
	deletetree(T);	
	return 0;
}

输入：ABD##E##CF###

输出：

先序和后序也是类似的。

总结

正在学习的程序⚪  。以上的内容就是数据结构线索二叉树的基本内容。如果有什么错误或问题下方留言。

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布