二叉查找树之二
?BST樹的經典問題
?
首先構造如下一棵二元查找樹（BST樹）：
C++代碼實現：
typedef struct _BSTreeNode {int value;struct _BSTreeNode *left;struct _BSTreeNode *right;} BSTreeNode;static BSTreeNode* insert(BSTreeNode* q, int x) {BSTreeNode* p = (BSTreeNode*) new(BSTreeNode);p->value = x;p->left = NULL;p->right = NULL;if (q == NULL) {q = p;} else if (x < q->value) {q->left = insert(q->left, x);} else {q->right = insert(q->right, x);}return q; }static BSTreeNode* search(BSTreeNode* p, int x) {int find = 0;while (p && !find) {if (x == p->value) {find = 1;} else if (x < p->value) {p = p->left;} else {p = p->right;}}if (p == NULL) {cout<< "not found" <<endl;}return p; }int main() {int n, key;vector<int> path;BSTreeNode *BT = NULL;int array[11] = {15, 6, 18, 3, 7, 17, 20, 2, 4, 13, 9};for (n=0; n<11; n++) {key = array[n];BT = insert(BT, key);}n = 0;return 0; }?
對二叉樹的遍歷除了常見的先序遍歷/中序遍歷/后序遍歷意外，還有廣度優先，深度優先遍歷。
?
廣度優先遍歷（BFS）
沿著樹的寬度遍歷樹的結點，自上而下，從左往右的遍歷一棵二叉樹。
思路：考慮用隊列的數據結構來實現，將根結點放入隊列之后。
每次從隊列頭取出一個結點的同時，將其左孩子、右孩子分別放入隊列尾。
?
?
深度優先遍歷（DFS）
沿著樹的深度遍歷樹的結點，盡可能的搜索樹的分支。
思路：考慮用stack的數據結構來實現，將根結點放入stack之后。
每次從棧頂取出一個結點的同時，將其右孩子、左孩子分別壓入stack。
?
void DepthFirstSearch(BSTreeNode* root, vector<int> &result) {if (!root) return;BSTreeNode *q;stack<BSTreeNode *> nodeStack;nodeStack.push(root);while (!nodeStack.empty()) {q = nodeStack.top();nodeStack.pop();result.push_back(q->value);if(q->right)nodeStack.push(q->right);if(q->left)nodeStack.push(q->left);} }?
BST樹的鏡像
輸入一顆BST樹，將該樹轉換為它的鏡像，即在轉換后的二元查找樹中，左子樹的結點都大于右子樹的結點。
例如輸入：
? ?8
? / \
6 ? 10
/\ ? ? /\
5 7 9 11
輸出：
? ? ? 8
? ? / ? ?\
? 10 ? ?6
? /\ ? ?/\
11 9 7 5
?
遞歸解法：
void MirrorRecursively(BSTreeNode *pNode) {if (!pNode) return;// swap the right and left child sub-treeBSTreeNode *pTemp = pNode->left;pNode->left = pNode->right;pNode->right = pTemp;// mirror left child sub-tree if not nullif (pNode->left)MirrorRecursively(pNode->left); // mirror right child sub-tree if not nullif (pNode->right)MirrorRecursively(pNode->right); }?
由于遞歸的本質是編譯器生成了一個函數調用的棧，因此用循環來完成同樣任務時最簡單的辦法就是用一個輔助棧來模擬遞歸。首先我們把樹的頭結點放入棧中。在循環中，只要棧不為空，彈出棧的棧頂結點，交換它的左右子樹。如果它有左子樹，把它的左子樹壓入棧中；如果它有右子樹，把它的右子樹壓入棧中。這樣在下次循環中就能交換它兒子結點的左右子樹了。
void MirrorIteratively(BSTreeNode *pTreeHead) {if (!pTreeHead) return;stack<BSTreeNode *> stackTreeNode;stackTreeNode.push(pTreeHead);while (stackTreeNode.size()) {BSTreeNode *pNode = stackTreeNode.top();stackTreeNode.pop();// swap the right and left child sub-treeBSTreeNode *pTemp = pNode->left;pNode->left = pNode->right;pNode->right = pTemp;// push left child sub-tree into stack if not nullif(pNode->left)stackTreeNode.push(pNode->left);// push right child sub-tree into stack if not nullif(pNode->right)stackTreeNode.push(pNode->right);} }?
?
將BST樹轉為一個有序的雙向鏈表
將上面的BST樹轉換為雙向鏈表：如2==3==4==6==7==9==13==15==17==18==20。
我們知道，BST樹的中序遍歷是有序的，所以只要按這種方式將當前訪問的節點加到鏈表末尾就可以了。
?
void ConvertNode(BSTreeNode *pNode, BSTreeNode** pLastNodeOfList) {if (NULL == pNode)return;if (pNode->left) {ConvertNode(pNode->left, pLastNodeOfList);}pNode->left = *pLastNodeOfList;if (*pLastNodeOfList) {(*pLastNodeOfList)->right = pNode;}*pLastNodeOfList = pNode;if (pNode->right) {ConvertNode(pNode->right, pLastNodeOfList);} }BSTreeNode* Convert_Solution(BSTreeNode* pHeadOfTree) {BSTreeNode *pLastNodeInList = NULL;ConvertNode(pHeadOfTree, &pLastNodeInList);// 找到雙向鏈表的頭指針BSTreeNode *pHeaderOfList = pLastNodeInList;while (pHeaderOfList && pHeaderOfList->left)pHeaderOfList = pHeaderOfList->left;return pHeaderOfList; }?
?
?
在二叉樹中找到和為特定值的所有路徑
實現一個FindPath函數，能找到所有節點的和等于50的路徑：
void FindPath(BSTreeNode* root, int sum, vector<int>&path, int ¤t) {if (!root) return;current += root->value;path.push_back(root->value);// find one pathif (NULL == root->left && NULL == root->right && current == sum) {vector<int>::iterator it = path.begin();for (; it!=path.end(); ++it) {cout<<*it<<"\t";}cout<<endl;}if (root->left)FindPath(root->left, sum, path, current);if (root->right)FindPath(root->right, sum, path, current);current -= root->value;path.pop_back(); }運行結果為：
[root@localhost cq]# ./a.out 15 6 7 13 9 15 18 17?
實現思路：
當訪問到某一節點時，將該節點添加到路徑上，并累加當前節點的值：
1、如果當前節點為葉節點并且當前路徑的和剛和等于輸入的值，則當前路徑就符合要求；
2、如果當前節點不是葉節點，則繼續訪問它的子節點；
3、當前節點訪問結束后，遞歸函數將自動回到父節點。因此在函數退出之前要在路徑上刪除當前節點并減去當前節點的值，以確保返回父節點時路徑剛好是根節點到父節點的路徑。保存路徑的數據結構實際上是一個棧結構，因為路徑要與遞歸調用狀態一致，而遞歸調用本質就是一個壓棧和出棧的過程。
?
?
?
判斷一個數組是不是一棵BST樹的后序遍歷
二叉樹的后序遍歷分為3部分： LETF、RIGHT、ROOT，并且，LEFT部分的值都不大于ROOT，RIGHT部分的值都大于ROOT。
因此，對一個數組，從第一個元素開始遍歷，把小于最后一個元素（即ROOT）的部分作為LEFT，大于最后一個元素的部分作為RIGHT。
然后再對LEFT和RIGHT遞歸判斷子樹是否也符合條件。
?
C++代碼實現如下：
int verifySequenceOfBST(int *seq, int N) {if (seq == NULL || N <= 0)return 0;int n, m;int root = seq[N-1]; // 根結點for (n=0; n<N-1 && seq[n] <= root; n++); // 左子樹for (m=n; m<N-1 && seq[m] > root; m++); // 右子樹if (m != N-1) return 0;int left = 1, right = 1;if (n > 0)left = verifySequenceOfBST(seq,n);if (n < N-1)right = verifySequenceOfBST(seq+n,N-1-n);return (left && right); }?
?
?
二叉樹兩結點的最低共同父結點
如果兩個節點A、B有共同的父節點C，那么有4種情況：
1、A和B都在C的左子樹中；
2、A和B都在C的右子樹中；
3、A在C的左子樹，B在C的右子樹；
4、B在C的左子樹，A在C的右子樹；
我們從根節點開始，先判斷屬于上面哪種情況，如果是情況1，只要A、B的共同父節點肯定在左子樹中，繼續遞歸；情況2類似處理；
如果是情況3、4，那么A和B的最低共同父節點就是根節點。
?
C++代碼實現如下：
int HasNode(BSTreeNode *pHead, BSTreeNode *pNode) {if (pHead == pNode)return 1;int has = 0;if (pHead->left)has = HasNode(pHead->left, pNode);if (!has && pHead->right)has = HasNode(pHead->right, pNode);return has; }BSTreeNode *LastCommonParent(BSTreeNode *pHead, BSTreeNode *pNode1, BSTreeNode *pNode2) {if (NULL == pHead || NULL == pNode1 || NULL == pNode2)return NULL;int leftHasNode1 = 0;int leftHasNode2 = 0;if (pHead->left) {leftHasNode1 = HasNode(pHead->left, pNode1);leftHasNode2 = HasNode(pHead->left, pNode2);} if (leftHasNode1 && leftHasNode2) { // 兩個結點都在左子樹中if (pHead->left == pNode1 || pHead->left == pNode2)return pHead;return LastCommonParent(pHead->left, pNode1, pNode2);} int rightHasNode1 = 0;int rightHasNode2 = 0;if (pHead->right) {if (!leftHasNode1)rightHasNode1 = HasNode(pHead->right, pNode1);if (!leftHasNode2)rightHasNode2 = HasNode(pHead->right, pNode2);} if (rightHasNode1 && rightHasNode2) { // 兩個結點都在右子樹中if (pHead->right == pNode1 || pHead->right == pNode2)return pHead;return LastCommonParent(pHead->right, pNode1, pNode2);} if ((leftHasNode1 && rightHasNode2) // 兩個結點一個在左子樹中，另一個在右子樹中|| (leftHasNode2 && rightHasNode1))return pHead;return NULL; }?
?
?
樹為另一樹的子結構
思路：要在樹A中查找是否存在和樹B結構一樣的子樹，可以分為兩步：
1、在樹A中找到和B的根節點一樣的節點N；
2、判斷樹A中以N為根節點的子樹是不是包括和樹B一樣的結構。
?
遞歸的實現方式如下：
int TreeEqual(BSTreeNode* Head1, BSTreeNode* Head2) {if (NULL == Head2) return 1;if (NULL == Head1) return 0;if (Head1->value != Head2->value) return 0;return TreeEqual(Head1->left, Head2->left) && TreeEqual(Head1->right, Head2->right);}int HasSubTreeCore(BSTreeNode* Head1, BSTreeNode* Head2) {int result = 0;if (Head1->value == Head2->value) {result = TreeEqual(Head1, Head2);} if (result == 0 && Head1->left) {result = TreeEqual(Head1->left, Head2);} if (result == 0 && Head1->right) {result = TreeEqual(Head1->right, Head2);} return result; }int HasSubTree(BSTreeNode* Head1, BSTreeNode* Head2) {if ((Head1 == NULL && Head2 != NULL)|| (Head1 != NULL && Head2 == NULL))return 0;if (Head1 == NULL && Head2 == NULL)return 1;return HasSubTreeCore(Head1, Head2); }?
轉載于:https://www.cnblogs.com/chenny7/p/4120961.html
總結
- 上一篇： 【bzoj4566】[Haoi2016]
- 下一篇： Software-testing-fou