温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

C语言线索二叉树的前中后如何创建和遍历

发布时间:2022-02-21 13:40:45 来源:亿速云 阅读:136 作者:iii 栏目:开发技术

这篇“C语言线索二叉树的前中后如何创建和遍历”文章的知识点大部分人都不太理解,所以小编给大家总结了以下内容,内容详细,步骤清晰,具有一定的借鉴价值,希望大家阅读完这篇文章能有所收获,下面我们一起来看看这篇“C语言线索二叉树的前中后如何创建和遍历”文章吧。

    1.结构

    #include<stdio.h>
    #include<stdlib.h>
    #define false 0
    #define true 1
    using namespace std;
    typedef struct BTnode{
     	int data;
     	struct BTnode *lchild,*rchild;
     	int ltag,rtag;
     }*BTree,BTnode;

    1.1初始化tag

    #include<stdio.h>
    #include<stdlib.h>
    #define false 0
    #define true 1
    using namespace std;
    typedef struct BTnode{
     	int data;
     	struct BTnode *lchild,*rchild;
     	int ltag,rtag;
     }*BTree,BTnode;

    2.基本操作

    2.1 先序创建二叉树

    int j=0;  //创建二叉树的全局变量 
     //先序创建二叉树
     int CreateBTree(BTree &T){
     	int str[]={1,2,3,NULL,4,NULL,NULL,NULL,5,6,NULL,7,NULL,NULL,8,NULL,NULL};
     	if(str[j]=='#') return false;
     	if(str[j]==NULL){
     		T=NULL;
     		j++;
    	 }else{
    	 	T=(BTnode *)malloc(sizeof(BTnode));
    	 	T->data=str[j];
    	 	j++;
    	 	CreateBTree(T->lchild);
    	 	CreateBTree(T->rchild);
    	 }
     }

    输出函数:

    inline bool visit(int e){   //此处使用内敛函数,提高运行效率 
     	printf("%d",e);
     	return true;
     }

    2.2.先序线索化

    //先序线索化.
     void prehread(BTree &root){
    	if(root!=NULL){
    		if(root->lchild==NULL){
    			root->ltag=1;
    			root->lchild=pre;
    		}else{
    			root->ltag=0;
    		}
    		if(pre){
    			if(pre->rchild==NULL){
    				pre->rtag=1;
    				pre->rchild=root;
    			}else{
    				pre->rtag=0;
    			}
    		}
    		pre=root;
    		if(root->ltag==0){
    		prehread(root->lchild);	
    		}
    		if(root->rtag==0){
    			prehread(root->rchild);
    		}
    	}
    }
    2.2.1.先序遍历
    //寻找先序后继 
    BTree preNext(BTree T){
     	if(T->rtag==1){
    		return T->rchild;
    	 }else{
    	 	if(T->ltag==0){
    	 		return T->lchild;
    		 }else{
    		 	return T->rchild;
    		 }
    	 }
    	 }
    //先序线索二叉树的遍历
    void prebianli(BTree T){
    	BTree p;
    	p=T;
    	while(p){
    		visit(p->data);
    		p=preNext(p);
    	}
    }

    C语言线索二叉树的前中后如何创建和遍历

    2.3.中序线索化

    //中序线索化
    BTree pre=NULL ;  //中序线索化的全局变量 
    void Inthread(BTree &root){
    	if(root!=NULL){
    		Inthread(root->lchild);
    		if(root->lchild==NULL){
    			root->ltag=1;
    			root->lchild=pre;
    		}else{
    			root->ltag=0;
    		}
    		if(pre){
    			if(pre->rchild==NULL){
    				pre->rtag=1;
    				pre->rchild=root;
    			}else{
    				pre->rtag=0;
    			}
    		}
    		pre=root;
    		Inthread(root->rchild);
    	}
    }
    2.3.1 中序遍历
    //求中序首结点 
    BTree InFirst(BTree T){
    	BTree p=T;
    	if(p==NULL) return NULL;
    	while(p->ltag==0){
    		p=p->lchild; 
    	}
    	return p;
    } 
    //求中序后继
     BTree InNext(BTree T) {
     	BTree next=NULL;
     	if(T->rtag==1){
     		next=T->rchild;
    	 }else {
    		T = T->rchild;
    		while (T->ltag==0 ) {
    			T = T->lchild;
    		}
    		next=T;
    	 }
    	 return next;
     }
     //中序线索二叉树的遍历
    void Inbianli(BTree T){
    	BTree p;
    	p=InFirst(T);
    	while(p){
    		visit(p->data);
    		p=InNext(p);
    	}
    }

    C语言线索二叉树的前中后如何创建和遍历

    2.4.后序线索化

    //后续线索化
      void Postthread(BTree &root){
    	BTree pre=NULL;
    	if(root){
    		Postthread(root->lchild);
    		Postthread(root->rchild);
    		if(root->lchild==NULL){
    			root->ltag=1;
    			root->lchild=pre;
    		}
    		if(pre&&pre->rchild==NULL){
    			pre->rtag=1;
    			pre->rchild=root;
    		}
    		pre=root;
    		}
    }
    2.4.1 后序遍历
    //求后序前驱 
    BTree postnext(BTree T){
    	if(T->ltag==0){
    		if(T->rtag==0){
    			return T->rchild;
    		}else{
    			return T->lchild;
    		}
    	}else {
    		return T->lchild;
    	}
    }
    //后序遍历
    void postbianli(BTree T){
    	BTree p;
    	p=T;
    	while(p){
    		p=postnext(p);
    		visit(p->data);
    	}
    }

    C语言线索二叉树的前中后如何创建和遍历

    以上就是关于“C语言线索二叉树的前中后如何创建和遍历”这篇文章的内容,相信大家都有了一定的了解,希望小编分享的内容对大家有帮助,若想了解更多相关的知识内容,请关注亿速云行业资讯频道。

    向AI问一下细节

    免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

    AI