本文實例講述了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++程序設計有所幫助。
新聞熱點
疑難解答
圖片精選
