Java数据结构—-二叉树

二叉树

代码：

package BianaryTree;

class treeNode {
	int value;
	treeNode left;
	treeNode right;

	public treeNode(int value) {
		this.value = value;
	}

	public void setLeft(treeNode left) {
		this.left = left;
	}

	public void setRight(treeNode right) {
		this.right = right;
	}

	// 前序遍历
	public void frontshow() {

		System.out.print(value);
		if (left != null) {
			left.frontshow();
		}
		if (right != null) {
			right.frontshow();
		}

	}

	// 中序遍历
	public void showMid() {

		if (left != null) {
			left.showMid();
		}
		System.out.print(value);
		if (right != null) {
			right.showMid();
		}

	}

	// 后序遍历
	public void showafter() {

		if (left != null) {
			left.showafter();
		}

		if (right != null) {
			right.showafter();
		}
		System.out.print(value);

	}

	// 前序查找
	public treeNode frontSearch(int i) {

		treeNode target = null;
		// 对比当前节点的值
		if (this.value == i) {
			return this;
		} else {
			// 查找左儿子
			if (left != null) {
				// 有可能查不到
				target = left.frontSearch(i);

			}
			// 不为空，说明左儿子已经查到
			if (target != null) {
				return target;
			}
			// 查找右儿子
			if (right != null) {
				target = right.frontSearch(i);
			}

		}

		return target;
	}

	public void delete(int i) {
		treeNode parent = this;
		// 判断左儿子
		if (parent.left != null && parent.left.value == i) {
			parent.left = null;
			return;

		}
		// 判断右儿子
		if (parent.right != null && parent.right.value == i) {
			parent.right = null;
			return;
		}
		// 如果都不是
		// 递归检查并删除左儿子
		parent = left;
		if (parent != null) {
			parent.delete(i);
		}
		// 递归检查并删除右儿子
		parent = right;
		if (parent != null) {
			parent.delete(i);
		}

	}

}

public class Binarytree {
	treeNode root;

	public void setRoot(treeNode root) {
		this.root = root;
	}

	public treeNode getRoot() {
		return root;
	}

	private void showFront() {
		// TODO Auto-generated method stub
		if (root != null)
			root.frontshow();
	}

	private void showMid() {
		// TODO Auto-generated method stub
		if (root != null)
			root.showMid();
	}

	private void showafter() {
		// TODO Auto-generated method stub
		if (root != null)
			root.showafter();

	}

	private treeNode frontSearch(int i) {
		// TODO Auto-generated method stub
		return root.frontSearch(i);
	}

	private void delete(int i) {
		// TODO Auto-generated method stub
		if (root.value == i) {
			root = null;
		} else {
			root.delete(i);
		}

	}

	public static void main(String[] args) {
		Binarytree binarytree = new Binarytree();
		treeNode root = new treeNode(1);
		treeNode rootL = new treeNode(2);
		treeNode rootR = new treeNode(3);
		// 创建一个根节点
		binarytree.setRoot(root);
		// 左子点
		root.setLeft(rootL);
		// 右子点
		root.setRight(rootR);
		// 为第二层的左子点创建两个子节点
		rootL.setLeft(new treeNode(4));
		rootL.setRight(new treeNode(5));
		// 第二层右子点创建子节点
		rootR.setLeft(new treeNode(6));
		rootR.setRight(new treeNode(7));
		System.out.println("前序遍历");
		binarytree.showFront();
		System.out.println("\n中序遍历");
		binarytree.showMid();
		System.out.println("\n后序遍历");
		binarytree.showafter();
		treeNode result = binarytree.frontSearch(2);
		// 输出一个对象，如果有就是查到了
		System.out.println("\n" + result);
		// 删除一个子树
		binarytree.delete(3);
		binarytree.showFront();

	}

}

二叉顺序树

class TreeNode{
	//节点的权
	public int value;
	//左儿子
	public TreeNode left;
	//右儿子
	public TreeNode right;
	
	public TreeNode(int value){
		this.value=value;
		this.left=null;
		this.right=null;
	}

}
public class BinaryTree {
	private TreeNode root;
	public BinaryTree(){
		root=null;		
	}
	public void insert (int value){
		TreeNode newNode=new TreeNode(value); 
		if(root==null){
			root=newNode;
		}else{
			TreeNode current =root;
			TreeNode parent;
			//寻找插入的位置
			while(true){
				parent=current;
				if(value<current.value){
					current=current.left;
					if(current==null){
						parent.left=newNode;
						return;
					}
				}else{
					current=current.right;
					if(current==null){
						parent.right=newNode;
						return;
					}
				}
			}
			
		}
	}
	//将数值输入构建二叉树
	public void buildTree(int []value){
		for(int i=0;i<value.length;i++){
			insert(value[i]);
		}
	}
	//中序遍历二叉树
	public void inOrder(TreeNode localRoot){
		if(localRoot!=null){
			inOrder(localRoot.left);
			System.out.print(localRoot.value+" ");
			inOrder(localRoot.right);
		}
	}
	public void inOrder(){
		this.inOrder(this.root);
	}
	//先序遍历二叉树
	public void preOrder(TreeNode localRoot){
		if(localRoot!=null){
			System.out.print(localRoot.value+" ");
			preOrder(localRoot.left);			
			preOrder(localRoot.right);
		}
	}
	public void preOrder(){
		this.preOrder(this.root);
	}
	//后序遍历二叉树
	public void nextOrder(TreeNode localRoot){
		if(localRoot!=null){		
			nextOrder(localRoot.left);			
			nextOrder(localRoot.right);
			System.out.print(localRoot.value+" ");
		}
	}
	public void nextOrder(){
		this.nextOrder(this.root);
	}
	
		
	
	public static void main(String[] args) {
		BinaryTree tree=new BinaryTree();
		int []data={2,8,7,4,9,3,1,6,7,5};
		tree.buildTree(data);
		System.out.println("二叉树中序遍历");
		tree.inOrder();		
		System.out.println("\n二叉树先序遍历");
		tree.preOrder();
		System.out.println("\n二叉树后序遍历");
		tree.nextOrder();
		
	
	}
}