验证中序线索化正确的程序.cpp

中序线索化的二叉树 能够对二叉树先线索化然后再中序排列 并且输出

//ThreadBiTree.cpp
#include <iostream>
using namespace std;
typedef enum PointerTag {Link, Thread};
typedef struct BiThrNode
{
 char data;
 struct BiThrNode *lchild, *rchild;
 PointerTag LTag, RTag;
}BiThrNode;
BiThrNode *BiTree, *pre, *Thrt;  //采用全局变量使得函数能返回多个值

BiThrNode *CreateBiTree(BiThrNode *BiTree)  //先序递归构造二叉树
{
 char ch;  
 ch = getchar();
 if(ch == '#')  //若为叶子节点则其左右孩子均为空
  BiTree = NULL;
 else
 {
  BiTree->data = ch;    //生成根节点
  BiTree->lchild = (BiThrNode *)malloc(sizeof(BiThrNode));
  BiTree->lchild = CreateBiTree(BiTree->lchild); //构造左子树
  BiTree->rchild = (BiThrNode *)malloc(sizeof(BiThrNode));
  BiTree->rchild = CreateBiTree(BiTree->rchild); //构造右子树
 }
 return BiTree;
}

BiThrNode *InThreading(BiThrNode *BiTree)  //中序线索化二叉树
{
 if(BiTree)
 {
  BiTree->lchild = InThreading(BiTree->lchild);  //左子树线索化
  if(!BiTree->lchild)
  {
   BiTree->LTag = Thread;
   BiTree->lchild = pre;  
  }
  if(!pre->rchild)
  {
   pre->RTag = Thread;
   pre->rchild = BiTree;
  }
  pre = BiTree;  //保持pre指向BiTree的前驱
  BiTree->rchild = InThreading(BiTree->rchild);  //右子树线索化
 }
 return BiTree;
}
BiThrNode *InOrderThreading(BiThrNode *BiTree)  //中序遍历并线索化
{
 Thrt = (BiThrNode *)malloc(sizeof(BiThrNode));
 pre = (BiThrNode *)malloc(sizeof(BiThrNode));
 Thrt->LTag = Link;   //初始化头节点
 Thrt->RTag = Thread;
 Thrt->rchild = Thrt;  //右指针回指
 if(!BiTree)
  Thrt->lchild = Thrt; //若树空则左指针回指
 else
 {
  Thrt->lchild = BiTree;
  pre = Thrt;
  BiTree = InThreading(BiTree); //中序线索化
  pre->rchild = Thrt;  //最后一个节点线索化
  pre->RTag = Thread;
  Thrt->rchild = pre;
 }
 return BiTree;
}
void InOrderTraverse(BiThrNode *BiTree)  //中序遍历线索二叉树并输出
{
 BiThrNode *p;
 p = (BiThrNode *)malloc(sizeof(BiThrNode));
 p = Thrt->lchild;
 while(p != Thrt && p)
 {
  while(p->LTag != Thread)
   p = p->lchild;
  cout<<p->data;
  while(p->RTag == Thread && p->rchild != Thrt)
  {
   p = p->rchild;
   cout<<p->data;
  }
  p = p->rchild;
 }
}
main()
{
 std::cout<<"可以输入（a#b##）试验"<<std::endl; 
 BiTree = (BiThrNode *)malloc(sizeof(BiThrNode));
 cout<<"输入节点数据(char 型)(#代表NULL):"<<endl;
 BiTree = CreateBiTree(BiTree);
 BiTree = InOrderThreading(BiTree);
 cout<<"线索化后遍历输出:"<<endl;
 InOrderTraverse(BiTree);
 system("pause");
 return 0;
}