thread.h

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

//ThreadBiTree.cpp
#include <iostream>
#include "treeabc.h"
using namespace std;

typedef struct AVLTree AVLTree;

AVLTree *BiTree, *pre, *Thrt;  //采用全局变量使得函数能返回多个值

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

AVLTree *InThreading(AVLTree *BiTree)  //中序线索化二叉树
{
 if(BiTree)
 {
  BiTree->pLeft = InThreading(BiTree->pLeft);  //左子树线索化
  if(!BiTree->pLeft)
  {
   BiTree->LTag = Thread;
   BiTree->pLeft = pre;  
  }
  if(!pre->pRight)
  {
   pre->RTag = Thread;
   pre->pRight = BiTree;
  }
  pre = BiTree;  //保持pre指向BiTree的前驱
  BiTree->pRight = InThreading(BiTree->pRight);  //右子树线索化
 }
 return BiTree;
}
AVLTree *InOrderThreading(AVLTree *BiTree)  //中序遍历并线索化
{
 Thrt = (AVLTree *)malloc(sizeof(AVLTree));
 pre = (AVLTree *)malloc(sizeof(AVLTree));
 Thrt->LTag = Link;   //初始化头节点
 Thrt->RTag = Thread;
 Thrt->pRight = Thrt;  //右指针回指
 if(!BiTree)
  Thrt->pLeft = Thrt; //若树空则左指针回指
 else
 {
  Thrt->pLeft = BiTree;
  pre = Thrt;
  BiTree = InThreading(BiTree); //中序线索化
  pre->pRight = Thrt;  //最后一个节点线索化
  pre->RTag = Thread;
  Thrt->pRight = pre;
 }
 return BiTree;
}
void InOrderTraverse(AVLTree *BiTree)  //中序遍历线索二叉树并输出
{
 AVLTree *p;
 p = (AVLTree *)malloc(sizeof(AVLTree));
 p = Thrt->pLeft;
 while(p != Thrt && p)
 {
  while(p->LTag != Thread)
   p = p->pLeft;
  cout<<p->nData<<"      ";
  while(p->RTag == Thread && p->pRight != Thrt)
  {
   p = p->pRight;
   cout<<p->nData<<"      ";
  }
  p = p->pRight;
 }
}