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