tree.cpp

实现从键盘按照先序输入二叉树

//在一已知的二叉树上建立中序线索树并遍历之

#include <iostream.h>
#include <stdlib.h>
#include <string.h>

char ch;
typedef struct BiThrNode//定义二叉树
{
   char data;
   struct BiThrNode *lchild,*rchild;
   int LTag,RTag;
}BiThrNode,*BiThrTree;



BiThrTree pre,p;
void CreateBiTree(BiThrTree &T)//创建二叉树，从键盘输入节点
{
      //cout<<ch<<endl;
     

	  cin>>ch;
      if (ch=='*') T=NULL;
      else
	  {
         T=new BiThrNode;
         T->data=ch; T->LTag=0; T->RTag=0;   //左右子树都指向孩子,用0标示
         CreateBiTree(T->lchild);
		 CreateBiTree(T->rchild);
		 
	  }

	 return;
      
}

void InThreading(BiThrTree p)//线索化二叉树函数
{
	if(p!=NULL)
	{
	   InThreading(p->lchild);
	   if(p->lchild==NULL){p->LTag=1;p->lchild=pre;}  //LTag=1代表指向前驱
	   if(pre->rchild==NULL){pre->RTag=1;pre->rchild=p;}
	   pre=p;
       InThreading(p->rchild);
	}
  
}
void InOrderThreading(BiThrTree &Thrt,BiThrTree T)//线索化二叉树
{
   Thrt=new BiThrNode;          
   Thrt->LTag=0;Thrt->RTag=1;         //建立头节点
   Thrt->rchild=Thrt;
   if(T==NULL) Thrt->lchild=Thrt;
   else
   {
      Thrt->lchild=T;  pre=Thrt;
	  InThreading(T);
	  pre->rchild=Thrt;pre->RTag=1;    //最后一个节点线索化
	  Thrt->rchild=pre;

   }
   return;
}
void InOrderTraverse_Thr(BiThrTree T)//遍历二叉树
{
   p=T->lchild;
   while(p!=T)
   {
      while(p->LTag==0)p=p->lchild;
	  cout<<p->data<<' ';            //输出最左边的元素
	  while(p->RTag==1 && p->rchild!=T)   
	  { p=p->rchild;cout<<p->data<<' '; }
	  p=p->rchild;
   }
   return;
}
void main()//主函数
{
	int temp;
   cout<<"按先序输入二叉树的节点(空格代表空，以*代表空节点):"<<endl;
   BiThrTree BiThrTree1,BiThrTree2;
   CreateBiTree(BiThrTree2);     //创建二叉树，从键盘输入节点
   InOrderThreading(BiThrTree1,BiThrTree2);  //线索化二叉树
   temp=0;
   cout<<"遍历线索化二叉树为:"<<endl;
   InOrderTraverse_Thr(BiThrTree1);    //遍历二叉树
   cout<<endl;
   
}