為什么80%的碼農都做不了架構師？>>> ??

?????? 樹結構同時集成了數組查找迅速和鏈表添刪迅速的優點。先來看看普通的搜索二叉樹的實現：

package com.wly.algorithmbase.datastructure;/*** 二叉搜索樹* @author wly*/ public class BinaryTree {private static BTreeNode root;public static void main(String[] args) {BinaryTree tree = new BinaryTree();tree.insert(new BTreeNode(11, 23));tree.insert(new BTreeNode(6, 12));tree.insert(new BTreeNode(16, 51));tree.insert(new BTreeNode(3, 32));tree.insert(new BTreeNode(9, 42));tree.insert(new BTreeNode(14, 52));tree.insert(new BTreeNode(19, 62));tree.insert(new BTreeNode(13, 72));tree.insert(new BTreeNode(12, 82));tree.find(2);tree.print(root);tree.delete(11);tree.print(root);}/*** 插入節點* 關鍵在于緩存當前節點，檢查當前節點的子節點*/public void insert(BTreeNode node) {if(root == null) {root = node;} else {BTreeNode currentNode = root;BTreeNode parent;while(true) {parent = currentNode;if(node.getKey() < currentNode.getKey()) {currentNode = currentNode.getLeft();if(currentNode == null) {parent.setLeft(node);return;}} else {currentNode = currentNode.getRight();if(currentNode == null) {parent.setRight(node);return;}}}}}/*** 根據關鍵字查找*/public BTreeNode find(int key) {BTreeNode current = root;while(true) {if(current == null) {System.out.println("未查找到key=" + key + "的節點");return null;} else {if(current.getKey() > key) {current = current.getLeft();} else if(current.getKey() < key) {current = current.getRight();} else {System.out.println("查找到key=" + key + ",data=" + current.getData() + "的節點");return current;}}}}/*** 根據key值刪除節點,刪除的成功與否取決于是否存在該節點* @param key* @return true刪除成功，false刪除失敗*/public boolean delete(int key) {BTreeNode deleteNode = find(key);if(deleteNode == null) {System.out.println("未查找到key=" + key + "的節點，無法進行刪除");return false;} else {removeFromTree(deleteNode);System.out.println("成功刪除key=" + key + "的節點");return true;}}/*** 將自身從樹中移除*/public void removeFromTree(BTreeNode node) {//1.自身不包含子節點if(node.getLeft() == null && node.getRight() == null) { if(node.isLeft) {node.getParent().setLeft(null);} else {node.getParent().setRight(null);}}//2.包含一個子節點if(node.getLeft() != null && node.getRight() == null) {if(node.isLeft) {node.getParent().setLeft(node.getLeft());} else {node.getParent().setRight(node.getLeft());}} else if(node.getLeft() == null && node.getRight() != null) {if(node.isLeft) {node.getParent().setLeft(node.getRight());} else {node.getParent().setRight(node.getRight());}}//3.包含兩個子節點//查找后繼節點BTreeNode successorNode = node.getSuccessor(node); //從樹種移除該后繼節點if(successorNode.getParent() != null) {if(successorNode.isLeft) {successorNode.getParent().setLeft(null);} else {successorNode.getParent().setRight(null);}}successorNode.setLeft(node.getLeft());successorNode.setRight(node.getRight());//從樹中移除待刪除節點，并用后繼節點替換if(node.getParent() != null) {if(node.isLeft) {node.getParent().setLeft(successorNode);} else {node.getParent().setRight(successorNode);}} else {root = successorNode;}}/*** 打印樹結構*/public void print(BTreeNode node) {if(node != null) {System.out.print(node.getKey() + "|" + node.getData());System.out.println();}if(node.getLeft() != null) {print(node.getLeft());}if(node.getRight() != null) {print(node.getRight());}}}/*** 節點類* @author wly**/ class BTreeNode {private BTreeNode left;private BTreeNode right;private BTreeNode parent;boolean isLeft; //是左子節點嗎，否則就是右子節點int key; //檢索關鍵字int data; //包含的數據對象public BTreeNode() {super();}public BTreeNode(int key, int data) {super();this.key = key;this.data = data;}public BTreeNode getLeft() {return left;}public void setLeft(BTreeNode left) {this.left = left;if(left != null) {left.parent = this;left.isLeft = true;}}public BTreeNode getRight() {return right;}public void setRight(BTreeNode right) {this.right = right;if(right != null) {right.parent = this;right.isLeft = false;}}public BTreeNode getParent() {return parent;}public void setParent(BTreeNode parent) {this.parent = parent;}public int getKey() {return key;}public void setKey(int key) {this.key = key;}public int getData() {return data;}public void setData(int data) {this.data = data;}/*** 返回指定節點的后繼節點(即大于指定節點的最小節點)* @param node* @return*/public BTreeNode getSuccessor(BTreeNode node) {BTreeNode result = node.getRight(); //先取得右節點if(result == null) {return null;} else {while(result.getLeft() != null) {result = result.getLeft();}}return result;} }

運行結果：

未查找到key=2的節點 11|23 6|12 3|32 9|42 16|51 14|52 13|72 12|82 19|62 查找到key=11,data=23的節點 成功刪除key=11的節點 12|82 6|12 3|32 9|42 16|51 14|52 13|72 19|62

O啦~~~

轉載請保留出處：http://blog.csdn.net/u011638883/article/details/17120363

謝謝!!

轉載于:https://my.oschina.net/cjkall/blog/195814

總結

以上是生活随笔為你收集整理的数据结构_树结构的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。