非遞歸先序遍歷

• 　　 // 輸出， 遍歷左子樹，遍歷右子樹 void firstOrder(Node* root) {stack<Node*> leftNodes;Node* curr = root;// deal each nodewhile(curr != NULL && !leftNodes.empty()){// deal with left subtreewhile(curr != NULL){cout << curr -> data << " ";// store curr node for reading right subtree leftNodes.push(curr);curr = curr -> left;}// deal with right subtreeif(!leftNodes.empty()){curr = leftNodes.top();leftNodes.pop();curr = curr -> right;}} }

  ?

非遞歸中序遍歷

• // 輸出， 遍歷左子樹，遍歷右子樹 void middleOrder(Node* root) {stack<Node*> leftNodes;Node* curr = root;// deal each nodewhile(curr != NULL && !leftNodes.empty()){// deal with left subtreewhile(curr != NULL){// store curr node for reading right subtree leftNodes.push(curr);curr = curr -> left;}// deal with right subtreeif(!leftNodes.empty()){curr = leftNodes.top();leftNodes.pop();// cout curr nodecout << curr -> data << " ";curr = curr -> right;}} }

  ?　　

非遞歸后序遍歷

• // 輸出， 遍歷左子樹，遍歷右子樹 void lastOrder(Node* root) {stack<Node*> leftNodes;stack<bool> tags;bool curr_tag = true;Node* curr = root;// deal each nodewhile(curr != NULL && !leftNodes.empty()){// deal with left subtreewhile(curr != NULL){// store curr node for reading right subtree leftNodes.push(curr);// mark have not seen right nodestags.push(false);curr = curr -> left;}// deal with right subtreeif(!leftNodes.empty()){curr = leftNodes.top();curr_tag = tags.top();tags.pop();if(curr_tag){cout << curr -> data << " ";leftNodes.pop();// have already dealt right subtreep = NULL;}else{curr = curr -> right;// mark has dealt with rightsubtreetags.push(true); }}} }

二叉排序樹：左<父<右

哈弗曼樹

• 哈夫曼編碼：帶權(quán)路徑最短
• 構(gòu)建方法：從最遠端構(gòu)建

平衡二叉（搜索）樹：每個節(jié)點的左右子樹深度差的絕對值小于等于1。

• 一種實現(xiàn)：紅黑樹
• 基本失衡情況：左左（右旋），右右（左旋），左右，右左。

紅黑樹

• 節(jié)點：紅色或黑色。根節(jié)點：黑色。葉節(jié)點：黑色。紅色節(jié)點的孩子為黑色。根節(jié)點到其每個葉子節(jié)點的所有路徑包含相同數(shù)目的黑色節(jié)點。
• 等待補充

完全二叉樹和滿二叉樹

• 完全二叉樹，集中在左邊
• 滿二叉樹，沒有葉子節(jié)點

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

總結(jié)

以上是生活随笔為你收集整理的C/C++程序基础 （八）数据结构的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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