1. 樹與樹的遍歷

樹是一種在實際編程中經常遇到的數據結構，它的邏輯結構很簡單：除了根節點之外每個節點只有一個父節點，根節點沒有父節點；除了葉節點之外所有節點都有一個或者多個子節點，葉節點沒有子節點。父節點和子節點之間用指針鏈接。所謂的二叉樹是樹的一種特殊結構，在二叉樹中每個節點最多只能有兩個子節點。二叉樹最重要的莫過于遍歷，即按照某一順序訪問樹中的搜有的節點。通常樹有三種遍歷方式。

• 前序遍歷：根節點-左子節點-右子節點。上圖的遍歷順序為：10-6-4-8-14-12-16；
• 中序遍歷：左子節點-根節點-右子節點。上圖的遍歷順序為：4-6-8-10-12-14-16
• 后序遍歷：左子節點-右子節點-根節點。上圖的遍歷順序為：4-8-6-12-16-14-10
• 寬度優先遍歷：自上到下，自左到右。 上圖的遍歷順序為：10-6-14-4-8-12-16

二叉搜索樹是二叉樹中的一個特例。在二叉搜索樹中，左子節點總是小于或者等于根節點，右子節點總是大于等于根節點。上圖實際上就是一棵二叉搜索樹。可以再平均O(logn)時間內根據數值在二叉搜索樹中找到一個節點。

二叉樹還有兩個特例。分別是堆和紅黑樹。堆分為最大堆和最小堆。在最大堆中，根節點的值最大，在最小隊中，根節點的值最小。很多需要快速查找到最大值最小值的問題都可以通過堆來實現。紅黑樹是把樹中的結點定義為紅、黑兩種顏色，并通過確定規則使得從根節點到葉節點的最常路徑的長度不差偶偶最短路徑的二倍。在C++的STL中，set, multiset, map, multimap等數據結構都是結余紅黑樹實現的。

2.利用前序遍歷和中序遍歷重建二叉樹

原理：

1.前序遍歷的第一個值對應的就是節點；

2.利用該節點可以在中序遍歷中劃分左子樹和左子樹；

3.劃分子樹結束后，回到前序遍歷中又可以判斷節點，遞歸的過程；

#include "BinaryTree.h" #include <exception> #include <stdio.h> #include <stdlib.h> using namespace std;BinaryTreeNode* ConstructCore(int* startPreorder, int* endPreorder, int* startInorder, int* endInorder);BinaryTreeNode* Construct(int* preorder, int* inorder, int length) {if (preorder == NULL || inorder == NULL || length <= 0)return NULL;return ConstructCore(preorder, preorder + length - 1,inorder, inorder + length - 1); }BinaryTreeNode* ConstructCore ( int* startPreorder, int* endPreorder, int* startInorder, int* endInorder ) {// 前序遍歷序列的第一個數字是根結點的值int rootValue = startPreorder[0];BinaryTreeNode* root = new BinaryTreeNode();root->m_nValue = rootValue;root->m_pLeft = root->m_pRight = NULL;if (startPreorder == endPreorder){if (startInorder == endInorder && *startPreorder == *startInorder)return root;elsethrow std::exception("Invalid input.");}// 在中序遍歷中找到根結點的值int* rootInorder = startInorder;while (rootInorder <= endInorder && *rootInorder != rootValue)++rootInorder;if (rootInorder == endInorder && *rootInorder != rootValue)throw std::exception("Invalid input.");int leftLength = rootInorder - startInorder;int* leftPreorderEnd = startPreorder + leftLength;if (leftLength > 0){// 構建左子樹root->m_pLeft = ConstructCore(startPreorder + 1, leftPreorderEnd,startInorder, rootInorder - 1);}if (leftLength < endPreorder - startPreorder){// 構建右子樹root->m_pRight = ConstructCore(leftPreorderEnd + 1, endPreorder,rootInorder + 1, endInorder);}return root; }// ====================測試代碼==================== void Test(char* testName, int* preorder, int* inorder, int length) {if (testName != NULL)printf("%s begins:\n", testName);printf("The preorder sequence is: ");for (int i = 0; i < length; ++i)printf("%d ", preorder[i]);printf("\n");printf("The inorder sequence is: ");for (int i = 0; i < length; ++i)printf("%d ", inorder[i]);printf("\n");try{BinaryTreeNode* root = Construct(preorder, inorder, length);PrintTree(root);DestroyTree(root);}catch (std::exception& exception){printf("Invalid Input.\n");} }// 普通二叉樹 // 1 // / \ // 2 3 // / / \ // 4 5 6 // \ / // 7 8 void Test1() {const int length = 8;int preorder[length] = { 1, 2, 4, 7, 3, 5, 6, 8 };int inorder[length] = { 4, 7, 2, 1, 5, 3, 8, 6 };Test("Test1", preorder, inorder, length); }// 所有結點都沒有右子結點 // 1 // / // 2 // / // 3 // / // 4 // / // 5 void Test2() {const int length = 5;int preorder[length] = { 1, 2, 3, 4, 5 };int inorder[length] = { 5, 4, 3, 2, 1 };Test("Test2", preorder, inorder, length); }// 所有結點都沒有左子結點 // 1 // \ // 2 // \ // 3 // \ // 4 // \ // 5 void Test3() {const int length = 5;int preorder[length] = { 1, 2, 3, 4, 5 };int inorder[length] = { 1, 2, 3, 4, 5 };Test("Test3", preorder, inorder, length); }// 樹中只有一個結點 void Test4() {const int length = 1;int preorder[length] = { 1 };int inorder[length] = { 1 };Test("Test4", preorder, inorder, length); }// 完全二叉樹 // 1 // / \ // 2 3 // / \ / \ // 4 5 6 7 void Test5() {const int length = 7;int preorder[length] = { 1, 2, 4, 5, 3, 6, 7 };int inorder[length] = { 4, 2, 5, 1, 6, 3, 7 };Test("Test5", preorder, inorder, length); }// 輸入空指針 void Test6() {Test("Test6", NULL, NULL, 0); }// 輸入的兩個序列不匹配 void Test7() {const int length = 7;int preorder[length] = { 1, 2, 4, 5, 3, 6, 7 };int inorder[length] = { 4, 2, 8, 1, 6, 3, 7 };Test("Test7: for unmatched input", preorder, inorder, length); }int main( ) {Test1();Test2();Test3();Test4();Test5();Test6();Test7();return 0; }

總結

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

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