二叉查找树系列

 

import java.util.ArrayList;
import java.util.List;
//author:lilywangcn
class Node {
	public Node left = null;
	public Node right = null;
	public int key;

	public Node(int key) {
		this.key = key;
	}
}

public class BinaryTree {
	public Node root;

	public BinaryTree() {
		root = null;
	}

	public Node search(int key, Node current) {  //查找节点
		if (current == null)
			return null;
		if (current.key == key)
			return current;
		else if (key < current.key) {
			return search(key, current.left);
		} else {
			return search(key, current.right);
		}
	}

	public void insert(int key) {                //插入节点
		if (root == null) {
			root = new Node(key);
			return;
		}
		Node current = root;
		Node parent = root;
		boolean isLeftChild = true;
		while (current != null) {
			parent = current;
			if (key < current.key) {
				current = current.left;
				isLeftChild = true;
			} else {
				current = current.right;
				isLeftChild = false;
			}
		}

		if (isLeftChild) {
			parent.left = new Node(key);
		} else {
			parent.right = new Node(key);
		}
	}

	public void preorder(Node current) {                   //先序遍历
		if (current == null)
			return;
		preorder(current.left);
		System.out.print(current.key + " ");
		preorder(current.right);
	}

	public void inorder(Node current) {                        //中序遍历
		if (current == null)
			return;
		System.out.print(current.key + " ");
		inorder(current.left);
		inorder(current.right);
	}

	public void delete(int key) {                                  //删除节点
		if (root == null)
			return;
		Node parent = root;
		Node delNode = parent;
		boolean isLeft = true;
		while (delNode!=null && delNode.key != key ) {
			parent = delNode;
			if (key < delNode.key) {
				delNode = delNode.left;
				isLeft = true;
			} else {
				delNode = delNode.right;
				isLeft = false;
			}
		}       //查找到删除的节点以及其父节点，弄清楚被删除节点在父节点的左节点还是右节点
		if(delNode==null) {
			System.out.println("delnode not exists, eixt!");
			return;
		}                                                              

		if (delNode.left == null && delNode.right == null) {         //如果删除节点是叶子节点
			if (delNode == root)
				root = null;
			else if (isLeft) {
				parent.left = null;
			} else
				parent.right = null;
			return;
		}

		if (delNode.right == null) {                                 //如果删除节点只有一个子节点，使用这个节点的子节点替换删除节点
			if (delNode == root)
				root = root.left;
			else if (isLeft) {
				parent.left = delNode.left;
			} else {
				parent.right = delNode.left;
			}
			return;
		}

		if (delNode.left == null) {
			if (delNode == root)
				root = root.right;
			else if (isLeft) {
				parent.left = delNode.right;
			} else {
				parent.right = delNode.right;
			}
			return;
		}

		Node parentSuccessor = delNode.right;               //如果删除节点有两个子节点，找到它的后继节点替换它
		Node successor = delNode.right;
		while (successor.left != null) {
			parentSuccessor = successor;
			successor = successor.left;
		}

		if (successor == delNode.right) {                           //后继节点是删除节点的右子节点，机后继节点没有左子树
			successor.left = delNode.left;
			if (delNode == root) {
				root = successor;
				return;
			} else if (isLeft) {
				parent.left = successor;
			} else {
				parent.right = successor;
			}
		} else {
			parentSuccessor.left = successor.right;        //后继节点是删除节点右子节点的左子树上的最左边节点     
			successor.left = delNode.left;
			successor.right = delNode.right;
			if (delNode == root) {
				root = successor;
			} else if (isLeft) {
				parent.left = successor;
			} else {
				parent.right = successor;
			}
		}

	}

      public void printlevel(Node node, int n){                        //打印层数为n的节点
		if(node==null) return;
		if(n==1) System.out.print(node.key+" ");
		printlevel(node.left,n-1);
		printlevel(node.right,n-1);
	}

      private int depth(Node node, int n){                            //获取树的深度=max（左子树的深度，右子树的深度）+1
		if(node==null) return n;
		int left=depth(node.left,n+1);
		int right=depth(node.right,n+1);
		return left>right?left:right;
	}

	public void printtree(){

		List<Node> arrayList=new ArrayList<Node>();
		List pos=new ArrayList();
		int cur=0;
		int last=0;
		pos.add(cur);
		Node current=root;
		arrayList.add(current);
		while(last >= cur){
			int end=last;
			while(cur<=end){
				current=arrayList.get(cur);
				System.out.print(current.key+ " ");
				if(current.left!=null) {
					arrayList.add(current.left);
					last++;
				}
				
				if(current.right!=null){
					arrayList.add(current.right);
					last++;
				}
				cur++;
			}
			System.out.println("");
			pos.add(cur);
		}
		
		System.out.println("reverse:");                                            //逆序层层遍历树，层节点逆序
		int j=pos.size()-2;
		for(int i=arrayList.size()-1; i>=0; i--){
			System.out.print(arrayList.get(i).key+" ");
			
			if(i == (Integer)pos.get(j)) {
				j--;
				System.out.println("");
			}
			
		}
		System.out.println("reverse2:");
		j=pos.size()-2;
		for(int i=(Integer)pos.get(j); i<(Integer)pos.get(j+1);){   //逆序层层遍历树，层节点顺序
			
			System.out.print(arrayList.get(i).key+" ");
			i++;
			if(i == (Integer)pos.get(j+1)) {
				j--;
				System.out.println("");
				if(j<0) break;
				i=(Integer)pos.get(j);
			}
			
		}
	}
	
	public static void main(String[] args) {
		System.out.println("build the tree");
		BinaryTree bt = new BinaryTree();
		bt.preorder(bt.root);
		bt.insert(50);
		bt.insert(25);
		bt.insert(75);
		bt.insert(12);
		bt.insert(37);
		bt.insert(43);
		bt.insert(30);
		bt.insert(33);
		bt.insert(87);
		bt.insert(93);
		bt.insert(97);

		System.out.println("preorder the tree");
		bt.preorder(bt.root);
		System.out.println("\ninorder the tree");
		bt.inorder(bt.root);
		System.out.println("\nsearch the tree");

		if (bt.search(93, bt.root) != null) {
			System.out.println("find!");
		} else {
			System.out.println("not find!");
		}
		System.out.println("before delete the node");
		int depth=bt.depth(bt.root, 0);
		for(int i=1;i<=depth;i++){
			bt.printlevel(bt.root,i);
			System.out.println("");
		}
		
		bt.delete(50);
		System.out.println("after delete the node");

		for(int i=1;i<=depth;i++){
			bt.printlevel(bt.root,i);
			System.out.println("");
		}
		
		bt.printtree();
	}

}

运行结果：

build the tree
preorder the tree
12 25 30 33 37 43 50 75 87 93 97 
inorder the tree
50 25 12 37 30 33 43 75 87 93 97 
search the tree
find!
before delete the node
50 
25 75 
12 37 87 
30 43 93 
33 97 
after delete the node
75 
25 87 
12 37 93 
30 43 97 
33 
print the tree
75 
25 87 
12 37 93 
30 43 97 
33 
reverse:
33 
97 43 30 
93 37 12 
87 25 
75 
reverse2:
33 
30 43 97 
12 37 93 
25 87 
75