学步园

二叉树的基本操作，代码如下

package 二叉树;

import java.util.ArrayList;
import java.util.List;

public class BinaryTree<E extends Comparable<E>>{
	private TreeNode<E> root;
	private int size;
	private List<E> inorderList = new ArrayList<E>();
	private List<E> preorderList = new ArrayList<E>();
	private List<E> postorderList = new ArrayList<E>();
	
	public BinaryTree(){
	}
	
	public BinaryTree(E[] objects){
		for(E e : objects){
			insert(new TreeNode<E>(e));
		}
	}
	
	public TreeNode<E> search(E e){
		TreeNode<E> current = root;
		
		while(current != null && e.compareTo(current.element) != 0){
			if(e.compareTo(current.element) < 0){
				current = current.left;
			}else{
				current = current.right;
			}
		}
		
		return current;
	}
	
	public TreeNode<E> min(TreeNode<E> x){
		while(x.left != null){
			x = x.left;
		}
		
		return x;
	}
	
	public TreeNode<E> max(TreeNode<E> x){
		while(x.right != null){
			x = x.right;
		}
		
		return x;
	}
	
	/**
	 * 找到节点x的后继
	 * @return x的后继
	 */
	public TreeNode<E> successor(TreeNode<E> x){
		if(x.right != null){
			return min(x.right);
		}
		
		TreeNode<E> y = x.parent;
		while(y != null && x.element.compareTo(y.right.element) == 0){
			x = y;
			y = y.parent;
		}
		return y;
	}
	
	/**
	 * 找出节点x的前驱
	 *@return x的前驱
	 */
	public TreeNode<E> predecessor(TreeNode<E> x){
		if(x.left != null){
			return max(x.left);
		}
		
		TreeNode<E> y = x.parent;
		while(y != null && x.element.compareTo(y.left.element) == 0){
			x = y;
			y = y.parent;
		}
		return y;
	}
	
	public void insert(TreeNode<E> z){
		TreeNode<E> x = root;
		TreeNode<E> y = null;
		
		while(x != null){
			y = x;
			if(z.element.compareTo(x.element) > 0){
				x = x.right;
			}else{
				x = x.left;
			}
		}
		z.parent = y;
		
		if(y == null){
			root = z;  // Tree was empty
		}
		else if(z.element.compareTo(y.element) < 0){
			y.left = z;
		}else{
			y.right = z;
		}
	}
	
	public void transplant(TreeNode<E> u, TreeNode<E> v){
		if(u.parent == null){
			root = v;
		}
		else if(u.parent.left == u){
			u.parent.left = v;
		}
		else{
			u.parent.right = v;
		}
		
		if(v != null){
			v.parent = u.parent;
		}
	}
	
	public void delete(E e){
		TreeNode<E> current = search(e);
		delete(current);
	}
	
	public void delete(TreeNode<E> z){
		if(z.left == null){
			transplant(z, z.right);
		}else if(z.right == null){
			transplant(z, z.left);
		}else{   // z的两个孩子都有, 那就找到z的后继者
			TreeNode<E> y = min(z.right);
			if(y.parent != z){
				transplant(y, y.right);   // 为什么第二个参数是y.right，因为y就处在z.right的最左边
				y.right = z.right;
				y.right.parent = y;
			}
			transplant(z, y);
			y.left = z.left;
			y.left.parent = y;
		}
	}
	
	public void inorder(){
		inorder(root);
	}
	
	public void inorder(TreeNode<E> root){
		if(root != null){
			inorder(root.left);
			System.out.print(root.element + " ");
			inorderList.add(root.element);
			inorder(root.right);
		}
	}
	
	public void preorder(){
		preorder(root);
	}
	
	public void preorder(TreeNode<E> root){
		if(root != null){
			System.out.print(root.element + " ");
			preorderList.add(root.element);
			preorder(root.left);
			preorder(root.right);
		}
	}
	
	public void postorder(){
		postorder(root);
	}
	
	public void postorder(TreeNode<E> root){
		if(root != null){
			postorder(root.left);
			postorder(root.right);
			System.out.print(root.element + " ");
			postorderList.add(root.element);
		}
	}
}

package 二叉树;

public class TreeNode <E extends Comparable<E>>{
	E element;
	TreeNode<E> left;
	TreeNode<E> right;
	TreeNode<E> parent;
	
	public TreeNode(E e){
		element = e;
	}
}

package 二叉树;

public class TestBinaryTree {
	
	public static void main(String[] args) {
		// TODO 自动生成方法存根
		BinaryTree<String> tree = new BinaryTree<String>();
		tree.insert(new TreeNode<String>("George"));
		tree.insert(new TreeNode<String>("Michael"));
		tree.insert(new TreeNode<String>("Tom"));
		tree.insert(new TreeNode<String>("Adam"));
		tree.insert(new TreeNode<String>("Jones"));
		tree.insert(new TreeNode<String>("Peter"));
		tree.insert(new TreeNode<String>("Daniel"));
		
		// Traverse tree
		System.out.print("Inorder (sorted): ");
		tree.inorder();
		System.out.print("\nPostorder: ");
		tree.postorder();
		System.out.print("\nPreorder: ");
		tree.preorder();
		tree.delete("Jones");
		System.out.print("\nAfter delete Jones: ");
		System.out.print("\nInorder (sorted): ");
		tree.inorder();
		System.out.print("\nPostorder: ");
		tree.postorder();
		System.out.print("\nPreorder: ");
		tree.preorder();
		
		Integer[] numbers = {10, 5, 1, 7, 17, 13, 20};
		BinaryTree<Integer> intTree = new BinaryTree<Integer>(numbers);
		System.out.print("\nInorder (sorted): ");
		intTree.inorder();
		intTree.delete(7);
		intTree.delete(1);
		System.out.print("\nAfter delete 7, 1: ");
		System.out.print("\nInorder (sorted): ");
		intTree.inorder();
	}

}

运行结果：

Inorder (sorted): Adam Daniel George Jones Michael Peter Tom 
Postorder: Daniel Adam Jones Peter Tom Michael George 
Preorder: George Adam Daniel Michael Jones Tom Peter 
After delete Jones: 
Inorder (sorted): Adam Daniel George Michael Peter Tom 
Postorder: Daniel Adam Peter Tom Michael George 
Preorder: George Adam Daniel Michael Tom Peter 
Inorder (sorted): 1 5 7 10 13 17 20 
After delete 7, 1: 
Inorder (sorted): 5 10 13 17 20