排序二叉树java的简略实现

排序二叉树java的简单实现

本程序实现了基本的对排序二叉树的增和删。

 

 

 

public class SortTreeTest {
	public static void main(String[] args) {
		SortTree tree = new SortTree(10); // 初始化一个root并且给一个value
		tree.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 nodes
		if (indexRoot.getLeft() == null && indexRoot.getRight() == null) {
			if (parent.getLeft() == indexRoot) { // if is leftNode
				parent.setLeft(null);
			} else { // if is rightNode
				parent.setRight(null);
			}
			return;
		}

		// has only left node
		if (indexRoot.getLeft() != null && indexRoot.getRight() == null) {
			if (indexRoot == this.getRoot()) { // if deleted is root
				setRoot(indexRoot.getLeft());
				indexRoot = null;
			} else {
				parent.setLeft(indexRoot.getLeft());
				indexRoot.getLeft().setParent(parent);
				indexRoot = null;
			}
			return;
		}

		// has only right node
		if (indexRoot.getLeft() == null && indexRoot.getRight() != null) {
			if (indexRoot == this.getRoot()) { // if deleted is root
				setRoot(indexRoot.getRight());
				indexRoot = null;
			} else {
				parent.setRight(indexRoot.getRight());
				indexRoot.getRight().setParent(parent);
				indexRoot = null;
			}
			return;
		}

		// has two node
		if (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 root
					setRoot(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