<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                合規國際互聯網加速 OSASE為企業客戶提供高速穩定SD-WAN國際加速解決方案。 廣告
                # 一、概念 ### 1.定義與性質 (1)設x為二叉查找樹中的一個結點,若y是x左子樹中的一個結點,則key[y] <= key[x];若y是x右子樹中的一個結點,則key[x]<=key[y] (2)二叉查找樹上執行的基本操作的時間與樹的高度成正比。 ### 2.結構 (1)結點結構: 關鍵字key 衛星數據data 分別指向父、左右孩子的指針p, left, right ### 3.在二叉查找樹上的操作 查找一個關鍵字:SEARCH(x, k) 求最小關鍵字:MINIMUM(x) 求最大關鍵字:MAXIMUM(x) 求前驅:PREDECESSOR(x) 求后繼:SUCCESSOR(x) 插入一個結點:INSERT(T, z) 刪除一個結點:DELETE(z) ### 4.二叉查找樹的應用 1.遍歷:中序遍歷、先序遍歷、后序遍歷 2.查找:查找包含某個關鍵字的結點,查找關鍵字最大或最小的結點、查找某個結點的前驅或后繼 # 二、代碼 [頭文件](https://code.csdn.net/mishifangxiangdefeng/algoritmcollection/tree/master/include/binarySearchTree.h) [產品代碼](https://code.csdn.net/mishifangxiangdefeng/algoritmcollection/tree/master/src/binarySearchTree.cpp) 測試代碼 # 三、練習 ### 12.1 二叉查找樹 12.1-2 二叉查找樹:左子樹關鍵字<根結點關鍵字<右子樹關鍵字 堆:左子樹關鍵字<根結點關鍵字 && 右子樹關鍵字<根結點關鍵字 不能,因為一個結點的的左子樹與右子樹的關鍵字大小沒有關系 12.1-3 用棧實現:見[算法導論-10.4-有根樹的表示](http://blog.csdn.net/mishifangxiangdefeng/article/details/7707756)中的10.4-3 不用棧實現:見[算法導論-10.4-5](http://blog.csdn.net/mishifangxiangdefeng/article/details/7708490) 12.1-4 ~~~ //遞歸的先序遍歷 void BST_Tree::Preorder_Tree_Walk(BST_Node *x) { //x不是葉子結點 if(x != NULL) { //訪問當前結點 cout<<x->key<<' '; //先序遍歷當前結點的左子樹 Preorder_Tree_Walk(x->left); //先序遍歷當前結點的右子樹 Preorder_Tree_Walk(x->right); } } //遞歸的后序遍歷 void BST_Tree::Postorder_Tree_Walk(BST_Node *x) { //x不是葉子結點 if(x != NULL) { //后序遍歷當前結點的左子樹 Postorder_Tree_Walk(x->left); //后序遍歷當前結點的右子樹 Postorder_Tree_Walk(x->right); //訪問當前結點 cout<<x->data<<' '; } } ~~~ ### 12.2 查詢二叉查找樹 ~~~ 12.2-1 c,e 12.2-2 //遞歸地查找最小值 BST_Node *BST_Tree::Tree_Minimum(BST_Node *x) { if(x->left != NULL) return Tree_Minimum(x->left); else return x; } //遞歸的查找最大值 BST_Node *BST_Tree::Tree_Maximum(BST_Node *x) { if(x->right != NULL) return Tree_Maximum(x->right); else return x; } 12.2-3 //查找中序遍歷下x的前驅,即小于x的最大值 BST_Node *BST_Tree::Tree_Predecessor(BST_Node *x) { //如果x的左子樹非空 if(x->left != NULL) //x的前驅是x的左子樹的最大值 return Tree_Maximum(x->left); //如果x的左子樹為空且x有前驅y,那么y是x的最低祖先結點,且y的右兒子也是 BST_Node *y = x->p; while(y != NULL && x == y->left) { x = y; y = y->p; } return y; } 12.2-4 (1) 4->left = 2 4->right =NIL 2->left = 1 2->right = 3 搜索路徑4-2-1 (2) 1->right = 3 1->left = NUL 3->left = 2 3->right = 4 搜索路徑1-3-4 ~~~ ### 12.3 插入和刪除 12.3-1 ~~~ //遞歸的二叉查找樹的插入操作,分三種情況 void BST_Tree::Tree_Insert(BST_Node *x, BST_Node *z) { //已經存在 if(z->key == x->key) { cout<<"error:exist"<<endl; return; } //插入到x的左子樹中 else if(z->key < x->key) { //x沒有左子樹 if(x->left == NULL) { //修改指針,插入操作 x->left = z; z->p = x; return; } //x有左子樹 else //對x的左子樹執行插入操作 Tree_Insert(x->left, z); } //插入到x的右子樹中,與上面類似 else if(z->key > x->key) { if(x->right == NULL) { x->right = z; z->p = x; } else Tree_Insert(x->right, z); } } ~~~ 12.3-3 最壞是n^2 最好是nlgn 12.3-4 求y的前驅z分為兩種情況,以下分別討論: (1)y有左孩子,則z是left[y]中最右邊的結點,z沒有右孩子,因此刪除z時直接刪除修改指針即可,沒有問題 (2)y沒有左孩子,則z是y的祖先,y是z右子樹是最左邊的點,又分為兩種情況: (2.1)若z沒有左孩子,則直接刪除z并修改指針,沒有問題。 (2.2)若z有左孩子,則不直接刪除z,而是用z代替y存在并刪除y。這里會有問題,另一個數據結構中的保存了指向y的指針,但是y的內容轉移到另一個結點上了,指向y的指針指向了一個被釋放的空間。 解決方法:使TREE-DELETE返回刪除后的y的指針,這個值可能會變,可能不變。讓另一個數據結構的y指針指向TREE-DELETE的返回值。 12.3-5 不或交換,反例如圖 ![](https://box.kancloud.cn/2016-02-02_56b02bd0c61a4.gif) ![](https://box.kancloud.cn/2016-02-02_56b02bd0d2fef.gif) 12.3-6 當待刪除結點有兩個子樹時,不刪除待刪除結點,而是刪除它的前驅或后繼,用隨機數rand()%2來確定刪除的前驅還是后繼 代碼見文:二 # 四、思考題 ### 12-1 具有相同關鍵字元素的二叉樹 見[算法導論-12-1-具有相同關鍵字元素的二叉查找樹](http://blog.csdn.net/mishifangxiangdefeng/article/details/7719138) ### 12-2 基數樹 見[算法導論-12-2-基數樹](http://blog.csdn.net/mishifangxiangdefeng/article/details/7719324) 12-3 隨機構造的二叉查找樹中的平均結點深度 f)待解決
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看