C++非遞歸樹立二叉樹實例

C++非遞歸樹立二叉樹實例。本站提示廣大學習愛好者：（C++非遞歸樹立二叉樹實例）文章只能為提供參考，不一定能成為您想要的結果。以下是C++非遞歸樹立二叉樹實例正文

本文實例講述了C++非遞歸樹立二叉樹的辦法。分享給年夜家供年夜家參考。詳細剖析以下：

思緒：

設置一個標志變量flag並初始化為1. flag = 1表現如今須要創立以後結點的左孩子，2表現須要創立右孩子，3則表現以後結點的閣下孩子都曾經創立終了，須要履行出棧操作，直到以後結點不是父結點的右孩子為止。

以先序創立如圖所示二杈樹：

完成代碼：

PBTree create()
{
 char ch[20];
 scanf("%s",ch);
 int len = strlen(ch);
 PBTree stack[20];
 /* 用來存儲結點地址的棧 */ 
 int top = 0;
 /* 棧頂指針 */
 int flag = 1;
 /* 1表現如今須要創立左孩子，
 2表現須要創立右孩子，
 3表現閣下孩子都曾經創立完成 */
 int i = 0;
 PBTree temp;
 PBTree root = (PBTree)malloc(sizeof(BTree));
 root->data = ch[i++];
 root->lchild = NULL;
 root->rchild = NULL;
 stack[top ++] = root;
 while(i < len)
 {
  PBTree pNew = NULL;
  if(1 == flag) /* 創立左孩子 */
  {
   if('#' == ch[i])
    flag = 2;
   else
   {
    pNew = (PBTree)malloc(sizeof(BTree));
    pNew->lchild = NULL;
    pNew->rchild = NULL;
    pNew->data = ch[i];
    temp = stack[top - 1];
    temp->lchild = pNew;
    stack[top++] = pNew;
    flag = 1;
   }
  }
  else if(2 == flag)
  /* 創立右孩子 */
  {
   if('#' == ch[i])
    flag = 3;
   else
   {
    pNew = (PBTree)malloc(sizeof(BTree));
    pNew->lchild = NULL;
    pNew->rchild = NULL;
    pNew->data = ch[i];
    temp = stack[top - 1];
    temp->rchild = pNew;
    stack[top++] = pNew;
    flag = 1;
   }
  }
  else
  /* 閣下孩子曾經創立完成，須要出棧*/
  {
   temp = stack[--top];
   while(top > 1 && stack[top - 1]->rchild == temp)
    --top;
   flag = 2;
   --i;
  }
  ++i;
 }
 return root;
}

願望本文所述對年夜家的C++法式設計有所贊助。