二叉樹(shù)是一種特殊的樹(shù)型結(jié)構(gòu)，一般都以二叉樹(shù)作為樹(shù)型結(jié)構(gòu)學(xué)習(xí)的案例講解。

二叉樹(shù)的主要操作有遍歷，例如有先序遍歷、中序遍歷、后序遍歷。在遍歷之前，就是創(chuàng)建一棵二叉樹(shù)，當(dāng)然，還需要有刪除二叉樹(shù)的算法。

以二叉樹(shù)的創(chuàng)建、刪除、先序遍歷為例，實(shí)現(xiàn)代碼如下

#include 
#include 


typedef char ElemType;
typedef struct node
{  ElemType data;
  struct node *lchild, *rchild;
} BTNode;      




BTNode * createTree(BTNode *tree){
  ElemType e; 
  fflush(stdin);
  scanf("%c", &e);
  if(e != '#'){
    tree = (BTNode *)malloc(sizeof(BTNode));
    tree->data = e; tree->lchild = NULL; tree->rchild = NULL;
    tree->lchild = createTree(tree->lchild);
    tree->rchild = createTree(tree->rchild);
  }
  return tree;
}


void DestroyBTree(BTNode *b)
{  if (b==NULL) return ;
  else
    {  DestroyBTree(b->lchild);
      DestroyBTree(b->rchild);
      free(b);           
  }
}


void PreOrder(BTNode *b)
{  if (b!=NULL)  
   {  printf("%c ",b->data); 
   PreOrder(b->lchild);
   PreOrder(b->rchild);
}
}


int main(){
  BTNode *tree = createTree(tree);


  PreOrder(tree);


  DestroyBTree(tree);
  return 0;
}

測(cè)試用例如下

A
B
D
#
G
#
#
#
C
E
#
#
F
#
#
A B D G C E F

以上測(cè)試用的測(cè)試案例，就是上述二叉樹(shù)圖形的結(jié)構(gòu)，二叉樹(shù)構(gòu)成過(guò)程中，以先序的方式創(chuàng)建，子樹(shù)為空的時(shí)候，輸入為#

上述算法中，還可以做更多的優(yōu)化，每一個(gè)優(yōu)化都是一次進(jìn)步。

審核編輯：劉清