二叉树线索化与遍历线索二叉树

迈不过友情╰ 2022-07-15 02:26 251阅读 0赞

**若某程序中所用二叉树经常遍历或查找节点在遍历所得线性序列中的后继和前驱，适用于线索链表存储结构即线索二叉树。**

#include <iostream>
    using namespace std;
    struct bithrnode//线索二叉树节点
    {
    	char date;
    	bithrnode *lchild,*rchild;
    	int ltag,rtag;//左右标记，0为指针，1为线索
    };
    class bithrtree
    {
    private:
    	bithrnode *root;
    	bithrnode *pre;//pre始终指向刚刚访问（即中序遍历中输出过）过的节点
    	bithrnode *q;//q指向当前访问的节点
    public:
    	bithrtree()//这里引入根节点的作用是在建立变量bithrtree的时候就开始生成树
    		    //不必再引用create函数
    	{
    		create(root);
    	};
        ~bithrtree();
    	bithrnode *getroot()
    	{
    		return root;
    	}
    	void create(bithrnode *jj)//建立二叉树
    	{
    		char aa;
    		cin>>aa;
    		if(aa==' ') jj=NULL;
    		else
    		{
    			jj=new bithrnode;
    			jj->date=aa;
    			create(jj->lchild);
    			create(jj->rchild);
    		}
    	}
    	void inorderthreading(bithrnode *aa)//中序遍历的二叉树线索化
    	{
    		//bithrtree *thrt=&aa(注释bithrtree aa)
    
    		bithrnode *thrt=new bithrnode;//建立头节点
    		thrt->ltag=0; thrt->rtag=1;
    		if(aa) thrt->lchild=thrt;
    		else
    		{
    			thrt->lchild=aa; 
    			pre=thrt;
    			inthreading(aa);
    			pre->rchild=thrt;//中序遍历后pre为最后一个叶子节点
    			pre->rtag=0;
    			thrt->rchild=pre;
    		}
    	}
    	void inthreading(bithrnode *bb)
    	{
    		if(bb)
    		{
    			inthreading(bb->lchild);
    			if(!bb->lchild) {bb->ltag=1;bb->lchild=pre;}
    			if(!pre->rchild) {pre->rtag=1;pre->rchild=bb;}
    			pre=bb;
    			inthreading(bb->rchild);
    		}
    	}<pre name="code" class="cpp">	void inordertraverse(bithrnode *head)//中序遍历线索二叉树
    	{
    		bithrnode *pp=head->lchild;
    		cout<<pp->date;
    		while(pp!=head)
    		{
    			while(pp->lchild) pp=pp->lchild;
    			cout<<pp->date;
    			while(pp->rtag==1&&pp->rchild!=head)
    			{
    				pp=pp->rchild;
    				cout<<pp->date;
    			}
    			pp=pp->rchild;//
    		}
    	}