本文總結了二叉樹常見的題目。 如下是頭文件的部分聲明： ~~~ //tree.h #ifndef TEST_TREE_H #define TEST_TREE_H typedef int ElementType; struct TreeNode; typedef struct TreeNode *Position; typedef struct TreeNode *SearchTree; struct TreeNode { ElementType element; SearchTree left; SearchTree right; }; ... #endif ~~~ 從上述的聲明可以看出Positon、SearchTree均是指向樹型結構的指針，在下面的程序中注意。 如下的程序中，有的是借助二叉搜索樹的性質，因此是二叉樹特有的；而大部分都是二叉樹均有的算法。在每段代碼開頭都注明了是僅用于二叉搜素樹或者是通用的。 # 一、二叉搜索樹一些實現 二叉搜索樹特點：結點左子樹的值均小于右子樹的值。 ~~~ //二叉搜索樹的創建 SearchTree CreateSearchTree(SearchTree tree) { int tree_element; while (cin >> tree_element) { if (tree_element == '*') break; else tree = InsertToTree(tree_element, tree); } return tree; } //二叉搜索樹的查找 Position FindFromTree(ElementType x, SearchTree tree) { ?if (tree == NULL) ??? ?return NULL; ?if (tree->element < x) ??? ?FindFromTree(x, tree->right); ?else if (x < tree->element) ??? ?FindFromTree(x, tree->left); ?else ??? ?return tree; } //尋找二叉搜索樹的最大節點:遞歸和非遞歸 Position FindMax(SearchTree tree) { ?if (tree != NULL) ??? ?while (tree->right != NULL) ??? ??? ?tree = tree->right; ?return tree; } Position FindMax2 (SearchTree tree) { ?if (tree == NULL) ??? ?return NULL; ?else if (tree->right == NULL) ??? ?return tree; ?else ??? ?return FindMax2(tree->right); } //尋找二叉搜索樹的最小節點：遞歸和非遞歸 Position FindMin(SearchTree tree) { ?if (tree != NULL) ??? ?while (tree->left) ??? ??? ?tree = tree->left; ?return tree; } Position FindMin2(SearchTree tree) { ?if (tree == NULL) ??? ?return NULL; ?else if (tree->left == NULL) ??? ?return tree; ?else ??? ?return FindMin(tree->left); } //二叉搜索樹的插入 SearchTree InsertToTree(ElementType x, SearchTree tree) { ?if (tree == NULL) { ??? ?tree = (struct TreeNode*)malloc(sizeof(struct TreeNode)); ??? ?if (tree == NULL) { ??? ??? ?cout << "malloc failed" << endl; ??? ?} ??? ?else { ??? ??? ?tree->element = x; ??? ??? ?tree->left = NULL; ??? ??? ?tree->right = NULL; ??? ?} ?} ?else if (x < tree->element) ??? ?tree->left = InsertToTree(x, tree->left); ?else if (x > tree->element) ??? ?tree->right = InsertToTree(x, tree->right); ?return tree; } //二叉搜索樹的刪除 SearchTree DeleteFromTree(ElementType x, SearchTree tree) { ?Position temp; ?if (tree == NULL) { ??? ?cout << "The tree is empty, no element." << endl; ?} ?else if (x < tree->element) {? //尋找要刪除的位置 ??? ?DeleteFromTree(x, tree->left); ?} ?else if (x > tree->element) {? //尋找要刪除的位置 ??? ?DeleteFromTree(x, tree->right); ?} ?else if(tree->left && tree->right) {? //找到要刪除的位置，該節點有兩個孩子 ??? ?temp = FindMin(tree->right); ??? ?tree->element = temp->element; ??? ?tree->right = DeleteFromTree(tree->element, tree->right); ?} ?else { //僅有一個子樹，或者為葉節點 ??? ?temp = tree; ??? ?if (tree->left == NULL) ??? ??? ?tree = tree->right; ??? ?else if (tree->right == NULL) ??? ??? ?tree = tree->left; ??? ?free(temp); ?} ?return tree; } ~~~ # 二、二叉樹的遍歷 二叉樹的遍歷基本操作就是訪問結點，無論按照哪一種次序進行遍歷，對含有n個結點的二叉樹，其時間復雜度均為O(n)。所需輔助空間為遍歷過程中棧的最大容量，即樹的深度，最壞情況下為n，則最壞空間復雜度為O(n)。 這里的遍歷僅僅是控制臺打印樹結點的值，由下面函數完成： ~~~ void VisitTreeElement(SearchTree tree) { cout << tree->element << " "; } ~~~ ### 1. 先序遍歷 先序遍歷是在元素入棧前，先訪問該元素；然后將此節點入棧，再遍歷其左子樹；遍歷完左子樹后，從棧中彈出該元素，然后根據該元素的右子樹指針去遍歷該節點的右子樹結構。給出了遞歸算法和幾種非遞歸算法（大同小異，使用輔助棧）。 ~~~ //先序遍歷的遞歸方法 void PreOrderTraversalRecursion(SearchTree tree) { if (tree == NULL) { return; } VisitTreeElement(tree); PreOrderTraversalRecursion(tree->left); PreOrderTraversalRecursion(tree->right); } //先序遍歷的非遞歸方法（一） void PreOrderTraversal(SearchTree tree) { ?if (tree == NULL) ??? ?return; ?stack<SearchTree> stk; ?Position cur = tree; ?while (cur != NULL || !stk.empty()) { ??? ?while (cur != NULL) { ??? ??? ?VisitTreeElement(cur); ??? ??? ?stk.push(cur); ??? ??? ?cur = cur->left; ??? ?} ??? ?//if (!stk.empty()) { ??? ?cur = stk.top(); ??? ?stk.pop(); ??? ?cur = cur->right; ??? ?//} ?} } //先序遍歷的非遞歸方法（二） void PreOrderTraversal2(SearchTree tree) { ?if (tree == NULL) ??? ?return; ?stack<SearchTree> stk; ?stk.push(tree); ?while(!stk.empty()) { ??? ?Position top_node = stk.top(); ??? ?VisitTreeElement(top_node); ??? ?stk.pop(); ??? ?if (top_node->right) ??? ??? ?stk.push(top_node->right); ??? ?if (top_node->left) ??? ??? ?stk.push(top_node->left); ?} } //先序遍歷的非遞歸方法（三） void PreOrderTraversal3(SearchTree tree) { ?if (tree == NULL) ??? ?return; ?stack<SearchTree> stk; ?while (tree) { ??? ?stk.push(tree); ??? ?VisitTreeElement(tree); ??? ?tree = tree->left; ?} ?while (!stk.empty()) { ??? ?Position top_node_right = stk.top()->right; ??? ?stk.pop(); ??? ?while (top_node_right) { ??? ??? ?VisitTreeElement(top_node_right); ??? ??? ?stk.push(top_node_right); ??? ??? ?top_node_right = top_node_right->left; ??? ?} ?} } ~~~ ### 2. 中序遍歷 中序遍歷遇到一個元素，先將其入棧，并遍歷其左子樹。遍歷完左子樹，從棧中彈出元素并訪問，然后按照該元素指示的其右孩子去遍歷右子樹。 其實前序和中序遍歷僅僅是訪問元素的時機不同，前者是入棧時就訪問，后者是在出棧時訪問。下面非遞歸中序遍歷的兩種方式分別與前序非遞歸的第（一）、第（三）種方式類似。 ~~~ //中序遍歷的遞歸方法 void InOrderTraversalRecursion(SearchTree tree) { if (tree == NULL) return; InOrderTraversalRecursion(tree->left); VisitTreeElement(tree); InOrderTraversalRecursion(tree->right); } //中序遍歷的非遞歸方法（一），類似前序非遞歸遍歷（一） void InOrderTraversal(SearchTree tree) { ?if (tree == NULL) ??? ?return; ?stack<SearchTree> stk; ?Position cur = tree; ? ?while (cur != NULL || !stk.empty()) { ??? ?while (cur != NULL) { ??? ??? ?stk.push(cur); ??? ??? ?cur = cur->left; ??? ?} ??? ?//if (!stk.empty()) { ??? ?cur = stk.top(); ??? ?VisitTreeElement(cur); ??? ?stk.pop(); ??? ?cur = cur->right; ??? ?//} ?} } //中序遍歷的非遞歸方法（二），類似前序非遞歸遍歷（三） void InOrderTraversal2(SearchTree tree) { ?if (tree == NULL) ??? ?return; ?stack<SearchTree> stk; ?while (tree) { ??? ?stk.push(tree); ??? ?tree = tree->left; ?} ?while (!stk.empty()) { ??? ?Position top_node_right = stk.top()->right; ??? ?VisitTreeElement(stk.top()); ??? ?stk.pop(); ??? ?while (top_node_right) { ??? ??? ?stk.push(top_node_right); ??? ??? ?top_node_right = top_node_right->left; ??? ?} ?} } ~~~ ### 3. 后序遍歷 后序遍歷遇到一個元素，將其入棧，遍歷其左子樹。遍歷結束后，不能立即訪問棧頂節點，而要遍歷右子樹。遍歷完右子樹后才能訪問該元素。另外，當從棧中彈出一個元素時，還要判斷該棧頂元素是從左邊返回的（這樣要繼續訪問其右子樹），還是從右邊返回的（這時該元素左右子樹均訪問過了）。 ~~~ //后序遍歷遞歸算法 void PostOrderTraversalRecursion(SearchTree tree) { ?if (tree == NULL) ??? ?return; ?PostOrderTraversalRecursion(tree->left); ?PostOrderTraversalRecursion(tree->right); ?VisitTreeElement(tree); } //后序非遞歸方法（一） void PostOrderTraversal(SearchTree tree) { stack<SearchTree> stk; Position cur = tree; Position visited = NULL; //指向前一個訪問的節點 while (cur != NULL || !stk.empty()) { while (cur != NULL) { //一直遍歷左子樹 stk.push(cur); cur = cur->left; } cur = stk.top(); //如果當前節點的右樹為空或者右樹已經訪問過了， //直接訪問該節點并彈出該節點 if (cur->right == NULL || cur->right == visited) { VisitTreeElement(cur); visited = cur; stk.pop(); cur = NULL; } else //否則遍歷右子樹 cur = cur->right; } } //后序非遞歸方法（二） void PostOrderTraversal2(SearchTree tree) { stack<SearchTree> s1, s2; Position cur; s1.push(tree); while (!s1.empty()) { cur = s1.top(); s1.pop(); s2.push(cur); if (cur->left) s1.push(cur->left); if (cur->right) s1.push(cur->right); } while (!s2.empty()) { VisitTreeElement(s2.top()); s2.pop(); } } ~~~ ### 4. 層次遍歷 ### 1、所有元素依次輸出，不換行 和以上三種遍歷方式不同：層次遍歷使用的輔助結構是隊列，先序、中序、后序遍歷都使用輔助結構棧。 ~~~ //層次遍歷，入隊前訪問或出隊前訪問均可 void LevelTraversal(SearchTree tree) { queue<SearchTree> q; VisitTreeElement(tree); q.push(tree); while (!q.empty()) { Position cur = q.front(); q.pop(); if (cur->left) { VisitTreeElement(cur->left); q.push(cur->left); } if (cur->right) { VisitTreeElement(cur->right); q.push(cur->right); } } } ~~~ ### 2、每行輸出樹的一層元素 參考：[http://www.cnblogs.com/miloyip/archive/2010/05/12/binary_tree_traversal.html](http://www.cnblogs.com/miloyip/archive/2010/05/12/binary_tree_traversal.html) ~~~ //每行輸出一層節點的各個元素 //方法一： //利用vector充當隊列，兩個指針current和last分別指向vector //中某層樹元素的第一個和最后一個，當current < last時，依次遍歷 //本層每個元素 typedef struct Tree{ Tree* left; Tree* right; int value; } Tree, Node; void PrintNodeByLevel(Tree* tree) { if (tree == NULL) return; vector<Node*> vec; int current = 0, last = 1; vec.push_back(tree); while (current < vec.size()) { last = vec.size(); while (current < last) { cout << vec[current] -> value << " "; if (vec[current]->left) vec.push_back(vec[current]->left); if (vec[current]->right) vec.push_back(vec[current]->right); ++current; } cout << endl; } } //方法二： //http://www.cnblogs.com/miloyip/archive/2010/05/12/binary_tree_traversal.html //每層遍歷結束，在隊列中插入一個空指針，標志本層結束需要輸出換行 void PrintNodeByLevel2(Tree* tree) { if (tree == NULL) return; queue<Node *> q; q.push(tree); while (!q.empty()) { Node * node = q.front(); q.pop(); if (node) { cout << node->value << " "; if (node->left) q.push(node->left); if (node->right) q.push(node->right); } else if (!q.empty()) { //當發現是空指針時要判斷隊列還有沒有元素，否則死循環 q.push(NULL); cout << endl; } } return; } ~~~ 注意一點，當發現空指針(結束信號)時，要檢查隊列內是否還有節點，如果沒有的話還插入新的結束信號，則會做成死循環。 # 三、二叉樹的清空 清空操作是刪除樹的所有結點、釋放內存。后序遍歷方式，遞歸刪除左右子樹，然后刪除根節點。 ~~~ //二叉樹的清空操作 SearchTree MakeEmptyTree(SearchTree tree) { if (tree != NULL) { MakeEmptyTree(tree->left); MakeEmptyTree(tree->right); free(tree); } return NULL; } ~~~ # 四、二叉樹的復制和鏡像 ~~~ //二叉樹的拷貝 SearchTree CopyTree(SearchTree tree) { if (NULL == tree) return NULL; SearchTree pleft = CopyTree(tree->left); SearchTree pright = CopyTree(tree->right); tree->left = pleft; tree->right = pright; return tree; } //二叉樹的鏡像 offerT19 void MirrorTree(SearchTree tree) { ?if (NULL == tree) ??? ?return; ?if (NULL == tree->left && NULL == tree->right) ??? ?return; ?SearchTree temp = tree->left; ?tree->left = tree->right; ?tree->right = temp; ?if (tree->left) ??? ?MirrorTree(tree->left); ?if (tree->right) ??? ?MirrorTree(tree->right); } ~~~ 如下圖是二叉樹鏡像求解過程，先交換根的左右子樹，然后遞歸交換子樹。  # 五、二叉樹和為某一值的路徑 題目：輸入二叉樹和一個整數，求路徑上結點的和等于輸入的整數的路徑。二叉樹的路徑是指，從根節點往下一直到葉節點所經過的節點形成的一條路徑。 思路：用先序遍歷，訪問到某結點將其加入到路徑上，并累加該結點的值。如果訪問的不是葉結點，則繼續訪問其子樹；如果訪問到葉結點而且路徑上的值等于輸入的整數，那么這條路徑就是符合要求的，將其打印出來。當遞歸函數退出時，自動回到了它的父節點，因此我們在函數退出時要在路徑上刪除當前結點并減去當前結點的值。 如下代碼并沒有使用stack完成棧的功能，因為打印路徑要遍歷棧結構，而stack是不可以遍歷的，因此使用vector來模擬棧。 ~~~ //offerT25 //打印二叉樹中和為某一值的路徑 void FindPathCore(SearchTree tree, int sum, vector<int>& path, int sum_current); void FindPath(SearchTree tree, int sum) { if (NULL == tree) return; vector<int> path; //模擬棧，保存路徑 int sum_current = 0; FindPathCore(tree, sum, path, sum_current); } void FindPathCore(SearchTree tree, int sum, vector<int>& path, int sum_current) { sum_current += tree->element; path.push_back(tree->element); bool isleef = (tree->left == NULL && tree->right == NULL); if (isleef && sum_current == sum) { cout << "a path: "; vector<int>::iterator iter = path.begin(); while (iter != path.end()) cout << *iter++ << " "; cout << endl; } if (tree->left) FindPathCore(tree->left, sum, path, sum_current); if (tree->right) FindPathCore(tree->right, sum, path, sum_current); path.pop_back(); } ~~~ # 六、將二叉樹轉換為雙向鏈表 題目：輸入二叉搜索樹，將其轉換為一個排序的雙向鏈表。要求不創建任何新結點，僅調整樹中結點指針的指向。 思路：按照二叉搜索樹的中序遍歷，得到的就是排序的序列；這里要求鏈表排序，因此也是中序遍歷的思路。如果沒有要求鏈表排序，當然不必非要按中序遍歷。 如下圖所示，按照中序遍歷左子樹，當遍歷到根結點（值為10）時，它的左子樹已經轉換為了排序的雙向鏈表，并且處在鏈表最后一個結點的是當前最大的結點。將值為8的結點和根結點連接起來，此時鏈表最后一個結點就是10了。然后，遍歷右子樹，并將根結點和右子樹最小的結點連接起來。如何轉換左右子樹，按照上述思路遞歸即可。  ~~~ //offerT27 //二叉搜素樹和雙向鏈表(中序遍歷) void CovertTreetoListCore(SearchTree tree, SearchTree* last_listnode); SearchTree CovertTreetoList(SearchTree tree) { SearchTree last_listnode = NULL; CovertTreetoListCore(tree, &last_listnode); //last_listnode指向雙向鏈表尾部，這里將其指向頭部 SearchTree head_list = last_listnode; while (head_list && head_list->left != NULL) head_list = head_list->left; return head_list; } //函數第二個參數是指針的指針 void CovertTreetoListCore(SearchTree tree, SearchTree* last_listnode) { if (NULL == tree) return; SearchTree current = tree; if (current->left) CovertTreetoListCore(current->left, last_listnode); current->left = *last_listnode; if (*last_listnode) (*last_listnode)->right = current; *last_listnode = current; if (current->right) CovertTreetoListCore(current->right, last_listnode); } ~~~ # 七、求二叉樹的深度 下面的幾個例子會用到求深度的算法。 ~~~ //求二叉樹的深度 int GetNodeDeepth(SearchTree tree) { if (tree == NULL) return 0; int deepth_left = GetNodeDeepth(tree->left); int deepth_right = GetNodeDeepth(tree->right); return deepth_right > deepth_left ? (deepth_right + 1): (deepth_left + 1); } ~~~ # 八、判斷二叉樹是不是平衡二叉樹 offerT39 思路一：遍歷樹的每個結點，得到其左右子樹的深度，如果某個結點左右子樹深度之差超過1，該數就不是平衡樹；否則是。該思路要多次重復遍歷一個結點，效率很低。 思路二：如果某個樹不是平衡樹，那么它在根結點處就肯定不是平衡樹。所以，后序遍歷一次二叉樹，求出二叉樹左右的最大和最小深度，如果根的左右子樹深度相差超過1，那么 樹不是平衡二叉樹。 如下，使用Depth結構存儲節點左右子樹的最大和最小深度。如果根的左右子樹中，最大和最小深度相差不超過1，該樹是平衡二叉樹。 ~~~ //Depth結構用于存儲根結點的最大和最小深度 struct Depth { int min_depth; int max_depth; }; //函數返回根結點的最大和最小深度 Depth GetDepth(SearchTree tree) { if (NULL == tree) { Depth empty = {0, 0}; return empty; } Depth lhs = GetDepth(tree->left); Depth rhs = GetDepth(tree->right); Depth depth; depth.max_depth = 1 + max(lhs.max_depth, rhs.max_depth); depth.min_depth = 1 + min(lhs.min_depth, rhs.min_depth); return depth; } bool IsBalancedTree2(SearchTree tree) { Depth depth = GetDepth(tree); //如果根結點的最大深度和最小深度之差不超過1為平衡二叉樹 if (depth.max_depth - depth.min_depth > 1) return false; else return true; } ~~~ 思路三：用后序遍歷的方式遍歷二叉樹，在遍歷到一個節點前，已經遍歷了它的左右子樹。那么首先判斷結點左右子樹是否平衡，若左右子樹均平衡了，然后該該結點處也平衡了，那么，該樹才是平衡的；如果左右子樹有一個不平衡，就直接返回false，相對于思路二需要遍歷的節點數目會少，雖然這兩種思路復雜度都是O（n）。 ~~~ //offerT39 //判斷一棵樹是不是平衡樹（后序遍歷） bool IsBalancedTreeCore(SearchTree tree, int *depth); bool IsBalancedTree(SearchTree tree) { int depth = 0; return IsBalancedTreeCore(tree, &depth); } bool IsBalancedTreeCore(SearchTree tree, int *depth) { if (NULL == tree) { *depth = 0; return true; } int depth_left, depth_right; if (IsBalancedTreeCore(tree->left, &depth_left) && IsBalancedTreeCore(tree->right, &depth_right)) { int diff = depth_left - depth_right; if (diff >= -1 && diff <= 1) { *depth = (depth_left > depth_right ? depth_left : depth_right) + 1; return true; } } return false; } ~~~ # 九、求二叉樹中節點的最大距離 即二叉樹中相距最遠的兩個節點之間的距離。 遞歸解法： （1）如果二叉樹為空，返回0，同時記錄左子樹和右子樹的深度，都為0 （2）如果二叉樹不為空，最大距離要么是左子樹中的最大距離，要么是右子樹中的最大距離，要么是左子樹節點中到根節點的最大距離+右子樹節點中到根節點的最大距離，同時記錄左子樹和右子樹節點中到根節點的最大距離。 方法一： ~~~ //求二叉樹中結點的最大距離 struct Result { int max_distance; int max_depth; }; Result GetMaxDistanceCore(SearchTree tree); int GetMaxDistance(SearchTree tree) { return GetMaxDistanceCore(tree).max_distance; } Result GetMaxDistanceCore(SearchTree tree) { if (NULL == tree) { //最大深度初始化為-1是因為調用這對其加1，然后變為0 Result empty = {0, -1}; return empty; } Result lhs = GetMaxDistanceCore(tree->left); Result rhs = GetMaxDistanceCore(tree->right); Result result; result.max_depth = max(lhs.max_depth + 1, rhs.max_depth + 1); result.max_distance = max(max(lhs.max_distance, rhs.max_distance), lhs.max_depth + rhs.max_depth + 2); return result; } ~~~ 方法二： 該代碼更簡單，要調用求二叉樹深度的函數GetNodeDepth： ~~~ int GetMaxDistance2(TreeNode * pRoot){ if (pRoot == NULL) return 0; return max(GetNodeDeepth(pRoot->left) + GetNodeDeepth(pRoot->right), GetMaxDistance2(pRoot->left), GetMaxDistance2(pRoot->right)); } ~~~ # 十、由先序遍歷和后序遍歷，構造二叉樹 題目：輸入兩個序列，分別表示先序遍歷和后序遍歷的結果，構造二叉樹。下一題也是這個思路。 ~~~ //由先序和中序遍歷構造二叉樹 Position ConstructBiTreeCore(int *startPreOrder, int *endPreorder, int *startInorder, int *endInorder) { int root_value = startPreOrder[0]; Position root = (struct TreeNode*)malloc(sizeof(struct TreeNode)); if (root == NULL) return NULL; root->element = root_value; root->right = root->left = NULL; if (startPreOrder == endPreorder) { if (startInorder == endInorder && *startInorder == *startPreOrder) return root; else { //當輸入序列不符合要求時，返回NUll之前釋放root，以免內存泄露 free(root); return NULL; } } int *rootInorder = startInorder; while (rootInorder <= endInorder && *rootInorder != root_value) ++rootInorder; int left_len = rootInorder - startInorder; int *leftPreOrderEnd = startPreOrder + left_len; if (left_len > 0) { root->left = ConstructBiTreeCore(startPreOrder + 1, leftPreOrderEnd, startInorder, rootInorder - 1); } if (left_len < endPreorder - startPreOrder) { root->right = ConstructBiTreeCore(leftPreOrderEnd + 1, endPreorder, rootInorder + 1, endInorder); } return root; } Position ConstructBiTree(int *preorder, int *inorder, int len) { ?if (preorder == NULL || inorder == NULL || len <= 0) ??? ?return NULL; ?return ConstructBiTreeCore(preorder, preorder + len - 1, ??? ?inorder, inorder + len - 1); } ~~~ # 十一、根據先序遍歷和中序遍歷，求后序遍歷序列 和上一題的思路一模一樣，只是這里僅求后序序列，不用構建二叉樹。 先序遍歷的第一個結點在后序遍歷中是最后一個結點（此結點時根結點），因此遞歸遍歷根的左子樹和右子樹：在左右子樹遍歷中，左子樹會先于根輸出，右子樹在左子樹后輸出，最后輸出根（這恰好就是后序遍歷的最后一個元素）。于是后序遍歷序列輸出完成。 ~~~ //根據先序遍歷和中序遍歷求后序遍歷(和上題構造二叉樹原理一樣) void PrintPostOrderCore(int *startPreorder, int *endPreorder, ?int *startInorder, int *endInorder) { ?int root_value = startPreorder[0]; ?//當先序遍歷和后序遍歷僅有一個元素且該元素相等時，輸出 ?//否則是非法輸入 ?if (startPreorder == endPreorder) { ??? ?if (startInorder == endInorder && *startPreorder == *startInorder) { ??? ??? ?cout << root_value << " "; ??? ?} ??? ?else { ??? ??? ?throw exception("invalid input"); ??? ?} ?} ?//在中序遍歷中尋找根的位置 ?int *rootInorder = startInorder; ?while (rootInorder <= endInorder && *rootInorder != root_value) ??? ?++rootInorder; ?//遞歸遍歷左右子樹 ?int left_length = rootInorder - startInorder; ?int *leftPreorderEnd = startPreorder + left_length; ?if (left_length > 0) ??? ?PrintPostOrderCore(startPreorder + 1, leftPreorderEnd, ??? ?????? startInorder, rootInorder - 1); ?if (left_length < endPreorder - startPreorder) ??? ?PrintPostOrderCore(leftPreorderEnd + 1, endPreorder, ??? ?????? rootInorder + 1, endInorder); ? ?//左右子樹輸出完成后，在輸出根結點值 ?cout << root_value << " "; } void PrintPostOrder(int *preorder, int *inorder, int length) { if (preorder == NULL || inorder == NULL || length <= 0) return; PrintPostOrderCore(preorder, preorder + length - 1, inorder, inorder + length -1); } ~~~ # 十二、判斷是否為二叉搜索樹的后序遍歷序列 題目：判斷輸入的序列是不是一個二叉搜索樹的后序遍歷序列。 思路：后序遍歷時，最后遍歷的是根結點。二叉搜索樹根節點值大于所以左子樹的值，且小于所以右子樹的值；在子樹中遞歸利用此性質，如果不滿足，那么就不是二叉搜索樹的后序遍歷序列。 ~~~ //offerT24 //判斷某個整數數組是不是一個二叉搜索樹的后序遍歷序列 bool IsPostOrderBST(int array[], int length) { if (length < 1 || array == NULL) return false; int root = array[length - 1]; int length_left = 0; for ( ; length_left < length - 1; ++length_left) { if (array[length_left] > root) break; } int pos_right = length_left; for ( ; pos_right < length - 1; ++pos_right) { if (array[pos_right] < root) return false; } //判斷左子樹是不是BST的后序遍歷序列 bool result_left = true; if (length_left > 0) result_left = IsPostOrderBST(array, length_left); //判斷右子樹是不是BST的后序遍歷序列 bool result_right = true; if (length_left < length - 1) result_right = IsPostOrderBST(array + length_left, length - length_left - 1); return (result_left && result_right); } ~~~ # 十三、判斷兩棵樹是否相等 ~~~ //二叉樹A和B，判斷A和B是否相等 bool EqualBinaryTree(SearchTree treea, SearchTree treeb) { if (treea == NULL && treeb == NULL) return true; if ((!treea && treeb) || (treea && !treeb)) return false; if (treea->element == treeb->element) { return EqualBinaryTree(treea->left, treeb->left) && EqualBinaryTree(treea->right, treeb->right); } return false; } //二叉樹A和B，判斷可以旋轉的A和B是否相等,旋轉是指左右子樹可交換 bool EqualBinaryTree2(SearchTree treea, SearchTree treeb) { if (treea == NULL && treeb == NULL) return true; if ((!treea && treeb) || (treea && !treeb)) return false; if (treea->element == treeb->element) { return (EqualBinaryTree2(treea->left, treeb->left) && EqualBinaryTree2(treea->left, treeb->left)) || (EqualBinaryTree2(treea->left, treeb->right) && EqualBinaryTree2(treea->right, treeb->left)); } return false; } ~~~ # 十四、判斷一棵樹是不是另一棵樹的子樹 ~~~ //offerT18 //二叉樹A和B，判斷B是不是A的子結構 bool SubTreeCore(SearchTree treea, SearchTree treeb) { if (treeb == NULL) return true; if (treea == NULL) return false; if (treea->element != treeb->element) return false; return SubTreeCore(treea->left, treeb->left) && SubTreeCore(treeb->right, treeb->right); } bool IsSubTree(SearchTree treea, SearchTree treeb) { bool result = false; if (treea && treeb) { if (treea->element == treeb->element) result = SubTreeCore(treea, treeb); if (!result) result = IsSubTree(treea->left, treeb); if (!result) result = IsSubTree(treea->right, treeb); } return result; } ~~~ # 十五、判斷二叉樹是不是完全二叉樹 思路：如果一棵樹是完全二叉樹，那么，如果某個結點只有右孩子，樹不是完全的；如果某個結點只有左孩子，只有當層次遍歷時，該結點之后所有結點都是葉子結點時，樹才是完全的；如果某個結點是葉子結點，那么按照層次遍歷時，其后的結點必須都是葉子結點，那么樹才是完全的。 ~~~ //判斷二叉樹是不是完全二叉樹 bool IsCompletedTree(SearchTree tree) { if (NULL == tree) return false; bool result = true; bool must_leaf = false; queue<SearchTree> nodes; nodes.push(tree); while (!nodes.empty()) { SearchTree node = nodes.front(); nodes.pop(); //如果某節點只有左子樹，那么按照層次遍歷時 //其后結點必須全為葉子結點，否則該樹不是完全二叉樹 if (must_leaf) { if (node->left || node->right) { result = false; break; } } else { if (node->left && node->right) { nodes.push(node->left); nodes.push(node->right); } else if (node->left && ! node->right) { must_leaf = true; nodes.push(tree->left); } else if (!node->left && node->right) { result = false; break; } else must_leaf = true; } } return true; } ~~~ # 十六、求樹中兩個節點的最低公共祖父 offerT50 ### 1、如果是在二叉搜索樹中 如果是二叉搜索樹，那么左子樹元素均小于根，右子樹均大于根。 那么從根開始和輸入的兩個結點比較： ?????? 如果當前結點比輸入的兩個數都大，那么最低公共祖先一定在當前結點的左子樹中，于是下一步遍歷當前結點的左子樹結點。 ?????? 如果當前結點的值比兩個輸入結點都小，那么最低公共祖先在右子樹，下一步遍歷右子樹結點。 ????? 這樣，從樹中找到第一個在兩個輸入結點值之間的結點，就是最低公共祖父節點。 ### 2、如果不是二叉搜索樹，但是有指向父節點的指針 如果除了根結點外的每個結點都有個一個指向父節點的指針，那么這個問題就可以轉換為[求兩個鏈表的第一個公共結點](http://blog.csdn.net/u013074465/article/details/41452147#t16)。 ### 3、如果沒有指向父節點的指針，普通樹 思路一、思路二：[http://zhedahht.blog.163.com/blog/static/25411174201081263815813/](http://zhedahht.blog.163.com/blog/static/25411174201081263815813/) # 十七、二叉搜索樹的前驅和后繼 ????? 二叉搜索樹按照中序遍歷時，輸出的節點是從小到大排列好的。如果各個節點關鍵字不相等，那么節點x的前驅就是中序遍歷的x的前一個，后繼就是中序遍歷的x的后一個節點。 ????? 尋找節點后繼的思想**：**如果節點的右子樹不為空，其后繼就是右子樹的最小節點；如果節點x右子樹為空，并且該節點有后繼節點y，則y是x的最低的祖先節點，并且y的左兒子也是x的祖先(這里可以認為每個節點都是自己的祖先)。 ????? 如下圖所示，節點13沒有右子樹，而該節點是有后繼的，因此其后繼節點就是其最低的祖先節點，且該祖先節點的左孩子也是其祖先。那么可以判斷13的后繼節點是15。 再比如，節點9沒有右子樹，且該節點有后繼節點；那么13是節點9的后繼節點，此時13的右孩子是節點9自己，此時可以認為9是自己的祖先節點。  同理，對于尋找前驅節點：如果節點x有左子樹，那么其前驅節點就是左子樹中最大的那個節點；如果該節點x沒有左子樹，且該節點存在前驅節點y，則y是x的最低祖先結點，且y的右孩子也是x的祖先（可以認為自己是自己的祖先節點）。 例如上圖中9沒有左子樹，因此其前驅為7，此時7是9的祖先，且7的右節點也是9的祖先。 再比如7的前驅是6，此時6的右孩子（節點7本身）是節點7的祖先節點（7是7本身的祖先節點）。 從上面的分析可以看出，要求出某結點的前驅和后繼節點，都需要指向結點父親的指針，如果有指向父節點的指針，那么，問題就很容易了，代碼參考[STL源碼：紅黑樹](http://blog.csdn.net/u013074465/article/details/44751877#t3)。 偽代碼如下： 找后繼： ~~~ TREE-SUCCESSOR(x) if rithx[x]≠NIL then return TREE-MINIMUM(right[x]) y←p[x] while y≠NIL and x=right[y] do x←y y←p[y] return y ~~~ 找前驅： ~~~ TREE-PREDECESSOR(x) if left[x]≠NIL then return TREE-MAXMUM(left[x]) y←p[x] while y≠NIL and x=left[x] do x←y y←p[y] return y ~~~