二叉树中序线索化.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->lchild=createbtree();
t->rchild=createbtree();
	}
return t;
}
//中序遍历
void inorder(BiTNode *t)
{if(t!=0)
{
inorder(t->lchild);
cout<<t->data<<"  ";
inorder(t->rchild);
}
}
void inorderthreading(BiTree t)
{if(t!=0)
{
inorderthreading(t->lchild);
if(!t->lchild)t->ltag=1;
if(!t->rchild) t->rtag=1;
if(pre)
{if(pre->rtag==1) pre->rchild=t;
if(t->ltag==1) t->lchild=pre;
}
pre=t;
inorderthreading(t->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 inordernext(BiTree t)
{ BiTNode *p;
if(t->rtag==1) return (t->rchild);
else
{ p=t->rchild;
while(p->ltag==0) p=p->lchild;
return p;
}
}
//中序线索二叉树中查找结点p的前驱
BiTree inorderpre(BiTree p)
{BiTree q;
if(p->ltag==1) return p->lchild;
else
{
	q=p->lchild;
	while(q->rtag==0)q=q->rchild ;
	return q;
}
}


void main()
{ int  x=0;
	BiTNode  *t1,*t2=0,*t3;
t1=createbtree(); 
printbtree(t1,x); 
t2=locate(t1,'e');
inorder(t1);cout<<endl;
inorderthreading(t1);
t3=inordernext(t2);
cout<<t3->data <<endl;
t3=inorderpre(t2);
cout<<t3->data <<endl;
}