学步园

好像一个多星期没写代码了，感觉手生很，脑袋不转啊。还是复习一下算法，今天早上把二叉查找树重写了一遍，而且还把节点的删除完全看明白了，

package com.kinglong.binarytree;<br /> /**<br /> * @author kinglong<br /> * @version 2011-6-26 上午09:29:40<br /> */<br /> public class SearchTree {<br /> private Node root;<br /> public SearchTree() {<br /> root = null;<br /> }<br /> public SearchTree(Node root) {<br /> this.root = root;<br /> }<br /> // 插入节点<br /> public void insert(Node node) {<br /> if (root == null) {<br /> root = node;<br /> } else {<br /> Node temp = root;<br /> Node privous = temp;<br /> while (temp != null) {<br /> privous = temp;<br /> if (temp.getData() < node.getData()) {<br /> temp = temp.getRight();<br /> } else {<br /> temp = temp.getLeft();<br /> }<br /> }<br /> if (privous.getData() < node.getData()) {<br /> privous.setRight(node);<br /> } else {<br /> privous.setLeft(node);<br /> }<br /> node.setParent(privous);<br /> }<br /> }<br /> // 返回最小值的节点(默认值为)<br /> public Node Minimum() {<br /> return Minimum(root);<br /> }<br /> public Node Minimum(Node node) {<br /> Node temp = node;<br /> while (temp.getLeft() != null) {<br /> temp = temp.getLeft();<br /> }<br /> return temp;<br /> }</p> <p> // 返回最大值的节点<br /> public Node Maximum() {<br /> Node temp = root;<br /> while (temp.getRight() != null) {<br /> temp = temp.getRight();<br /> }<br /> return temp;<br /> }<br /> // 查询包含关键字K的节点(非递归)<br /> public Node search(int k) {<br /> Node x = root;<br /> while (x != null) {<br /> if (x == null || k == x.getData()) {<br /> return x;<br /> } else if (k < x.getData()) {<br /> x = x.getLeft();<br /> } else {<br /> x = x.getRight();<br /> }<br /> }<br /> return x;<br /> }<br /> //查找包含关键字k的节点(递归)<br /> public Node searchRecursive(Node node, int k) {<br /> if (node == null || k == node.getData()) {<br /> return node;<br /> }<br /> if (k < node.getData()) {<br /> return searchRecursive(node.getLeft(), k);<br /> } else {<br /> return searchRecursive(node.getRight(), k);<br /> }</p> <p> }</p> <p> //返回后继节点<br /> public Node successor(int k) {<br /> Node node = search(k);<br /> return successor(node);<br /> }</p> <p> public Node successor(Node node) {</p> <p> if (node.getRight() != null) {<br /> return Minimum(node.getRight());<br /> }</p> <p> Node temp = node;<br /> Node parent = node.getParent();</p> <p> while (parent != null && parent.getRight() == temp) {<br /> temp = parent;<br /> parent = parent.getParent();<br /> }<br /> return parent;<br /> }</p> <p> //返回前驱节点<br /> public Node predecessor(int k) {<br /> Node node = search(k);<br /> return predecessor(node);</p> <p> }</p> <p> public Node predecessor(Node node) {</p> <p> if (node.getLeft() != null) {<br /> return node.getLeft();<br /> }</p> <p> Node temp = node;<br /> Node parent = node.getParent();</p> <p> while (parent != null && parent.getLeft() == temp) {<br /> temp = parent;<br /> parent = parent.getParent();<br /> }<br /> return parent;<br /> }<br /> //删除关键字为k的节点<br /> public Node delete(int k) {</p> <p> Node node = search(k);<br /> Node temp = null;<br /> Node tempChild = null;</p> <p> if (node.getLeft() == null || node.getRight() == null) {<br /> temp = node;<br /> } else {<br /> temp = successor(node);<br /> }</p> <p> if (temp.getLeft() != null) {<br /> tempChild = temp.getLeft();<br /> } else {<br /> tempChild = temp.getRight();<br /> }</p> <p> if (tempChild != null) {<br /> tempChild.setParent(temp.getParent());<br /> }</p> <p> if (temp.getParent() == null) {<br /> root = tempChild;<br /> } else if (temp.getParent().getRight() == temp) {<br /> temp.getParent().setRight(tempChild);<br /> } else if (temp.getParent().getLeft() == temp) {<br /> temp.getParent().setLeft(tempChild);<br /> }</p> <p> if (temp != node) {<br /> node.setData(temp.getData());<br /> }<br /> return temp;<br /> }</p> <p> //中序遍历<br /> public void printTree() {</p> <p> printTree(root);<br /> System.out.println(" ");<br /> }</p> <p> public void printTree(Node node) {<br /> if (node != null) {<br /> printTree(node.getLeft());<br /> System.out.print(node.getData() + " ");<br /> printTree(node.getRight());<br /> }<br /> }</p> <p>}<br /> class Node {<br /> private Node left;<br /> private Node right;<br /> private Node parent;<br /> private int data;<br /> public Node() {<br /> }<br /> public Node(int data) {<br /> this(data, null, null, null);<br /> }<br /> private Node(int data, Node parent, Node left, Node right) {<br /> this.data = data;<br /> this.left = left;<br /> this.parent = parent;<br /> this.right = right;<br /> }<br /> public Node getLeft() {<br /> return left;<br /> }<br /> public void setLeft(Node left) {<br /> this.left = left;<br /> }<br /> public Node getRight() {<br /> return right;<br /> }<br /> public void setRight(Node right) {<br /> this.right = right;<br /> }<br /> public Node getParent() {<br /> return parent;<br /> }<br /> public void setParent(Node parent) {<br /> this.parent = parent;<br /> }<br /> public int getData() {<br /> return data;<br /> }<br /> public void setData(int data) {<br /> this.data = data;<br /> }<br /> } 

测试代码：

package com.kinglong.binarytree;<br /> /**<br /> *@author kinglong<br /> *@version 2011-6-26 上午10:41:38<br /> */<br /> public class SearchTest {<br /> public static void main(String[] args) {<br /> SearchTree tree = new SearchTree();<br /> tree.insert(new Node(5));<br /> tree.insert(new Node(2));<br /> tree.insert(new Node(10));<br /> tree.insert(new Node(17));<br /> tree.insert(new Node(3));<br /> tree.printTree();<br /> System.out.println("最大值："+tree.Maximum().getData());<br /> System.out.println("最小值："+tree.Minimum().getData());<br /> tree.delete(5);//删除5<br /> tree.printTree();<br /> System.out.println("节点3 的前驱为：" + tree.predecessor(3).getData());<br /> tree.insert(new Node(12));<br /> System.out.println("节点12的后继为：" + tree.successor(12).getData());<br /> }<br /> } 

算法的重点在于找节点的后继，节点的前驱，和删除。