排序二叉树java的简单实现
本程序实现了基本的对排序二叉树的增和删。
?
?
?
public class SortTreeTest {public static void main(String[] args) {SortTree tree = new SortTree(10); // 初始化一个root并且给一个valuetree.add(7);tree.add(15);tree.add(12);tree.add(16);tree.add(7);tree.add(8);tree.add(4);tree.add(13);tree.read();System.out.println("root.value = " + tree.getRoot().getValue());tree.delete(10);System.out.println("---------after delete---------");tree.read();System.out.println("root.value = " + tree.getRoot().getValue());}}class SortTree {private Node root;private int size;public SortTree(int v) {root = new Node(v);size = 1;}public Node getRoot() {return root;}public void setRoot(Node root) {this.root = root;}public int Size() {return size;}public void add(int value) {if (root == null)return;Node indexRoot = getRoot();Node parent = indexRoot;int indexValue = 0;while (indexRoot != null) {indexValue = indexRoot.getValue();parent = indexRoot;if (value < indexValue) {indexRoot = indexRoot.getLeft();} else if (value > indexValue) {indexRoot = indexRoot.getRight();} else {return;}}Node newNode = new Node(value);if (value < indexValue) {parent.setLeft(newNode);} else if (value > indexValue) {parent.setRight(newNode);} else {return;}newNode.setParent(parent);size++;}public void read() { // 中序遍历read(root);}public void read(Node node) {if (node.getLeft() != null) {read(node.getLeft());}if (node != null) {System.out.println(node.getValue());}if (node.getRight() != null) {read(node.getRight());}}public void delete(int value) {if (root == null)return;Node indexRoot = getRoot();Node parent = indexRoot;int indexValue = indexRoot.getValue();while (indexValue != value && indexRoot != null) {parent = indexRoot;if (value < indexValue) {indexRoot = indexRoot.getLeft();} else if (value > indexValue) {indexRoot = indexRoot.getRight();}if (indexRoot != null) {indexValue = indexRoot.getValue();}}if (indexRoot == null) {return;}// no any nodesif (indexRoot.getLeft() == null && indexRoot.getRight() == null) {if (parent.getLeft() == indexRoot) { // if is leftNodeparent.setLeft(null);} else { // if is rightNodeparent.setRight(null);}return;}// has only left nodeif (indexRoot.getLeft() != null && indexRoot.getRight() == null) {if (indexRoot == this.getRoot()) { // if deleted is rootsetRoot(indexRoot.getLeft());indexRoot = null;} else {parent.setLeft(indexRoot.getLeft());indexRoot.getLeft().setParent(parent);indexRoot = null;}return;}// has only right nodeif (indexRoot.getLeft() == null && indexRoot.getRight() != null) {if (indexRoot == this.getRoot()) { // if deleted is rootsetRoot(indexRoot.getRight());indexRoot = null;} else {parent.setRight(indexRoot.getRight());indexRoot.getRight().setParent(parent);indexRoot = null;}return;}// has two nodeif (indexRoot.getLeft() != null && indexRoot.getRight() != null) {// 找到删除节点的后继节点Node afterNode = indexRoot.getRight();Node afterFather = indexRoot;while (afterNode.getLeft() != null) {afterFather = afterNode;afterNode = afterNode.getLeft();}if (afterFather == indexRoot) {parent.setRight(afterNode);afterNode.setParent(parent);afterNode.setLeft(indexRoot.getLeft());indexRoot.getLeft().setParent(afterNode);if (indexRoot == this.getRoot()) { //if delete is rootsetRoot(afterNode);}} else {//比较复杂if(afterNode.getRight()!= null) {afterFather.setLeft(afterNode.getRight());afterNode.getRight().setParent(afterFather);}else {afterFather.setLeft(null);}afterNode.setRight(indexRoot.getRight());indexRoot.getRight().setParent(afterNode);parent.setRight(afterNode);afterNode.setParent(parent);afterNode.setLeft(indexRoot.getLeft());indexRoot.getLeft().setParent(afterNode);if(indexRoot == this.getRoot()) {this.setRoot(afterNode);}}indexRoot = null;}}}?
忘记了放Node类，补上。
?
//Node类public class Node {private Node left;private Node right;private int value;private Node parent;public Node(int v) {this.value = v;}public Node() {}public Node getLeft() {return left;}public void setLeft(Node left) {this.left = left;}public Node getRight() {return right;}public void setRight(Node right) {this.right = right;}public int getValue() {return value;}public void setValue(int value) {this.value = value;}public Node getParent() {return parent;}public void setParent(Node parent) {this.parent = parent;}}??
?
?
输出：
?
?
?
4
7
8
10
12
13
15
16
root.value = 10
---------after delete---------
4
7
8
12
13
15
16
root.value = 12