二叉排序树java实现

二叉排序树java实现

二叉树排序树是什么?

二叉排序树（Binary Sort Tree）又称二叉查找树、二叉搜索树。 它或者是一棵空树；或者是具有下列性质的二叉树：

• 若左子树不空，则左子树上所有结点的值均小于它的根结点的值；

• 若右子树不空，则右子树上所有结点的值均大于它的根结点的值；

• 左、右子树也分别为二叉排序树；

二叉排序树节点的定义

package tree;

public class TreeNode {
	private int data;//数据
	private TreeNode left;//左子树节点
	private TreeNode right;//右子树节点
	
	public TreeNode(int data, TreeNode left, TreeNode right) {
		super();
		this.data = data;
		this.left = left;
		this.right = right;
	}
	
	

	public TreeNode(int data) {
		super();
		this.data = data;
	}


	public int getData() {
		return data;
	}

	public void setData(int data) {
		this.data = data;
	}

	public TreeNode getLeft() {
		return left;
	}

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

	public TreeNode getRight() {
		return right;
	}

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

	@Override
	public String toString() {
		return "TreeNode [data=" + data+"]";
	}
	
}

二叉排序树类实现

package tree;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;




public class BinaryTree {
	private TreeNode root;

	public BinaryTree() {
		super();
		// TODO Auto-generated constructor stub
	}

	public BinaryTree(TreeNode root) {
		super();
		this.root = root;
	}

	public TreeNode getRoot() {
		return root;
	}

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

	// 前序遍历
	public static void pre_visit(TreeNode root) {

		System.out.println(root);
		if (root.getLeft() != null)
		{
			pre_visit(root.getLeft());
		}
		if (root.getRight() != null)
		{
			pre_visit(root.getRight());
		}

	}

	// 中序遍历
	public static void infix_visit(TreeNode root) {
		if (root != null)
		{

			if (root.getLeft() != null)
			{
				infix_visit(root.getLeft());
			}
			System.out.println(root);
			if (root.getRight() != null)
			{
				infix_visit(root.getRight());
			}
		}
	}

	// 后续遍历
	public static void post_visit(TreeNode root) {
		if (root != null)
		{

			if (root.getLeft() != null)
			{
				post_visit(root.getLeft());
			}
			if (root.getRight() != null)
			{
				post_visit(root.getRight());
			}
			System.out.println(root);
		}
	}

	// 前序查找
	public static TreeNode preFind(TreeNode root, int data) {
		if (root != null)
		{
			if (root.getData() == data)
			{
				return root;
			}
			TreeNode temp = null;
			if (root.getLeft() != null)
			{
				temp = preFind(root.getLeft(), data);
			}
			if (temp != null)
			{
				return temp;
			}
			if (root.getRight() != null)
			{
				temp = preFind(root.getRight(), data);
			}
			return temp;
		} else
		{
			return null;
		}

	}

	// 中序查找
	public static TreeNode infixFind(TreeNode root, int data) {
		if (root != null)
		{
			TreeNode temp = null;
			if (root.getLeft() != null)
			{
				temp = infixFind(root.getLeft(), data);
			}
			if (temp != null)
			{
				return temp;
			}
			if (root.getData() == data)
			{
				return root;
			}
			if (root.getRight() != null)
			{
				temp = infixFind(root.getRight(), data);
			}
			return temp;
		} else
		{
			return null;
		}

	}

	// 后序查找
	public static TreeNode postFind(TreeNode root, int data) {
		if (root != null)
		{
			TreeNode temp = null;
			if (root.getLeft() != null)
			{
				temp = postFind(root.getLeft(), data);
			}
			if (temp != null)
			{
				return temp;
			}
			if (root.getRight() != null)
			{
				temp = postFind(root.getRight(), data);
			}
			if (temp != null)
			{
				return temp;
			}
			if (root.getData() == data)
			{
				return root;
			}
			return temp;

		} else
		{
			return null;
		}

	}

	// 查找数据，按照二叉排序树的情况
	public TreeNode findByOrder(int key) {
		TreeNode temp = this.root;
		while (temp != null)
		{
			if (temp.getData() > key)
			{
				temp = temp.getLeft();
			} else if (temp.getData() < key)
			{
				temp = temp.getRight();
			} else
			{
				return temp;
			}
		}
		return null;
	}

	// 按照二叉排序树进行插入
	public boolean insertByOrder(int data) {
		TreeNode newNode = new TreeNode(data);
		if (root == null)
		{// 当前树为空树，没有任何节点
			root = newNode;
			return true;
		} else
		{
			TreeNode current = root;
			TreeNode parentNode = null;
			while (current != null)
			{
				parentNode = current;
				if (current.getData() > data)
				{// 当前值比插入值大，搜索左子节点
					current = current.getLeft();
					if (current == null)
					{// 左子节点为空，直接将新值插入到该节点
						parentNode.setLeft(newNode);
						;
						return true;
					}
				} else
				{
					current = current.getRight();
					if (current == null)
					{// 右子节点为空，直接将新值插入到该节点
						parentNode.setRight(newNode);
						return true;
					}
				}
			}
		}
		return false;
	}

	// 查找二叉树的最大值
	public TreeNode findMax() {
		TreeNode cur = this.root;
		TreeNode max = this.root;
		while (cur != null)
		{
			max = cur;
			cur = cur.getRight();
		}
		return max;
	}

	// 查找二叉树的最小值
	public TreeNode findMin() {
		TreeNode cur = this.root;
		TreeNode min = this.root;
		while (cur != null)
		{
			min = cur;
			cur = cur.getLeft();
		}
		return min;
	}

	// 求二叉树的高度
	public static int getTreeHigh(TreeNode root) {
		if (root == null)
		{
			return 0;
		} else
		{
			return Math.max(getTreeHigh(root.getLeft()), getTreeHigh(root.getRight())) + 1;
		}
	}

	// 返回二叉树节点的数量
	public static int getSize(TreeNode root) {
		if (root == null)
		{
			return 0;
		} else
		{
			return getSize(root.getLeft()) + getSize(root.getRight()) + 1;
		}
	}

	// 返回叶子节点的数量
	public static int getLeafSize(TreeNode root) {
		if (root == null)//如果根节点为空0
		{
			return 0;
		}
		if (root.getLeft() == null && root.getRight() == null)//如果是叶子节点不存在左右子树
		{
			return 1;
		}
		return getLeafSize(root.getLeft()) + getLeafSize(root.getRight());//左子树的叶子+右子树叶子的数量
	}

	// 销毁二叉树
	public static  void destoryTree(TreeNode root) {
		 while (root != null) {//当根节点不空
		        TreeNode left = root.getLeft();
		        if (left == null) {//如果左子树为空
		            TreeNode right = root.getRight();//获取右子树
		            root.setRight(null);//删除根节点
		            root = right;//根节点指向右子树
		        } else {
		            
		        	root.setRight(left.getLeft());//根节点的右儿子指向左子树
		            left.setRight(root);//左子树的右子树指向根节点
		            root = left;//根节点指向左子树
		        }
		    }
	}
	


	// 删除二叉树节点
	// root是根节点
	// key是待删除的节点的值
	// 返回根节点
	public static TreeNode deleteTreeNode(TreeNode root, int key) {
		if (root == null)
		{
			return null;
		}
		if (key < root.getData())
		{// 向左子树进行删除
			root.setLeft(deleteTreeNode(root.getLeft(), key));
			return root;
		}
		if (key > root.getData())
		{
			root.setRight(deleteTreeNode(root.getRight(), key));
			return root;
		}
		// 开始删除,如果是叶子节点
		if (root.getLeft() == null && root.getRight() == null)
		{
			root = null;
			return root;
		}
		// 待删除节点只有右子树
		if (root.getLeft() == null && root.getRight() != null)
		{
			root = root.getRight();
			return root;
		}
		// 只有左子树
		if (root.getRight() == null && root.getLeft() != null)
		{
			root = root.getLeft();
			return root;
		}
		// 有两个孩子
		if (root.getLeft() != null && root.getRight() != null)
		{
			// 挑选左子树中最大或者右子树中最小的，替换当前节点，再将替换节点置空
			int val = findMaxInLeftTree(root.getLeft());
			root.setData(val);
			root.setLeft(deleteTreeNode(root.getLeft(), key));
			return root;
		}

		return root;

	}

	// 找到左子树中最大的节点的值
	private static int findMaxInLeftTree(TreeNode left) {
		if (left == null)
		{
			return 0;
		}
		if (left.getRight() == null)
		{
			return left.getData();
		}
		if (left.getRight() == null && left.getLeft() == null)
		{
			return left.getData();
		}
		return findMaxInLeftTree(left.getRight());
	}

	// 层序打印二叉树
	public static void printTree(TreeNode root) {
		if (root == null)
		{
			return;
		}
		Deque<TreeNode> prioriDeque = new LinkedList<TreeNode>();
		prioriDeque.offerLast(root);
		while (prioriDeque.size() != 0)
		{
			TreeNode pNode = prioriDeque.getFirst();
			prioriDeque.pollFirst();
			System.out.printf(pNode.getData() + "" + " ");
			if (pNode.getLeft() != null)
			{
				prioriDeque.push(pNode.getLeft());
			}
			if (pNode.getRight() != null)
			{
				prioriDeque.push(pNode.getRight());
			}
		}

	}

	// 按层打印二叉树
	public static void printTreeBylayer(TreeNode root) {
		if (root == null)
		{
			return;
		}
		Queue<TreeNode> queue = new LinkedList<TreeNode>();
		int current;// 当前层
		int next;// 下一层的节点个数
		queue.offer(root);
		current = 1;
		next = 0;
		while (!queue.isEmpty())
		{
			TreeNode currentNode = queue.poll();
			System.out.printf("%-4d", currentNode.getData());
			current--;
			if (currentNode.getLeft() != null)
			{
				queue.offer(currentNode.getLeft());
				next++;
			}
			if (currentNode.getRight() != null)
			{
				queue.offer(currentNode.getRight());
				next++;
			}
			if (current == 0)
			{
				System.out.println();
				current = next;
				next = 0;
			}
		}

	}

	// 可视化打印
	public static void printBinaryTree(TreeNode root, int level) {
		if (root == null)
			return;
		printBinaryTree(root.getRight(), level + 1);
		if (level != 0)
		{
			for (int i = 0; i < level - 1; i++)
				System.out.print("|	");
			System.out.println("|-------" + root.getData());
		} else
			System.out.println(root.getData());
		printBinaryTree(root.getLeft(), level + 1);
	}

	// 二叉树的二分查找
	public static TreeNode binarySearch(TreeNode root, int key) {
		if (root == null)
		{
			return null;
		}
		if (root != null)
		{
			if (root.getData() == key)
			{
				return root;
			} else if (root.getData() > key)
			{
				return binarySearch(root.getLeft(), key);
			} else
			{
				return binarySearch(root.getRight(), key);
			}
		}
		return null;
	}

	// 二叉树的反转
	public static void mirror(TreeNode root) {
		if (root == null)
		{
			return;
		}
		if (root.getLeft() == null && root.getRight() == null)
		{
			return;
		}
		TreeNode temp = root.getLeft();
		root.setLeft(root.getRight());
		root.setRight(temp);
		mirror(root.getLeft());
		mirror(root.getRight());
	}

}