二叉树

定义

二叉树（binary tree）是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。

二叉树的递归定义为：

二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树 。

二叉树性质

性质1：二叉树的第i层上至多有2i-1（i≥1）个节点 。

性质2：深度为h的二叉树中至多含有2h-1个节点 。

性质3：若在任意一棵二叉树中，有n0个叶子节点，有n2个度为2的节点，则必有n0=n2+1。

性质4：具有n个节点的满二叉树深为log2n+1。

性质5：若对一棵有n个节点的完全二叉树进行顺序编号（1≤i≤n），那么，对于编号为i（i≥1）的节点：

当i=1时，该节点为根，它无双亲节点。

当i>1时，该节点的双亲节点的编号为i/2 。

若2i≤n，则有编号为2i的左节点，否则没有左节点。

若2i+1≤n，则有编号为2i+1的右节点，否则没有右节点 。

实现

顺序存储

public class ArrayBinaryTree<T> {
	private Object[] arr; // 用数组来存储树的所有节点
	private int deep; // 保存该树的深度
	private int size; // 数组大小
	private static final int DEFAULT_DEEP = 5; // 树的默认深度
 
	/**
	 * 以默认的深度来创建二叉树
	 */
	public ArrayBinaryTree() {
		this.deep = DEFAULT_DEEP;
		this.size = (int) Math.pow(2, deep) - 1; // Math.pow(2,deep)返回第一个参数的第二个参数次幂的值
		arr = new Object[size];
	}
 
	/**
	 * 以指定深度来创建二叉树
	 * @param deep
	 */
	public ArrayBinaryTree(int deep) {
		this.deep = deep;
		this.size = (int) Math.pow(2, deep) - 1;
		arr = new Object[size];
	}
 
	/**
	 * 以指定深度,指定根节点创建二叉树
	 * 
	 * @param deep 树的深度
	 * @param data 数据
	 */
	public ArrayBinaryTree(int deep, T data) {
		this.deep = deep;
		this.size = (int) Math.pow(2, deep) - 1; 
		arr = new Object[size];
		arr[0] = data; // 根节点
	}
 
	/**
	 * 为指定节点添加子节点。
	 * 
	 * @param index 需要添加子节点的父节点的索引
	 * @param data 新子节点的数据
	 * @param left 是否为左节点
	 */
	public void add(int index, T data, boolean left) {
		if (arr[index] == null) {
			throw new RuntimeException(index + "处节点为空，无法添加子节点");
		}
		if (2 * index + 1 >= size) {
			throw new IndexOutOfBoundsException();
		}
		if (left) { 
			arr[2 * index + 1] = data; // 添加左子节点
		} else {
			arr[2 * index + 2] = data; // 添加右子结点
		}
	}
 
	/**
	 * 判断二叉树是否为空
	 * @return
	 */
	public boolean isEmpty() {
		return arr[0] == null; // 根据根元素来判断二叉树是否为空
	}
 
	/**
	 * 返回根节点
	 * @return
	 */
	@SuppressWarnings("unchecked")
	public T getRoot() {
		return (T) arr[0];
	}
 
	/**
	 * 返回指定节点（非根节点）的父节点
	 * @param index 
	 * @return
	 */
	@SuppressWarnings("unchecked")
	public T getParent(int index) {
		return (T) arr[(index - 1) / 2];
	}
 
	/**
	 * 返回指定节点（非叶子）的左子节点，当左子节点不存在时返回null
	 * @param index
	 * @return
	 */
	@SuppressWarnings("unchecked")
	public T getLeft(int index) {
		if (2 * index + 1 >= size) {
			throw new RuntimeException("该节点为叶子节点，无子节点");
		}
		return (T) arr[index * 2 + 1];
	}
 
	/**
	 * 返回指定节点（非叶子）的右子节点，当右子节点不存在时返回null
	 * @param index
	 * @return
	 */
	@SuppressWarnings("unchecked")
	public T getRight(int index) {
		if (2 * index + 1 >= size) {
			throw new RuntimeException("该节点为叶子节点，无子节点");
		}
		return (T) arr[index * 2 + 2];
	}
 
	/**
	 * 返回该二叉树的深度。
	 * @param index
	 * @return
	 */
	public int getDeep(int index) {
		return deep;
	}
 
	/**
	 * 返回指定节点的位置。
	 * @param data
	 * @return
	 */
	public int index(T data) {
		for (int i = 0; i < size; i++) { // 该循环实际上就是按广度遍历来搜索每个节点
			if (arr[i].equals(data)) {
				return i;
			}
		}
		return -1;
	}
	
	/**
	 * 打印数组
	 */
	public String toString() {
		return Arrays.toString(arr);
	}
	
	/**
	 * 测试方法
	 * @param args
	 */
	public static void main(String[] args) {
		ArrayBinaryTree<String> binTree = new ArrayBinaryTree<String>(4, "根结点");
		binTree.add(0, "第二层右子节点", false); // 第一个参数为需要添加子节点的父节点的索引： 即根节点
		binTree.add(2, "第三层右子节点", false);
		binTree.add(6, "第四层右子节点", false);
		System.out.println(binTree);
	}
}

链式存储

class TreeNode {
	private int key = 0;
	private String data = null;
	private boolean isVisted = false;
	private TreeNode leftChild = null;
	private TreeNode rightChild = null;

	public TreeNode() {
	}

	public TreeNode(int key, String data) {
		this.key = key;
		this.data = data;
		this.leftChild = null;
		this.rightChild = null;
	}

	public int getKey() {
		return key;
	}

	public void setKey(int key) {
		this.key = key;
	}

	public String getData() {
		return data;
	}

	public void setData(String data) {
		this.data = data;

	}

	public TreeNode getLeftChild() {
		return leftChild;
	}

	public void setLeftChild(TreeNode leftChild) {
		this.leftChild = leftChild;
	}

	public TreeNode getRightChild() {
		return rightChild;
	}

	public void setRightChild(TreeNode rightChild) {
		this.rightChild = rightChild;
	}

	public boolean isVisted() {
		return isVisted;
	}

	public void setVisted(boolean isVisted) {
		this.isVisted = isVisted;
	}
}

public class BinaryTree {
	private TreeNode root = null;

	public BinaryTree() {
		root = new TreeNode(1, "rootNode(A)");
	}

	public void createBinTree(TreeNode root) {
		// 手动的创建(结构如图所示)
		TreeNode newNodeB = new TreeNode(2, "B");

		TreeNode newNodeC = new TreeNode(3, "C");

		TreeNode newNodeD = new TreeNode(4, "D");

		TreeNode newNodeE = new TreeNode(5, "E");

		TreeNode newNodeF = new TreeNode(6, "F");

		root.setLeftChild(newNodeB);

		root.setRightChild(newNodeC);

		root.getLeftChild().setLeftChild(newNodeD);

		root.getLeftChild().setRightChild(newNodeE);

		root.getRightChild().setRightChild(newNodeF);

	}

	public boolean IsEmpty() {
		// 判二叉树空否
		return root == null;
	}

	public int Height() {
		// 求树高度
		return Height(root);
	}

	public int Height(TreeNode subTree) {
		if (subTree == null)
			return 0; // 递归结束：空树高度为0
		else {
			int i = Height(subTree.getLeftChild());
			int j = Height(subTree.getRightChild());
			return (i < j) ? j + 1 : i + 1;
		}
	}

	public int Size() {
		// 求结点数

		return Size(root);

	}

	public int Size(TreeNode subTree) {
		if (subTree == null)

			return 0;

		else {
			return 1 + Size(subTree.getLeftChild())

					+ Size(subTree.getRightChild());

		}

	}

	public TreeNode Parent(TreeNode element) {
		// 返回双亲结点

		return (root == null || root == element) ? null : Parent(root, element);

	}

	public TreeNode Parent(TreeNode subTree, TreeNode element) {
		if (subTree == null)

			return null;

		if (subTree.getLeftChild() == element

				|| subTree.getRightChild() == element)

			// 找到, 返回父结点地址

			return subTree;

		TreeNode p;

		// 先在左子树中找，如果左子树中没有找到，才到右子树去找

		if ((p = Parent(subTree.getLeftChild(), element)) != null)

			// 递归在左子树中搜索

			return p;

		else

			// 递归在左子树中搜索

			return Parent(subTree.getRightChild(), element);

	}

	public TreeNode LeftChild(TreeNode element) {
		// 返回左子树

		return (element != null) ? element.getLeftChild() : null;

	}

	public TreeNode RightChild(TreeNode element) {
		// 返回右子树

		return (element != null) ? element.getRightChild() : null;

	}

	public TreeNode getRoot() {
		// 取得根结点

		return root;

	}

	public void destroy(TreeNode subTree) {
		// 私有函数: 删除根为subTree的子树

		if (subTree != null) {
			destroy(subTree.getLeftChild()); // 删除左子树

			destroy(subTree.getRightChild()); // 删除右子树

			// delete subTree; //删除根结点

			subTree = null;

		}

	}

	public void Traverse(TreeNode subTree) {
		System.out.println("key:" + subTree.getKey() + "--name:"

				+ subTree.getData());

		Traverse(subTree.getLeftChild());

		Traverse(subTree.getRightChild());

	}

	public void PreOrder(TreeNode subTree) {
		// 先根

		if (subTree != null) {
			visted(subTree);

			PreOrder(subTree.getLeftChild());

			PreOrder(subTree.getRightChild());

		}

	}

	public void InOrder(TreeNode subTree) {
		// 中根

		if (subTree != null) {
			InOrder(subTree.getLeftChild());

			visted(subTree);

			InOrder(subTree.getRightChild());

		}

	}

	public void PostOrder(TreeNode subTree) {
		// 后根

		if (subTree != null) {
			PostOrder(subTree.getLeftChild());

			PostOrder(subTree.getRightChild());

			visted(subTree);

		}

	}

	public void LevelOrder(TreeNode subTree) {
		// 水平遍边

	}

	public boolean Insert(TreeNode element) {
		// 插入

		return true;

	}

	public boolean Find(TreeNode element) {
		// 查找

		return true;

	}

	public void visted(TreeNode subTree) {
		subTree.setVisted(true);

		System.out.println("key:" + subTree.getKey() + "--name:"

				+ subTree.getData());

	}
	
	
	
	public static void main(String[] args) {
		BinaryTree bt = new BinaryTree();

		bt.createBinTree(bt.root);

		System.out.println("the size of the tree is " + bt.Size());

		System.out.println("the height of the tree is " + bt.Height());

		System.out.println("*******先根(前序)[ABDECF]遍历*****************");

		bt.PreOrder(bt.root);

		System.out.println("*******中根(中序)[DBEACF]遍历*****************");

		bt.InOrder(bt.root);

		System.out.println("*******后根(后序)[DEBFCA]遍历*****************");

		bt.PostOrder(bt.root);

	}
}