1 // 遞歸算法 2 template <class T> 3 void postOrder(void (*visit)(BinTreeNode<T>* t), BinTreeNode<T>* root) 4 { 5 if (root != NULL) { 6 postOrder(visit, root->leftChild); 7 postOrder(visit, root->rightChild); 8 visit(root); 9 } 10 }

?

1 /* 2 非遞歸算法1. 3 4 非遞歸算法，使用節(jié)點(diǎn)的右指針來(lái)做判別標(biāo)志該節(jié)點(diǎn)是否是第一次訪問(wèn)，從根節(jié)點(diǎn)開(kāi)始?jí)喝胨凶钭筮吂?jié)點(diǎn)進(jìn)入堆棧，因?yàn)楸粔喝攵褩５倪^(guò)程決定了，當(dāng)前節(jié)點(diǎn)的左子結(jié)點(diǎn)已經(jīng)被訪問(wèn)過(guò)了，所以只需判斷右子節(jié)點(diǎn)。如果右子節(jié)點(diǎn)為空可以認(rèn)為已經(jīng)訪問(wèn)過(guò)了，如果非空，則修改指向右子節(jié)點(diǎn)的指針為空，作為已經(jīng)訪問(wèn)過(guò)的標(biāo)志。 5 6 */ 7 template <class T> 8 void postOrder(void(*visit)(BinTreeNode<T>* t), stack<BinTreeNode<T>*> s) 9 { 10 BinTreeNode<T>* p = root; 11 s.push(NULL); 12 bool flag = true; 13 do { 14 while (p != NULL) { 15 s.push(p); 16 p = p->leftChild; 17 } 18 while (flag) { 19 if (! s.isEmpty()) { 20 s.pop(p); 21 if (p->rightChild == NULL) visit(p); 22 else { // 右子節(jié)點(diǎn)非空，且未訪問(wèn)過(guò) 23 flag = false; 24 s.push(p); // 右子節(jié)點(diǎn)壓回堆棧 25 BinTreeNode<T>* tmp = p->rightChild; 26 p->rightChild = NULL; 27 p = tmp; 28 } 29 } 30 } 31 } while (! s.isEmpty()); 32 }

?

1 /* 2 非遞歸算法2 3 4 要保證根節(jié)點(diǎn)在左孩子和右孩子都訪問(wèn)之后才能訪問(wèn)，因此對(duì)任一節(jié)點(diǎn)P，先將其入棧，如果P沒(méi)有子女，則可以直接訪問(wèn)它，如果有子女，且其左右孩子都已經(jīng)訪問(wèn)過(guò)了，也可以訪問(wèn)P節(jié)點(diǎn)。否則，需要將P的右孩子和左孩子先后入棧，這樣保證出棧順序是先左孩子后右孩子。 5 6 acknowledgement: http://www.cnblogs.com/dolphin0520/archive/2011/08/25/2153720.html 7 */ 8 9 10 11 template <class T> 12 void postOrder(void(*visit)(BinTreeNode<T>* t), stack<BinTreeNode<T>*> s) 13 { 14 BinTreeNode<T>* cur = NULL; 15 BinTreeNode<T>* pre = NULL; 16 s.push(root); 17 while (! s.isEmpty()) { 18 cur = s.getTop(); 19 if ((cur->leftChild == NULL && cur->rightChild == NULL) || (pre != NULL && (pre = cur->leftChild || pre = cur->rightChild))) { 20 s.pop(cur); 21 visit(cur); 22 pre = cur; 23 } else { 24 if (cur->rightChild != NULL) s.push(cur->rightChild); 25 if (cur->leftChild != NULL) s.push(cur->leftChild); 26 } 27 } 28 }

?

1 /* 2 非遞歸算法3 3 構(gòu)建一個(gè)新的struct，加入一個(gè)變量visit標(biāo)示該節(jié)點(diǎn)是否被訪問(wèn)過(guò) 4 */ 5 6 template <class T> 7 struct newNode { 8 BinTreeNode<T>* ptr; 9 int visit; 10 newNode(BinTreeNode<T>* p) : ptr(p), visit(0) {} 11 } 12 13 template <class T> 14 void postOrder(void (visit*)(BinTreeNode<T>* t), stack<newNode<T>*> s) 15 { 16 BinTreeNode<T>* p = root; 17 newNode* np = NULL; 18 do { 19 while (p != NULL) { 20 np = newNode(p); 21 s.push(np); 22 p = p->leftChild; 23 } 24 bool flag = true; 25 while (flag) { 26 s.pop(np); 27 if (np->ptr->rightChild == NULL || np->visit == 1) { 28 visit(np->ptr); 29 } else { 30 s.push(np); 31 flag = false; 32 np->visit = 1; 33 p = np->ptr->rightChild; 34 } 35 } 36 } while (! s.isEmpty()); 37 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/shadowwalker9/p/4731878.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的二叉树的后续遍历算法实现的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。