二叉树先序线索化.cpp

二叉树的建立

#include "iostream.h"
typedef char TelemType;
typedef struct BiTNode
{
       TelemType data;
    struct BiTNode *lchild,*rchild;    /*左右孩子指针*/
    int ltag,rtag; 
 }BiTNode,*BiTree;

BiTree  pre=0;

//按先序遍历得到的字符串建立二叉链表
BiTNode *createbtree()
{BiTNode *t;
	TelemType ch;
	cin>>ch;
if(ch=='#') return 0;
else
{t=new BiTNode;
t->data=ch;
t->ltag=t->rtag=0;
t->lchild=createbtree();
t->rchild=createbtree();
	}
return t;
}
//先序遍历
void preorder(BiTNode *t)
{if(t!=0)
{
cout<<t->data<<"  ";

preorder(t->lchild);
preorder(t->rchild);
}
}
//线索化
void PreThreading(BiTNode *P)
   {  if (P)
       {  if (!P->lchild)
       { P->ltag=1;P->lchild=pre;}
if (!P->rchild) P->rtag=1; 
if(pre && pre->rtag==1)
     pre->rchild=P;
    pre=P;
 if (P->ltag==0)
       PreThreading(P->lchild);
   if (P->rtag==0) PreThreading(P->rchild);
	 }
    }

//查找
BiTNode *locate(BiTNode *bt,TelemType x)
   {BiTNode *p;
    if(bt==0) return 0;
	if(bt->data==x)return bt;
	if(bt->lchild !=0) 
	{p=locate(bt->lchild,x);
	if(p!=0) return p;
	}
  if(bt->rchild !=0)
  {p=locate(bt->rchild,x);
	if(p!=0) return p;
	}
	 return 0;
}
//输出二叉树（向左旋转90度）
void printbtree(BiTNode  *t,int level)
{ if(t!=0)
{ printbtree(t->rchild,level+1);
  if(level!=0)
  { for(int i=0;i<6*(level-1);i++) cout<<"  ";
  cout<<"----";
  }
  cout<<t->data<<endl;
  printbtree(t->lchild ,level+1);
}
}
//先序线索二叉树中查找结点t的后继
BiTree preordernext(BiTree t)
{
if(t->lchild) return t->lchild;
if(t->rchild) return t->rchild;
return 0;

/*if(t->rtag==1) return (t->rchild);
else
{ p=t->rchild;
while(p->ltag==0) p=p->lchild;
if(p==t) return null;
return p;
}*/
}
//先序线索二叉树中查找结点p的前驱
BiTree preorderpre(BiTree t,BiTree p)
{
  if(t==p) return pre;
   pre=p;
 if(t->lchild)  preorderpre(t->lchild,p);
 if(t->rchild) preorderpre(t->rchild,p);
 
}


void main()
{ int  x=0;
	BiTNode  *t1,*t2=0,*t3;
t1=createbtree(); 
printbtree(t1,x); 
t2=locate(t1,'d');
preorder(t1);cout<<endl;
PreThreading(t1);
t3=preordernext(t2);
if(t3)cout<<t3->data <<endl;
t3=preorderpre(t1,t2);
if(t3) cout<<t3->data <<endl;
}