三層二叉樹算法？二叉樹的每個節(jié)點(diǎn)最多有兩個子樹(沒有度數(shù)大于2的節(jié)點(diǎn))，二叉樹的子樹分左右，順序不能顛倒。二叉樹的I層最多有1個2^(i節(jié)點(diǎn)；深度為k的二叉樹最多有1個2^k節(jié)點(diǎn)；對于任意二叉樹T，如

三層二叉樹算法？

二叉樹的每個節(jié)點(diǎn)最多有兩個子樹(沒有度數(shù)大于2的節(jié)點(diǎn))，二叉樹的子樹分左右，順序不能顛倒。二叉樹的I層最多有1個2^(i節(jié)點(diǎn)；深度為k的二叉樹最多有1個2^k節(jié)點(diǎn)；對于任意二叉樹T，如果終端節(jié)點(diǎn)數(shù)為n0，度為2的節(jié)點(diǎn)數(shù)為n2，則n0 ^ N2 ^ 1。二叉樹算法常用來實(shí)現(xiàn)二叉查找樹和二叉堆。

如何在Java中實(shí)現(xiàn)二叉搜索樹？

二分搜索法樹木必須符合以下四個條件:

如果任一節(jié)點(diǎn)的左子樹不為空，則左子樹上所有節(jié)點(diǎn)的值都小于其根節(jié)點(diǎn)的值；如果任一節(jié)點(diǎn)的右子樹不為空，則右子樹上所有節(jié)點(diǎn)的值都大于其根節(jié)點(diǎn)的值；任一節(jié)點(diǎn)的左右子樹也分別是二分搜索法樹；沒有鍵值相等的節(jié)點(diǎn)。二叉查找樹的例子:

圖1

接下來，將基于圖1來介紹二叉查找樹的相關(guān)操作。

首先，應(yīng)該有一個與節(jié)點(diǎn)對象相關(guān)的類，名為Node。

1類Node { 2 int key 3 int value 4 Node left child 5 Node right child 6 7 public Node(int key，int value){ 8 key 9 value 10 } 1112 publicvoid display Node(){ 1314 } 15 } Node類包含鍵值，用于確定節(jié)點(diǎn)在樹中的對應(yīng)位置。value value表示要存儲的內(nèi)容，它還包含對左右兩個子節(jié)點(diǎn)的兩個引用。

接下來，在搜索樹中查看相應(yīng)的類:

1類樹{2節(jié)點(diǎn)根//保存樹的根3 4公共節(jié)點(diǎn)find(int key) {//查找指定節(jié)點(diǎn)5 6} 7 8公共void insert(int key，Int value) {//插入節(jié)點(diǎn)9 10} 11 12公共Boolean Delete(Int key){//刪除指定節(jié)點(diǎn)13 14} 15 16私有節(jié)點(diǎn)getdirectpostnode(Node delnode){//獲取要刪除的節(jié)點(diǎn)的直接后繼:17 18} 19 20公共void preorder(節(jié)點(diǎn)根節(jié)點(diǎn)){//遍歷樹RootNode) {//中遍歷樹25 26 } 27 28 public void post order(node根節(jié)點(diǎn)){//post遍歷樹29 30 }31}類表示樹的框架，包括相應(yīng)的查找、插入、遍歷、刪除的方法，其中刪除節(jié)點(diǎn)是最復(fù)雜的操作，將一一介紹。

首先，找到一個節(jié)點(diǎn)

由于二叉查找樹定義的特殊性，我們只需要根據(jù)輸入的鍵值從根進(jìn)行比較。如果小于根的鍵值，則與根的左子樹進(jìn)行比較，如果大于根，則與根的右子樹進(jìn)行比較，以此類推。如果找到，則返回相應(yīng)的節(jié)點(diǎn)，否則返回null。

1公共節(jié)點(diǎn)find(int key) { 2節(jié)點(diǎn)current Node root 3 while(current Node！空ampamp！key){ 4 if(key lt){ 5 currentnodecurrentnode . left child 6 } else { 7 currentnodecurrentnode . right child 8 } 9 } 10 Return currentnode 11 }其次，插入節(jié)點(diǎn)。

與查找操作類似，由于二叉查找樹的特殊性，需要從根節(jié)點(diǎn)開始比較要插入的節(jié)點(diǎn)。如果小于根節(jié)點(diǎn)，則與根節(jié)點(diǎn)的左子樹進(jìn)行比較，反之亦然，直到左子樹為空或者右子樹為空，再插入到相應(yīng)的空位置。在比較過程中，要注意保存父節(jié)點(diǎn)的信息，以及要插入的位置是父節(jié)點(diǎn)的左子樹還是右子樹，然后再插入到正確的位置。

1 public void insert(int key，int value){ 2 if(root null){ 3 root new Node(key，value)4 return 5 } 6 Node current Node root 7 Node parent Node root 8 boolean is left child true 9 while(current Node！null){ 10 parent node current node 11 if(key lt){ 12 current node current node . left child 13 is left child true 14 } else { 15 current node current node . right child 16 is left child false 17 } 18 } 19 Node new Node new Node(key，value)20 if(is left child){ 21 parent Node . left child new Node 22 } else { 23 parent Node . right child new Node 24 } 25 }

第三，穿越二叉查找樹

遍歷操作和普通二叉樹的遍歷完全一樣，所以我贏了 不要重復(fù)。

1 public void preOrder(Node root Node){ 2 if(root Node！null){ 3()4 preOrder(root Node . left child)5 preOrder(root Node . right child)6 } 7 } 8 9 public void in order(Node root Node){ 10 if(root Node！null){ 11 in order(root Node . left child)12()13 in order(root Node . right child)14 } 15 } 16 17 public void post order(Node root Node){ 18 if(root Node！null){ 19 post order(root node . left child)20 post order(root node . right child)21()22 } 23 }

第四，刪除指定的節(jié)點(diǎn)。

在二叉查找樹中刪除節(jié)點(diǎn)很復(fù)雜，可以分為以下三種情況。

1.要刪除的節(jié)點(diǎn)是葉節(jié)點(diǎn)，可以直接刪除。

public Boolean Delete(int key){ Node當(dāng)前節(jié)點(diǎn)根//用于保存要刪除的節(jié)點(diǎn)Node parentNode根//用于保存父節(jié)點(diǎn)Boolean islefchild true//用于確定要刪除的節(jié)點(diǎn)是左子節(jié)點(diǎn)還是右子節(jié)點(diǎn)while (currentNode！空ampamp！key){ parent node current node if(key lt){ current node current node . left child is left child true } eLSE { current node current node . right child is left child false } } If(current node null){ return false } If(當(dāng)前節(jié)點(diǎn)。leftchild空amp amp當(dāng)前節(jié)點(diǎn)。right child null){//要刪除的節(jié)點(diǎn)是葉節(jié)點(diǎn)if(當(dāng)前節(jié)點(diǎn)根)root null else if(是leftchild)。parent node . left child null else parent node . right child null }......}

2.要刪除的節(jié)點(diǎn)只有一個子節(jié)點(diǎn)。

例如，要刪除圖1中鍵值為11的節(jié)點(diǎn)，只需要將鍵值為13的節(jié)點(diǎn)的左子節(jié)點(diǎn)指向鍵值為12的節(jié)點(diǎn)，就可以刪除鍵值為11的節(jié)點(diǎn)。

從上面的分析中得到的代碼如下(省略了上面提到的delete方法之后):

1 else if(當(dāng)前節(jié)點(diǎn)。right child null){//唯一要刪除的節(jié)點(diǎn)是左子2 if(當(dāng)前節(jié)點(diǎn)根)3根當(dāng)前節(jié)點(diǎn)。Leftchild4 else if(是Leftchild)。5 parent node . left child current node . left child 6 else 7 parent node . right child current node . left child 8 } else if(current node . left child null){//僅右子9 if(當(dāng)前節(jié)點(diǎn)根)10根當(dāng)前節(jié)點(diǎn)。Rightchild 11 else if(是leftchild) 12父節(jié)點(diǎn)。Leftchchild當(dāng)前節(jié)點(diǎn)。Rightchild 13 else 14父節(jié)點(diǎn)。Rightchild當(dāng)前節(jié)點(diǎn)。Rightchild 15}將被刪除。......

3.要刪除的節(jié)點(diǎn)有左右兩個子節(jié)點(diǎn)。

例如，如果您刪除圖1中鍵值為10的節(jié)點(diǎn)，您需要使用鍵值為10的節(jié)點(diǎn)。序數(shù)后繼節(jié)點(diǎn)(節(jié)點(diǎn)11)替換鍵值為10的節(jié)點(diǎn)，并刪除鍵值為10的節(jié)點(diǎn)的序數(shù)后繼節(jié)點(diǎn)。根據(jù)序數(shù)遍歷的相關(guān)規(guī)則，鍵值為10的節(jié)點(diǎn)的直接序數(shù)后繼節(jié)點(diǎn)必然是其右子樹中鍵值最小的節(jié)點(diǎn)，所以這個序數(shù)后繼節(jié)點(diǎn)必然不包含子節(jié)點(diǎn)或者只包含一個右子節(jié)點(diǎn)，刪除這個序數(shù)后繼節(jié)點(diǎn)屬于上面1和2中提到的情況。在圖1中，鍵值為10的節(jié)點(diǎn)的直接中間順序后繼節(jié)點(diǎn)是11，節(jié)點(diǎn)11包含一個右子節(jié)點(diǎn)12。

因此，刪除圖1中鍵值為10的節(jié)點(diǎn)分為以下幾個步驟:

A.找到鍵值為10的節(jié)點(diǎn)的直接中間后繼節(jié)點(diǎn)(即其右子樹中值最小的節(jié)點(diǎn)11)，刪除這個直接中間后繼節(jié)點(diǎn)。

1 private nodegetdirectpostnode(nodedelnode){//方法用于獲取要刪除的節(jié)點(diǎn)的直接后繼節(jié)點(diǎn)。2 3節(jié)點(diǎn)parentNode delNode//用于保存待刪除節(jié)點(diǎn)的直接后繼節(jié)點(diǎn)的父節(jié)點(diǎn)，4節(jié)點(diǎn)direcrPostNode delNode///用于保存待刪除節(jié)點(diǎn)的直接后繼節(jié)點(diǎn)，5節(jié)點(diǎn)當(dāng)前節(jié)點(diǎn)del Node。右子6 While(當(dāng)前節(jié)點(diǎn)！null){ 7 parent node direcrPostNode 8 direcrPostNode current node 9 current node current node . left child 10 } 11 if(direcrPostNode！DelNode.rightChild) {//從樹中刪除此直接后繼節(jié)點(diǎn):12parentnode。LeftchildDirecPostnode。RightChild13dDirecPostnode。right child null 14 } 15 Return DirecPostnode//返回直接后繼節(jié)點(diǎn)16 17} b并將該后繼節(jié)點(diǎn)的鍵值賦給要刪除的節(jié)點(diǎn)的鍵值。(在情況2中的省略號代碼之后)

1 else {//要刪除的節(jié)點(diǎn)既有左右子節(jié)點(diǎn)。2 3 //思路:將待刪除節(jié)點(diǎn)的值替換為待刪除節(jié)點(diǎn)右子樹中鍵值最小的節(jié)點(diǎn)的值，然后刪除右子樹中鍵值最小的節(jié)點(diǎn)。4 //右邊子樹中鍵最小的節(jié)點(diǎn)不能包含左邊的子樹，所以刪除具有最小鍵的節(jié)點(diǎn)必須屬于葉節(jié)點(diǎn)或只有右子樹的節(jié)點(diǎn)，5節(jié)點(diǎn)DirectPostNode GetDirectPostNode(當(dāng)前節(jié)點(diǎn))6 9}

至此，刪除指定節(jié)點(diǎn)的操作結(jié)束。

最后給出了完整代碼、簡單測試代碼和測試結(jié)果:

1類節(jié)點(diǎn){ 2 int key 3 int value 4 Node left child 5 Node right child 6 7 public Node(int key，int value){ 8 key 9 value 10 } 11 12 public void display Node(){ 13 14 } 15 } 16 17類樹{ 18 Node root 19 20 public Node find(int key){ 21 Node current Node root 22 while(current Node！空ampamp！key){ 23 if(key lt){ 24 current Node current Node . left child 25 } else { 26 current Node current Node . right child 27 } 28 } 29 return current Node 30 } 31 32 public void insert(int key，int value){ 33 if(root null){ 34 root new Node(key，value)35 return 36 } 37 Node current Node root 38 Node parent Node root 39 boolean is left child true 40 while(current Node！null){ 41 parent Node current Node 42 if(key lt){ 43 current Node current Node . left child 44 is left child true 45 } else { 46 current Node current Node . right child 47 is left child false 48 } 49 } 50 Node newNode新節(jié)點(diǎn)(key，value)51 if(is left child){ 52 parent Node . left child new Node 53 } else { 54 parent Node . right child new Node 55 } 56 } 57 58 public boolean delete(int key){ 59 Node current Node root 60 Node parent Node root 61 boolean is left child true 62 while(current Node！空ampamp！key){ 63 parent node current node 64 if(key lt){ 65 current node current node . left child 66 is left child true 67 } else { 68 current node current node . right child 69 is left child false 70 } 71 } 72 if(current node null){ 73 return false 74 } 75 if(當(dāng)前節(jié)點(diǎn)。leftchild空amp amp當(dāng)前節(jié)點(diǎn)。right child null){ 76//要刪除的節(jié)點(diǎn)是葉節(jié)點(diǎn)77 if (currentNode root)。78根null 79 else if(islefchild)80 parent node . left child null 81 else 82 parent node . right child null 83 } else if(current node . right child null){//唯一要刪除的節(jié)點(diǎn)是左孩子84 if(當(dāng)前節(jié)點(diǎn)根)85根當(dāng)前節(jié)點(diǎn)。Leftchild86 else if(是Leftchild)。87 parent node . left child current node . left child 88 else 89 parent node . right child current node . left child 90 } else if(cUrrentNode.leftChild null) {//唯一要刪除的節(jié)點(diǎn)是右子91 if(當(dāng)前節(jié)點(diǎn)根)92根當(dāng)前節(jié)點(diǎn)。Rightchild 93 else if(是leftchild)。94 parentnode。leftchild當(dāng)前節(jié)點(diǎn)。rightchild 95 else 96 parentnode。rightchild當(dāng)前節(jié)點(diǎn)。right child 97 } else {//要刪除的節(jié)點(diǎn)有左右兩個子節(jié)點(diǎn)98 //思路:用要刪除的節(jié)點(diǎn)的右子樹中鍵值最小的節(jié)點(diǎn)的值替換要刪除的節(jié)點(diǎn)的值，然后刪除右子樹中鍵值最小的節(jié)點(diǎn)。//右邊子樹中鍵最小的節(jié)點(diǎn)不能包含左邊子樹。所以鍵最小的節(jié)點(diǎn)一定屬于葉節(jié)點(diǎn)或者只有右子樹的節(jié)點(diǎn)100節(jié)點(diǎn)DirectPostNode GetDirectPostNode(當(dāng)前節(jié)點(diǎn))101} 104返回True 105 } 106 107私有節(jié)點(diǎn)GetDirectPostNode(Node Delnode){//方法用于獲取直接后繼節(jié)點(diǎn)108 109節(jié)點(diǎn)parentNode delNode//父節(jié)點(diǎn)110node direcpstnodedelnode用于保存待刪除節(jié)點(diǎn)的直接后繼節(jié)點(diǎn)//直接后繼節(jié)點(diǎn)110nnull){ 113 parent node direcrPostNode 114 direcrPostNode current node 115 current node current node . left child 116 } 117 if(direcrPostNode！DelNode.rightChild) {//從樹中刪除這個直接后繼節(jié)點(diǎn)118。Leftchild DirecPostnode。Rightchild 119 DirecPostnode。right child null 120 } 121 Return DirecPostnode//返回此直接后繼節(jié)點(diǎn)122 123 }124。125 public void preOrder(Node root Node){ 126 if(root Node！null){ 127()128 preOrder(root Node . left child)129 preOrder(root Node . right child)130 } 131 } 132 133 public void in order(Node root Node){ 134 if(root Node！null){ 135 in order(root Node . left child)136 (k:·valu:)137 in order(root Node . right child)138 } 139 } 140 141 public void post order(Node root Node){ 142 if(root Node！null){ 143 post order(rootnode . left child)144 post order(rootnode . right child)145()146 } 147 } private void destroy(Node tree){ if(tree null)return if(tree . left！null)銷毀(tree.leftChild) if (tree.right！null)destroy(tree . right child)tree null } public void destory(){ destory(root)} 148 } 149 public class binarysearchtreeapp { 150 public static void main(string[]args){ 151 tree tree new tree()152(6，6)//insert操作，二叉樹153 (3，3) 154 (14，14) 155 (16，16) 156 (10，10) 157 (9，9) 15811) 160 (12，12) 161 162(刪除前的遍歷結(jié)果)163 ()//中間遍歷操作164 165(刪除節(jié)點(diǎn)10后的遍歷結(jié)果)166 (10)//刪除操作167 () 168} 169}測試結(jié)果: