线索二叉树

以你之姓@ 2022-06-09 01:13 183阅读 0赞

线索化二叉树相对于之前的树的遍历，在树的定义上增加了两个值，一个是ltag，另外一个是rtag。

ltag代表着这个节点的是否有右孩子，如果有，则ltag=1，p->lchild指向的是p的左孩子。

如果没有左孩子，那么ltag=0，p->lchild指向的是p的前驱节点。

rtag代表着这个节点的是否有右孩子，如果有，则rtag=1，p->rchild指向的是p的右孩子。

如果没有右孩子，那么rtag=0，p->rchild指向的是p的后继节点。

线索二叉树的定义如下：

typedef struct ThreadTree(BiTree T)
    {
           ElemType data;
           struct ThreadTree *lchild,*rchild;
           int ltag,rtag;
    }ThreadTree;

首先声明：

void CreateThreadTree(ThreadNode T) {          ThreadNode pre=NULL,p=T;          if(T!=NULL)          {                    ThreadTree(T,pre);                    pre->rchild =NULL;//处理最后一个节点的右子树                    pre->rtag = 0;          } }

中序遍历线索化二叉树的递归代码，作用是生成线索化二叉树：

void ThreadTree(BiTree &T,BiTree &pre)
    {
    	if(T)
    	{
    		ThreadTree(T->lchild,pre);
    		if(T->lchild==NULL)
    		{
    			T->lchild = pre;
    			T->ltag = 1;
    		}
    		if(pre!=NULL && pre->lchild!=NULL)
    		{
    			pre->rchild = T;
    			pre->rtag = 1;
    		}
    		pre = T;
    		ThreadTree(T->rchild,pre);
    	}
    }

线索化二叉树的遍历：

查找第一个节点：

ThreadNode FirstNode(ThreadNode T)
    {
    	while(T->ltag == 0)
    		T=T->lchild;
    	return T;
    }

一直向最左边进行遍历。直到查找到第一个不为0的，便是中序遍历的第一个字符。

查找节点p的下一个后继节点

ThreadNode NextNode(ThreadNode *p){
           if(p->rtag==0)
                return FirstNode(p->rchild);
           else
               return p->rchild;
    }

整个的树的遍历：

ThreadNode InOrder(ThreadNode T){
          if(T!=NULL)
          {
              for(ThreadNode p = FirstNode(T); p!=NULL ;p = NextNode(p))
                    visit(p); 
          }
    }