C++非遞歸建立二叉樹實例
本文實例講述了C++非遞歸建立二叉樹的方法。分享給大家供大家參考。具體分析如下:
思路:
設置一個標記變量flag并初始化為1. flag = 1表示現(xiàn)在需要創(chuàng)建當前結(jié)點的左孩子,2表示需要創(chuàng)建右孩子,3則表示當前結(jié)點的左右孩子都已經(jīng)創(chuàng)建完畢,需要執(zhí)行出棧操作,直到當前結(jié)點不是父結(jié)點的右孩子為止。
以先序創(chuàng)建如圖所示二杈樹:
實現(xiàn)代碼:
PBTree create() { char ch[20]; scanf("%s",ch); int len = strlen(ch); PBTree stack[20]; /* 用來存儲結(jié)點地址的棧 */ int top = 0; /* 棧頂指針 */ int flag = 1; /* 1表示現(xiàn)在需要創(chuàng)建左孩子, 2表示需要創(chuàng)建右孩子, 3表示左右孩子都已經(jīng)創(chuàng)建完成 */ 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) /* 創(chuàng)建左孩子 */ { 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) /* 創(chuàng)建右孩子 */ { 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 /* 左右孩子已經(jīng)創(chuàng)建完成,需要出棧*/ { temp = stack[--top]; while(top > 1 && stack[top - 1]->rchild == temp) --top; flag = 2; --i; } ++i; } return root; }
希望本文所述對大家的C++程序設計有所幫助。
相關文章
《戰(zhàn)狼》中兩軍作戰(zhàn)入侵代碼竟然是輸出星期幾的!
這篇文章主要介紹了《戰(zhàn)狼》中兩軍作戰(zhàn)入侵代碼竟然是輸出星期幾的,喜歡戰(zhàn)狼和編程的同學可以了解下。2017-11-11C/C++?Qt?StringListModel?字符串列表映射組件詳解
StringListModel?字符串列表映射組件,該組件用于處理字符串與列表框組件中數(shù)據(jù)的轉(zhuǎn)換,通常該組件會配合ListView組件一起使用,本文給大家介紹了C/C++?Qt?StringListModel?字符串列表映射組件的相關知識,感興趣的朋友跟隨小編一起看看吧2021-12-12Qt圖形圖像開發(fā)之高性能曲線圖模塊QCustomplot庫詳細使用方法與實例(支持動、靜曲線圖)
這篇文章主要介紹了Qt圖形圖像開發(fā)之高性能曲線圖模塊QCustomplot庫詳細使用方法與實例(支持動、靜曲線圖),需要的朋友可以參考下2020-03-03