二叉樹結構：

1 2 3 4 5 6 7

template<class?T> struct?BinaryTreeNode { ????T?_data;?? ????BinaryTreeNode<T>*?_left;??? ????BinaryTreeNode<T>*?_right; }

前序，中序，后序遍歷（遞歸&非遞歸）

先寫非遞歸實現方法：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79

void?PrevOrder_NonR()????????//前序非遞歸 { ????stack<BinaryTreeNode<T>*>?s; ????if?(_root) ????{ ????????s.push(_root);??//將樹入棧 ????} ????while?(!s.empty())??//棧不為空，根節點先出棧 ????{ ????????BinaryTreeNode<T>*?top?=?s.top(); ????????s.pop(); ????????cout?<<?top->_data?<<?"?"; ????????if?(top->_right)????????????//壓入右子樹 ????????{ ????????????s.push(top->_right); ????????} ????????if?(top->_left)?????????//壓入左子樹 ????????{ ????????????s.push(top->_left); ????????} ????} ????cout?<<?endl; } void?InOrder_NonR()????????//中序非遞歸 { ????stack<BinaryTreeNode<T>*>?s; ????BinaryTreeNode<T>*?cur?=?_root; ????while?(cur?||?!s.empty()) ????{ ????????while?(cur) ????????{ ????????????s.push(cur); ????????????cur?=?cur->_left; ????????} ????????if?(!s.empty()) ????????{ ????????????BinaryTreeNode<T>*?top?=?s.top(); ????????????cout?<<?top->_data?<<?"?"; ????????????s.pop(); ????????????cur?=?top->_right; ????????} ????} ????cout?<<?endl; } void?PostOrder_NonR()????????//后序非遞歸 { ????stack<BinaryTreeNode<T>*>?s; ????BinaryTreeNode<T>*?cur?=?_root; ????BinaryTreeNode<T>*?prevVisited?=?NULL; ????while?(cur?||?!s.empty()) ????{ ????????while?(cur) ????????{ ????????????s.push(cur); ????????????cur?=?cur->_left; ????????} ????????BinaryTreeNode<T>*?top?=?s.top(); ????????if?(top->_right?==?NULL?||?top->_right?==?prevVisited) ????????{ ????????????cout?<<?top->_data?<<?"?"; ????????????prevVisited?=?top; ????????????s.pop(); ????????} ????????else ????????{ ????????????cur?=?top->_right; ????????} ????} ????cout?<<?endl; }

再實現遞歸方法：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

void?_PrevOrder(BinaryTreeNode<T>*?root)????//前序 { ????if?(root?==?NULL) ????{ ????????return; ????} ????cout?<<?root->_data?<<?"?"; ????_PrevOrder(root->_left); ????_PrevOrder(root->_right); } void?_InOrder(BinaryTreeNode<T>*?root)????????//中序 { ????if?(root?==?NULL) ????{ ????????return; ????} ????_InOrder(root->_left); ????cout?<<?root->_data?<<?"?"; ????_InOrder(root->_right); } void?_PostOrder(BinaryTreeNode<T>*?root)????????//后序 { ????if?(root?==?NULL) ????{ ????????return; ????} ????_PostOrder(root->_left); ????_PostOrder(root->_right); ????cout?<<?root->_data?<<?"?"; }

2.層次遍歷

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

void?_LevelOrder() { ????queue<BinaryTreeNode<T>*>?q;???//定義一個隊列q ????if?(_root)?????????//判斷_root是否為空 ????{ ????????q.push(_root); ????} ????while?(!q.empty()) ????{ ????????BinaryTreeNode<T>*?front?=?q.front(); ????????q.pop(); ????????cout?<<?front->_data?<<?"?"; ????????if?(front->_left)???//由左向右依次進入隊列，依次輸出 ????????{ ????????????q.push(front->_left); ????????} ????????????? ????????if?(front->_right) ????????{ ????????????q.push(front->_right); ????????} ????} ????cout?<<?endl; }

3.求二叉樹的高度

1 2 3 4 5 6 7 8 9 10 11 12

int?_Depth(BinaryTreeNode<T>*?root) { ????if?(root?==?NULL) ????{ ????????return?0; ????} ????int?leftDepth?=?_Depth(root->_left); ????int?rightDepth?=?_Depth(root->_right); ????return?leftDepth?>?rightDepth???leftDepth?+?1?:?rightDepth?+?1; }

4.求葉子節點的個數

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

void?_GetLeafNum(BinaryTreeNode<T>*?root,?int&?num) { ????if?(root?==?NULL) ????{ ????????return; ????} ????if?(root->_left?==?NULL&&root->_right?==?NULL) ????{ ????????++num; ????????return; ????} ????_GetLeafNum(root->_left,?num); ????_GetLeafNum(root->_right,?num); }

5.求二叉樹第K層的節點個數

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

int?_GetLevelLeafNum(const?BinaryTreeNode<T>*?root,?const?int?k) { ????int?count?=?0; ????if?(root?==?NULL?||?k?<?0) ????{ ????????return?0; ????} ????if?(k?==?0) ????{ ????????count++; ????} ????_GetLevelLeafNum(root->_left,?k?-?1); ????_GetLevelLeafNum(root->_right,?k?-?1); ????return?count; }

6.判斷一個節點是不是在二叉樹中

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

BinaryTreeNode<T>*?_Find(BinaryTreeNode<T>*?root,?const?T&?x) { ????if?(root?==?NULL) ????{ ????????return?NULL; ????} ????else?if?(root->_data?==?x) ????{ ????????return?root; ????} ????else ????{ ????????BinaryTreeNode<T>*?ret?=?_Find(root->_left,?x); ????????if?(ret) ????????{ ????????????return?ret; ????????} ????????else ????????{ ????????????return?_Find(root->_right,?x); ????????} ????} }

7.求兩個節點的最近公共祖先

1 2 3 4

int?FindCommonAncestor(BinaryTreeNode<T>*?root,BinaryTreeNode<T>*?node1,?BinaryTreeNode<T>*?node2) { }

8.判斷二叉樹是不是平衡二叉樹

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

bool?_IsBalanceTree(Node*?root) { ????if?(root?==?NULL) ????{ ????????return?true; ????} ????int?left?=?_Height(root->_left); ????int?right?=?_Height(root->_right); ????int?bf?=?abs(right?-?left); ????if?(bf?>?1) ????{ ????????return?false; ????} ????else?if?(bf?!=?abs(root->_bf)) ????{ ????????cout?<<?root->_bf?<<?"平衡因子有誤！"?<<?endl; ????????return?false; ????} ????return?_IsBalanceTree(root->_left)?&&?_IsBalanceTree(root->_right); }

9.求二叉樹中最遠的兩個節點的距離

1 2 3 4

void?MaxDistance() { }

10. 由前序，中序遍歷重建二叉樹(前序：1, 2，3, 4, 5, 6；中序：3, 2, 4, 1, 5, 6)

1 2 3 4 5 6 7 8 9 10 11 12

BinaryTreeNode*?RebuildBinaryTree(int*?pPrevOrder,?int*?pInOrder,?size_t?length) { ????if?(pPrevOrder?==?NULL?||?pInOrder?==?NULL?||?length?<=?0) ????{ ????????return?NULL; ????} ????return?ConstructCore(pPrevOrder,?pPrevOrder?+?length?-?1,?pInOrder,?pInOrder?+?length?-?1); } BinaryTreeNode*?ConstructCore(int*?startPrevOrder,??int*?startInOrder) { }

11.判斷是否是完全二叉樹

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45

bool?_IsCompleteBinaryTree(BinaryTreeNode<T>*?root) { ????//空樹也算作是完全二叉樹 ????if?(root?==?NULL) ????????return?true; ????queue<BinaryTreeNode<T>*>?q; ????q.push(root); ????bool?NextNoChild?=?false; ????bool?result?=?true; ????????? ????while(!q.empty()) ????{ ????????BinaryTreeNode<T>*?pNode?=?q.front(); ????????q.pop(); ????????if?(NextNoChild) ????????{ ????????????if?(pNode->_left?!=?NULL?||?pNode->_right?!=?NULL) ????????????{ ????????????????result?=?false; ????????????????break; ????????????} ????????} ????????else?if?(pNode->_left?!=?NULL?&&?pNode->_right?!=?NULL) ????????{ ????????????q.push(pNode->_left); ????????????q.push(pNode->_right); ????????} ????????else?if?(pNode->_left?!=?NULL?&&?pNode->_right?==?NULL) ????????{ ????????????q.push(pNode->_left); ????????????NextNoChild?=?true; ????????} ????????else?if?(pNode->_left?==?NULL?&&?pNode->_right?!=?NULL) ????????{ ????????????return?false; ????????????break; ????????} ????????else ????????{ ????????????NextNoChild?=?true; ????????} ????} ????return?result; }

12.求二叉樹的鏡像

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43

//遞歸實現 void?_TreeMirror(BinaryTreeNode<T>*?root) { ????if?(root?==?NULL?||?(root->_left?==?NULL?&&?root->_right?==?NULL)) ????{ ????????return; ????} ????swap(root->_left,?root->_right); ????if?(root->_left) ????????_TreeMirror(root->_left); ????if?(root->_right) ????????_TreeMirror(root->_right); } //非遞歸實現 void?_TreeMirror_NonR(BinaryTreeNode<T>*?root) { ????if?(root?==?NULL) ????return; ????stack<BinaryTreeNode<T>?*>?s; ????s.push(root); ????while?(s.size()) ????{ ????????BinaryTreeNode<T>*?pNode?=?s.top(); ????????s.pop(); ????????if?(NULL?!=?pNode->_left?||?NULL?!=?pNode->_right) ????????{ ????????????BinaryTreeNode<T>?*pTemp?=?pNode->_left; ????????????pNode->_left?=?pNode->_right; ????????????pNode->_right?=?pTemp; ????????????//swap(pNode->_left,?pNode->_right); ????????} ????????if?(NULL?!=?pNode->_left) ????????????s.push(pNode->_left); ????????if?(NULL?!=?pNode->_right) ????????????s.push(pNode->_right); ????} }

13.將二叉搜索樹轉換為雙向鏈表

1 2 3 4

void?ToList() { }

本文轉自 七十七快 51CTO博客，原文鏈接:http://blog.51cto.com/10324228/1785322
與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的二叉树面试题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。