二叉树的操作

 

//=======================================================================
//                  二叉树的操作
//     BY:CHLAWS   
//     TIME:08-8-2
//=======================================================================
#include <stdio.h>
#include <stdlib.h>

/*
#define MAX_TREE_SIZE 100
typedef struct CTNode{
 int child;    //孩子结点位置
 struct CTNode* next;
}*ChildPtr;

typedef struct ChildNode{
 char data;
 int parent;    //双亲位置
 ChildPtr firstchlid; //孩子链表头指针
}CTBox;

typedef struct CTREE{
 CTBox nodes[MAX_TREE_SIZE];
 int n,r;
}CTree;
*/

/*
** 二叉链表结构
typedef struct BNode{
 char data;
 struct BNode *lchild, *rchild;
}BiTree;
*/

//判断指针或线索的标志
typedef enum PointerTag{ Link = 0, Thread};

typedef struct BNode{
 char data;
 struct BNode *lchild, *rchild;
 PointerTag   Ltag,     Rtag; 
}BiTree;
BiTree* prevTree = NULL;

bool (*Vist)(char);
bool Print(char);
bool CreateBiTree(BiTree*&);
bool DestroyBiTree(BiTree*&);
bool InOrderTraverse(const BiTree*, bool (*Vist)(char) );
bool InOrderThreading(BiTree*&,BiTree*);
void InThreading(BiTree*);
bool InOrderTraverse_Thread(BiTree* , bool (*Vist)(char));

void main()
{

 BiTree *Bitree = NULL;
 BiTree *headThread = NULL;
 Vist = Print;

 printf("//=====================#表示空子树=========================///n");

 CreateBiTree(Bitree);
 printf("This BinaryTree headnode data is: %c",Bitree->data);
 InOrderTraverse(Bitree,Vist);
 
 printf("/n//==============================================///n");
 
 InOrderThreading(headThread,Bitree);
 InOrderTraverse_Thread(headThread,Vist);
 
 
 DestroyBiTree(headThread);
 prevTree = NULL;
 Bitree = NULL;
 printf("/n//=======================完成操作=========================///n");
}

bool CreateBiTree(BiTree* &bTree)
{
 char ch;

 printf("Input single char date :/n");
 fflush(stdin);
 scanf("%c",&ch);
 /*
 *scanf_s("%c",&ch);
 *this is vc9 scanf instead function the reason is scanf may be unsafe
 */
 if(ch == '#')
 {
  bTree = NULL;
  return true;
 }
 else
 {
  if( !(bTree = (BiTree*)malloc(sizeof(BiTree)) ) ) exit(-1);
  
   bTree->data = ch;
   bTree->Ltag = Link;
   bTree->Rtag = Link;

   CreateBiTree(bTree->lchild);
   CreateBiTree(bTree->rchild); 
 }
 return true; 
}

bool Print(char data)
{
 printf("/nthis elem is : %c",data);
 return true;
}

//前序遍历输出每个结点值
bool InOrderTraverse(const BiTree* bTree,bool (*Vist)(char data))
{
 if(bTree)
 {
  if(Vist(bTree->data))
   if(InOrderTraverse(bTree->lchild,Vist))
    if(InOrderTraverse(bTree->rchild,Vist))
     return true;
  return false;
 }
 else return true;
}

//中序遍历线索二叉树并对每个元素应用Vist
bool InOrderTraverse_Thread(BiTree* headTree, bool (*Vist)(char data) )
{
 BiTree* bTree = headTree->lchild;

 while(bTree != headTree)
 {
  while(bTree->Ltag == Link) bTree = bTree->lchild; //走到头
  if(!Vist(bTree->data)) return false;
  while( (bTree->Rtag == Thread) && (bTree->rchild != headTree))
  {
   bTree = bTree->rchild; Vist(bTree->data);
  }

  bTree = bTree->rchild;
 }

 return true;
}

//中序遍历并将其线索化
bool InOrderThreading(BiTree*& Thrtree,BiTree*bTree)
{
 if(!(Thrtree = (BiTree*)malloc(sizeof(BiTree))) ) exit(-1);
 
 Thrtree->Ltag = Link;
 Thrtree->Rtag = Thread;
 Thrtree->rchild = Thrtree;
 
 if(!bTree) Thrtree->lchild = Thrtree; //若空,则回指
 else
 { 
  Thrtree->lchild = bTree;
  prevTree = Thrtree;

  InThreading(bTree); //线索化函数
  
  prevTree->rchild = Thrtree;
  prevTree->Rtag = Thread;

  Thrtree->rchild = prevTree;
 
 }

 return true;
}

void InThreading(BiTree* bTree)
{
 if(bTree)
 {
  InThreading(bTree->lchild);//左子树线索化
  
  /*
  *线索化其实就是对空指针的修改
  *关键是用prevTree保存前一个访问过的结点
  *根据当前指针指向的结点是前一个结点的前驱
  *则前一个结点的后续是当前结点
  */

  if(!bTree->lchild)   
  {
   bTree->Ltag = Thread;
   bTree->lchild = prevTree;
  }
  if(!prevTree->rchild)
  {
   prevTree->Rtag = Thread;
   prevTree->rchild = bTree;
  }
  prevTree = bTree;
  InThreading(bTree->rchild);//右子树线索化
 }
}

bool DestroyBiTree(BiTree* &bTree)
{
/*
//二叉链表的删除
 if(bTree)
 {
  BiTree* lbtemp;
  BiTree* rbtemp;
  lbtemp = bTree->lchild;
  rbtemp = bTree->rchild;
  
  free(bTree);
  bTree = NULL;
  
  if(DestroyBiTree(lbtemp))
   if(DestroyBiTree(rbtemp))
    return true;
  
  return false;
 }
 else return true;
*/

 
 BiTree* CurTree = bTree->lchild;
 
 while(CurTree != bTree)
 {
  while(CurTree->Ltag == Link)
  { 
   CurTree = CurTree->lchild; //走到头
  }

  prevTree = CurTree;

  while( (CurTree->Rtag == Thread) && (CurTree->rchild != bTree))
  {  
   
   CurTree = CurTree->rchild; //Vist(CurTree->data);   
   free(prevTree);
   prevTree = CurTree;
  }
  
  CurTree = CurTree->rchild;
  free(prevTree);
  prevTree = CurTree;
 }

 free(prevTree); 
 bTree = NULL;
 CurTree = NULL;
 return true;
}