算法-二叉查找樹BST

BST是一種 。若它的左子樹不為空，則左子樹上的所有節點的值均小於根節點的值；若它的右子樹不為空，則右子樹上的所有節點的值均大於根節點的值；左右子樹又各是一顆二叉排序樹；沒有鍵值相等的節點。

1、查找

BST的查找從根節點開始，沿著某一個分支逐層向下比較。先和根節點比較，如果大於根節點值在右子樹繼續查找，小於根節點值在左子樹查找。

 private TreeNode<integer> getByValue(TreeNode<integer> node, int value) {
 if (null == node) {
 return null;
 }
 if (value < node.getData()) { // 查找左樹
 return getByValue(node.getLeftChild(), value);
 } else if (value == node.getData()) { // 找到當前值，返回
 return node;
 } else { // 查找右樹
 return getByValue(node.getRightChild(), value);
 }
 }
/<integer>/<integer>

2、插入

從根節點開始，如果即將插入的值小於節點的值，往左子樹遞歸查找；如果大於節點的值，往右子樹遞歸查找。直到找到空節點時，插入數據

 private TreeNode<integer> insertNode(TreeNode<integer> node, Integer value) {
 TreeNode<integer> newNode = new TreeNode<integer>(); 

 newNode.setData(value);
 // 1. 如果x為null，返回新添加的節點
 if (null == node) {
 return newNode;
 }
 if (node.getData() > value) {// 要添加的value node.setLeftChild(insertNode(node.getLeftChild(), value));
 } else if (node.getData() < value) {// 要添加的value>當前value，往其右子樹添加
 node.setRightChild(insertNode(node.getRightChild(), value));
 }
 // 2. 如果不為null的返回值為當前節點
 return node;
 }
/<integer>/<integer>/<integer>/<integer>

3、遍歷

文章中已經詳細描述。

4、查找小於等於指定值v的最大值

如果給定的值v小於根節點的值，那麼查找的值肯定在二叉樹的左側；如果給定的值v等於根節點的值，根節點就是要找的值；如果給定的值v大於根節點的值，那麼只有當根節點的右子樹中存在小於等於給定值v的節點時，查找的值才會出現在右子樹，否則就是根節點。

 /* 查找小於等於指定鍵的最大值 */
 private TreeNode<integer> getFloorNode(TreeNode<integer> node, int value) {
 if (null == node) {
 return null;
 } 

 if (value == node.getData()) {
 return node;
 }
 if (value < node.getData()) {
 return getFloorNode(node.getLeftChild(), value);
 }
 TreeNode<integer> t = getFloorNode(node.getRightChild(), value);
 if (null != t) {
 return t;
 } else {
 return node;
 }
 }
/<integer>/<integer>/<integer>

5、查找大於等於指定值v的最小值

如果給定的值v大於根節點的值，那麼要查找的值肯定在根節點的右子樹；如果給定的值v等於根節點的值，那麼要查找的值就是根節點的值；如果給定的值v小於根節點的值，那麼當且僅當根節點的左子樹中存在大於等於給定值v的節點時，才會出現在左子樹中，否則就是根節點。

 /* 查找大於等於指定鍵的最小值 */
 private TreeNode<integer> getCeilNode(TreeNode<integer> node, int value) {
 if (null == node) {
 return null;
 }
 if (value == node.getData()) {
 return node;
 }
 if (value > node.getData()) {
 return getCeilNode(node.getRightChild(), value);
 }
 TreeNode<integer> t = getCeilNode(node.getLeftChild(), value);
 if (null != t) {
 return t;
 } else { 

 return node;
 }
 }
/<integer>/<integer>/<integer>

6、刪除指定節點

如果被刪節點z是葉子節點，則直接刪除；若節點z只有一顆左子樹或右子樹，則讓z的子樹成為z父節點的子樹，替代z的位置；若節點z有左、右兩棵樹，取出節點z右子樹的最小節點替換當前節點。

 /* 刪除指定節點 */
 public TreeNode<integer> delete(TreeNode<integer> node, int value) {
 //1. 如果node為null，返回null
 if(node == null) {
 return null;
 }
 
 
 if(node.getData() > value) {
 node.setLeftChild(delete(node.getLeftChild(),value));
 }else if(node.getData() < value) {
 node.setRightChild(delete(node.getRightChild(),value)); 
 }else {
 if(node.getLeftChild() == null) {
 return node.getRightChild();
 }
 if(node.getRightChild() == null) {
 return node.getLeftChild();
 }
 //取出要刪除節點右子樹的最小節點替換當前節點
 TreeNode<integer> t = node;
 node = min(node.getRightChild());
 node.setRightChild(deleteMin(t.getRightChild()));
 node.setLeftChild(t.getLeftChild());
 }
 //2. 否則返回當前節點 

 return node;
 }
 
 /* 獲取最小值 */
 public TreeNode<integer> min(TreeNode<integer> node) {
 if(node.getLeftChild() == null) {
 return node;
 }
 return min(node.getLeftChild());
 }
/<integer>/<integer>/<integer>/<integer>/<integer>