按層次遍歷二元樹
問題描述：輸入一顆二元樹，從上往下按層打印樹的每個結點，同一層中按照從左往右的順序打印。
例如輸入：
8 / / 6 10/ / / /5 7 9 11
輸出
8 6 10 5 7 9 11
定義二元樹（其實是二元搜索樹，但并不遍歷算法）的結點為：
struct BSTreeNode { int value; BSTreeNode *left; BSTreeNode *right; }; 思路：利用隊列的先進先出，很容易實現。每次取出隊列的首元素，然后將其左右子女放入隊列中。直至隊列為空即可。按這種方式進出隊列，正好是按層遍歷二元樹。
參考代碼：
//函數功能 ： 按層次遍歷二元樹 //函數參數 ： pRoot指向根結點 //返回值 ： 無 void LevelReverse(BSTreeNode *pRoot) { if(pRoot == NULL) return; queue<BSTreeNode *> nodeQueue; nodeQueue.push(pRoot); while(nodeQueue.size()) { BSTreeNode * pNode = nodeQueue.front(); //取隊首元素 nodeQueue.pop(); //必須出隊列 if(pNode->left) //左子女 nodeQueue.push(pNode->left); if(pNode->right) //右子女 nodeQueue.push(pNode->right); cout<<pNode->value<<' '; } } 擴展一：上文給出的代碼，所有結點都輸出在同一行。如果希望僅僅同層結點輸出在同一行，該如何修改代碼呢？
思路：如果我們能知道每層的最后一個結點，那么就方便多了，輸出每層最后一個結點的同時，輸出一個換行符。因此，關鍵在于如何標記每層的結束。可以考慮在每層的最后一個點之后，插入一個空結點。比如隊列中先放入根結點，由于第0層只有一個結點，因此放入一個空結點。然后依次取出隊列中的結點，將其子女放入隊列中，如果遇到空結點，表明當前層的結點已遍歷完了，而隊列中放的恰恰是下一層的所有結點。如果當前隊列為空，表明下一層無結點，也就說是所有結點已遍歷好了。如果不為空，那么插入一個空結點，用于標記下一層的結束。
參考代碼：
void LevelReverse(BSTreeNode *pRoot) { if(pRoot == NULL) return; queue<BSTreeNode *> nodeQueue; nodeQueue.push(pRoot); nodeQueue.push(NULL); //放入空結點，作為層的結束符 while(nodeQueue.size()) { BSTreeNode * pNode = nodeQueue.front(); //取隊首元素 nodeQueue.pop(); //必須出隊列 if(pNode) { if(pNode->left) //左子女 nodeQueue.push(pNode->left); if(pNode->right) //右子女 nodeQueue.push(pNode->right); cout<<pNode->value<<' '; } else if(nodeQueue.size()) //如果結點為空并且隊列也為空，那么所有結點都已訪問 { nodeQueue.push(NULL); cout<<endl; } } } 擴展二：之前討論的都是從上往下、從左往右遍歷二叉樹，那么如果希望自下往上、從左右往右遍歷二叉樹，該如何修改代碼呢？
思路：比較簡單的方法，首先遍歷二叉樹，將所有結點保存在一個數組中，遍歷的同時記錄每一層在數組中的起止位置。然后根據起止位置，就可以自下往上的打印二叉樹的結點。
//每層的起止位置 struct Pos { int begin; int end; Pos(int b, int e): begin(b),end(e) {} }; void LevelReverse(BSTreeNode *pRoot) { if(pRoot == NULL) return; vector<BSTreeNode*> vec; //用以存放所有結點 vector<Pos> pos; //用以記錄每層的起止位置 vec.push_back(pRoot); int level = 0; //樹的層數 int cur = 0; int last = 1; while(cur < vec.size()) { last = vec.size(); pos.push_back(Pos(cur, last)); //記錄當前層的起止位置 while(cur < last) //遍歷當前層的結點，將子女放入數組中 { if(vec[cur]->left) //先是左然后是右。如果希望自由向左，交換一下順序即可 vec.push_back(vec[cur]->left); if(vec[cur]->right) vec.push_back(vec[cur]->right); cur++; } level++; //層數加1 } for(int i = level - 1; i >= 0; i--) //自下往上遍歷 { for(int j = pos[i].begin; j < pos[i].end; j++) cout<<vec[j]->value<<' '; cout<<endl; } } 輸入一顆二元查找樹，將該樹轉換為它的鏡像
問題描述：輸入一顆二元查找樹，將該樹轉換為它的鏡像，即在轉換后的二元查找樹中，左子樹的結點都大于右子樹的結點。用遞歸和循環兩種方法完成樹的鏡像轉換。
例如輸入：
8 / / 6 10 // //5 7 9 11
輸出：
8 / / 10 6 // //11 9 7 5
定義二元查找樹的結點為：
struct BSTreeNode { int value; BSTreeNode *left; BSTreeNode *right; }; 思路：題目要求用兩種方法，遞歸和循環，其實質是一樣的。
解法一：用遞歸。假設當前結點為pNode，只需交換該結點的左右子女，然后分別遞歸求解左子樹和右子樹即可。代碼極為簡單。
解法二：用循環，需要一個輔助棧完成，每次取棧頂元素交換左右子女，然后將左右子女分別壓入輔助棧，當棧中元素為空時，結束循環。其實不論是遞歸也好，循環也好，都是利用棧的特性完成。
參考代碼：
//函數功能 ： 輸入一顆二元查找樹，將該樹轉換為它的鏡像 //函數參數 ： pRoot為根結點 //返回值 ： 根結點 BSTreeNode * Mirror_Solution1(BSTreeNode * pRoot) { if(pRoot != NULL) { BSTreeNode * pRight = pRoot->right; BSTreeNode * pLeft = pRoot->left; pRoot->left = Mirror_Solution1(pRight); //轉化右子樹 pRoot->right = Mirror_Solution1(pLeft); //轉化左子樹 } return pRoot; } BSTreeNode * Mirror_Solution2(BSTreeNode * pRoot) { if(pRoot != NULL) { stack<BSTreeNode *> stk; //輔助棧 stk.push(pRoot); //壓入根結點 while(stk.size()) { BSTreeNode *pNode = stk.top(); BSTreeNode *pLeft = pNode->left; BSTreeNode* pRight = pNode->right; stk.pop(); if(pLeft != NULL) stk.push(pLeft); if(pRight != NULL) stk.push(pRight); pNode->left = pRight; //交換左右子女 pNode->right = pLeft; } } return pRoot; } 判斷整數序列是不是二元查找樹的后序遍歷結果
問題描述：輸入一個整數數組，判斷該數組是不是某二元查找樹的后序遍歷的結果。如果是返回true，否則返回false。
例如輸入5、7、6、9、11、10、8，由于這一整數序列是如下樹的后序遍歷結果：
8 / / 6 10 / / / / 5 7 9 11
因此返回true。如果輸入7、4、6、5，沒有哪棵樹的后序遍歷的結果是這個序列，因此返回false。
思路：分析后序遍歷的特點，序列的最后一個數應該是根結點，剩余的節點分為兩個連續的子序列，前一子序列的值小于最后一個數，后一子序列的值大于最后一個數。然后遞歸求解這兩個子序列。
如果是判斷是前序遍歷也很簡單，只不過根節點變為了第一個數，剩余的節點也是分為兩個連續的子序列。如果判斷是中序遍歷，更方便，只需掃描一遍，檢查序列是不是排好序的，如果沒有排好序，就不是中序遍歷的結果。
把二元查找樹轉變成排序的雙向鏈表
問題描述：輸入一棵二元查找樹，將該二元查找樹轉換成一個排序的雙向鏈表。要求不能創建任何新的結點，只調整指針的指向。
10 / / 6 14 / / / /4 8 12 16
轉換成雙向鏈表
4=6=8=10=12=14=16
思路：利用遞歸的思想求解，分別調整某結點的左右子樹，調整完后，將該結點的左指針指向左子樹的最大節點，右指針指向右子樹的最小節點。
代碼如下：
BSTreeNode * Convert(BSTreeNode *node) { if(node == NULL) return NULL; BSTreeNode *leftMax,*rightMin; leftMax = node->left; rightMin = node->right; //找到左子樹的最大結點 while(leftMax != NULL && leftMax->right != NULL) leftMax = leftMax->right; //找到右子樹的最小結點 while(rightMin != NULL && rightMin->left != NULL) rightMin = rightMin->left; //遞歸求解 Convert(node->right); Convert(node->left); //將左右子樹同根結點連起來，只不過是以兄弟的關系 if(leftMax != NULL) leftMax->right = node; if(rightMin != NULL) rightMin->left = node; node->left = leftMax; node->right = rightMin; return node; } 測試當中，需要建立二叉搜索樹，下面給出建立及遍歷二叉樹的代碼。
struct BSTreeNode { int value; BSTreeNode *left; BSTreeNode *right; }; BSTreeNode * Insert(BSTreeNode *p, int x) { if(p == NULL) { p = new BSTreeNode; p->value = x; p->left = NULL; p->right = NULL; } else { if(p->value > x) p->left = Insert(p->left, x); if(p->value < x) p->right = Insert(p->right, x); } return p; } void Traverse(BSTreeNode *p) //中序遍歷 { if(p == NULL) return; Traverse(p->left); cout<<p->value<<' '; Traverse(p->right); } 在二元樹中找出和為某一值的所有路徑（樹）
問題描述：輸入一個整數和一棵二元樹。從樹的根結點開始往下訪問一直到葉結點所經過的所有結點形成一條路徑。打印出和與輸入整數相等的所有路徑。
例如輸入整數22和如下二元樹
10 / / 5 12 / / 4 7
則打印出兩條路徑：10, 12和10, 5, 7。
二元樹節點的數據結構定義為：
struct BinaryTreeNode{int data;BinaryTreeNode *pLeft;BinaryTreeNode *pRight;}; 思路：遞歸的思想。很多樹的題目都是用遞歸解決的，例如把二元查找樹轉變成排序的雙向鏈表（樹）。遞歸的終止條件為當前為空結點或當前結點的值大于剩余和。如果當前結點的值等于剩余和，并且是葉結點，那么打印路徑。否則，將剩余和減去當前結點的值，遞歸求解。至于路徑的記錄，可以利用棧的思想來實現。
代碼：
void FindPath(BinaryTreeNode *pNode,int sum,vector<int> &path) { //結點為空或值大于當前和 if(pNode == NULL || pNode->data > sum) return; path.push_back(pNode->data); //判斷是不是葉結點 bool isLeaf = (pNode->pLeft == NULL && pNode->pRight == NULL)? true: false; //找到一條路徑，打印 if(pNode->data == sum && isLeaf) { vector<int>::iterator iter = path.begin(); for(; iter != path.end(); iter++) cout<<*iter<<' '; cout<<endl; } else { //求剩余和 sum = sum - pNode->data; //遞歸求解 FindPath(pNode->pLeft, sum, path); FindPath(pNode->pRight, sum, path); } path.pop_back(); } 判斷二叉樹是不是平衡的
問題描述：輸入一棵二叉樹的根結點，判斷該樹是不是平衡二叉樹。如果某二叉樹中任意結點的左右子樹的深度相差不超過1，那么它就是一棵平衡二叉樹。例如下圖中的二叉樹就是一棵平衡二叉樹：
思路：對于樹的題目，第一反應就是用遞歸。對于以某個結點為根的樹，只需計算出它的左右子樹的深度，如果深度相差小于等于1，則遞歸判斷它的左右子樹是不是平衡樹；否則肯定不是平衡二叉樹。這個問題的關鍵是要計算樹的深度，如果是自頂向下，會有很多重復的計算。計算以1為根的樹的深度，會牽涉到以2為根、以3為根的子樹。計算以2為根的樹的深度，會牽涉到以4為根、以5為根的子樹。由于要遍歷每個結點，判斷以該結點為根的樹是不是平衡二叉樹。所以計算以1為根的樹的深度，與計算以2為根的樹的深度，會重復計算以4為根、以5為根的子樹的深度。
消除重復辦法，當時是能記錄下之前計算過的子樹的深度，下次使用就不用重新計算。這就需要自底向上的計算深度。慶幸的是遞歸解決樹的問題，就是自底向上的過程。因為我們在遞歸求解中，先要得出子樹的解，子樹的解最終會轉換為葉結點的解。可以利用后序遍歷的方法，遍歷每個結點時，先判斷它的左右子樹是不是平衡二叉樹，同時記錄下左右子樹的深度，然后判斷該結點為根的樹是不是平衡二叉樹，至于該樹的深度計算很方便，取左右子樹中較大的深度+1就可以了。這里左右子樹的深度在遞歸求解中已經計算出來，不需要重復計算了。
參考代碼：
struct BinaryTreeNode { int data; BinaryTreeNode *pLeft; BinaryTreeNode *pRight; }; //函數功能 ： 判斷二叉樹是不是平衡的 //函數參數 ： pRoot為根結點，pDepth為根結點的深度。 //返回值 ： 是否平衡的 bool IsBalanced(BinaryTreeNode *pRoot, int *pDepth) { if(pRoot == NULL) { *pDepth = 0; return true; } int leftDepth, rightDepth; //左右子樹的深度 if(IsBalanced(pRoot->pLeft, &leftDepth)&& IsBalanced(pRoot->pRight, &rightDepth)) { int diff = leftDepth - rightDepth; if(diff == 0 || diff == 1 || diff == -1) //相差為0或1或-1 { *pDepth = 1 + (leftDepth > rightDepth ? leftDepth: rightDepth); return true; } else return false; } return false; } 新聞熱點
疑難解答
圖片精選
