二叉树

二叉树概念总结
1、二叉树的递归定义
二叉树(Binary Tree)是个有限元素的集合，该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。
当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个结点。二叉树是有序的，即若将其左、右子树颠倒，就成为另一棵不同的二叉树。即使树中结点只有一棵子树，也要区分它是左子树还是右子树。(二叉树有五种形态)
2、二叉树的相关概念
(1)结点的度。结点所拥有的子树的个数称为该结点的度。
(2)叶结点。度为0 的结点称为叶结点，或者称为终端结点。
(3)分枝结点。度不为0 的结点称为分支结点，或者称为非终端结点。
(4)左孩子、右孩子、双亲。树中一个结点的子树的根结点称为这个结点的孩子。这个结点称为它孩子结点的双亲。具有同一个双亲的孩子结点互称为兄弟。
(5)路径、路径长度。如果一棵树的一串结点n1,n2,…,nk有如下关系：结点ni是ni+1的父结点(1≤i<k),就把n1,n2,…,nk称为一条由n1至nk的路径。这条路径的长度是k-1。
(6)祖先、子孙。在树中，如果有一条路径从结点M 到结点N，那么M 就称为N的祖先，而N 称为M 的孙。
(7)结点的层数。规定树的根结点的层数为1，其余结点的层数等于它的双亲结点的层数加1。
(8)树的深度。树中所有结点的最大层数称为树的深度。
(9)树的度。树中各结点度的最大值称为该树的度。
3、二叉树的主要性质
性质1： 在二叉树的第i层上至多有2的i-1次方个结点(i>=1)。
性质2： 深度为k的二叉树至多有2的k次方减1个结点(k>=1)。
性质3： 对任何一棵二叉树T，如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1。
性质4： 具有n个结点的完全二叉树的深度为|log2n|+1
性质5： 如果对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点i(1≤i≤n)有：
(1) 如果i=1,则结点i是二叉树的根,无双亲;如果i>1,则双亲PARENT(i)是结点i/2
(2) 如果2i>n,则结点i无左孩子(结点i为叶子结点);否则其左孩子LCHILD(i)是结点2i
(3) 如果2i+1>n,则结点i无右孩子;否则其右孩子RCHILD(i)是结点2i+1 

 

图片来源：http://sunlei.blog.51cto.com/525111/111063

 二叉树实现

 

import java.util.Queue;
import java.util.Vector;
import java.util.concurrent.ConcurrentLinkedQueue;

class BinaryTreeNode {
	int data;
	BinaryTreeNode leftchild;
	BinaryTreeNode rightchild;

	BinaryTreeNode(int t) {
		this.data = t;
		this.leftchild = null;
		this.rightchild = null;
	}

	BinaryTreeNode(int t, BinaryTreeNode leftchild, BinaryTreeNode rightchild) {
		this.data = t;
		this.leftchild = leftchild;
		this.rightchild = rightchild;
	}
}

public class BinaryTree {
	BinaryTreeNode root = null;

	public BinaryTree(int[] t) {
		creatBinaryTree(t);
	}

	/* 拷贝构造函数 */
	public BinaryTree(BinaryTree otherTree) {
		if (otherTree.root == null)
			this.root = null;
		else{			
			this.root=copy(otherTree.root);
			//this.root=otherTree.root;
		}
	}

	private BinaryTreeNode creatBinaryTree(int[] t) {
		int length = t.length;
		if (root == null) {
			root = new BinaryTreeNode(t[0]);
		}
		for (int i = 1; i < length; i++) {
			creat(root, t[i]);
		}
		return root;
	}

	// 构造二叉树
	private void creat(BinaryTreeNode root, int t) {
		if (t >= root.data) {
			if (root.rightchild == null) {
				root.rightchild = new BinaryTreeNode(t);
			} else {
				creat(root.rightchild, t);
			}
		} else {
			if (root.leftchild == null) {
				root.leftchild = new BinaryTreeNode(t);
			} else {
				creat(root.leftchild, t);
			}
		}
	}

	/* 遍历二叉树  前中后*/
	public void inIterator(BinaryTreeNode b) {
		if (b != null) {
			inIterator(b.leftchild);
			System.out.print(b.data + ",");
			inIterator(b.rightchild);
		}
	}
	public void levelOrderDisplay(BinaryTreeNode b){
		ConcurrentLinkedQueue<BinaryTreeNode> q = new ConcurrentLinkedQueue<BinaryTreeNode>();//创建链式队列对象
        if(b == null)return;
        BinaryTreeNode curr;
        q.add(b);                     //根结点入队列
        while(!q.isEmpty()){              //当队列非空时循环
            curr = (BinaryTreeNode)q.remove(); //出队列
            System.out.println(curr.data);      //访问该结点
            if(curr.leftchild != null)
                q.add(curr.leftchild); //左孩子结点入队列
            if(curr.rightchild != null)
                q.add(curr.rightchild);//右孩子结点入队列
        }

	}

	/* 树的高度 */
	public int treeHeight(BinaryTreeNode b) {
		if (b == null)
			return -1;
		else
			return (treeHeight(b.leftchild) >= treeHeight(b.rightchild) ? treeHeight(b.leftchild)
					: treeHeight(b.rightchild)) + 1;
	}

	/* 求总节点数 */
	public int treeNodes(BinaryTreeNode b) {
		if (b == null)
			return 0;
		else if (b.leftchild == null && b.rightchild == null)
			return 1;
		else
			return 1 + treeNodes(b.rightchild) + treeNodes(b.leftchild);
	}

	/* 求叶节点数 */
	public int treeLeavesNode(BinaryTreeNode b) {
		if (b == null)
			return 0;
		else if (b.leftchild == null && b.rightchild == null)
			return 1;
		else
			return treeLeavesNode(b.rightchild) + treeLeavesNode(b.leftchild);
	}

	/* 复制树 */
	public BinaryTreeNode copy(BinaryTreeNode b) {
		BinaryTreeNode newNode;
		if (b == null)
			return null;
		newNode=new BinaryTreeNode(b.data);
		newNode.leftchild = copy(b.leftchild);
		newNode.rightchild = copy(b.rightchild);
		//newNode = new BinaryTreeNode(b.data, newLeftChild, newRightChild);
		return newNode;
	}
	/*删除树*/
	public void delete(){
		 deleteTree(this.root);
		 System.out.println(this.root.rightchild.rightchild.rightchild==null);
	}
	public void deleteTree(BinaryTreeNode b){
		if(b!=null){
			deleteTree(b.leftchild);
			deleteTree(b.rightchild);
			b=null;
		}
	}
	/* 查找一个节点 */
	public boolean findNode(BinaryTreeNode b,int key){
		if(b==null)return false;
		if(b.data==key)return true;
		if(key>b.data)return findNode(b.rightchild,key);
		return findNode(b.leftchild,key);
	}
	public void insertNode(BinaryTreeNode b,int t){
		creat(b,t);
	}
	public static void main(String[] args) {
		int[] data = { 12, 11, 34, 45, 67, 38, 56, 43, 22, 8};
		System.out.println(data.length);
		BinaryTree btree = new BinaryTree(data);
		BinaryTreeNode r = btree.root;
		btree.inIterator(r);
		System.out.println();

		System.out.println("Height:" + btree.treeHeight(r));
		System.out.println("Nodes:" + btree.treeNodes(r));
		System.out.println("Leaves:" + btree.treeLeavesNode(r));
		
		BinaryTree copyTree=new BinaryTree(btree);	
		System.out.println("copyTree:");
		copyTree.insertNode(copyTree.root, 57);
		System.out.println("Height:" + copyTree.treeHeight(copyTree.root));
		System.out.println("Nodes:" + copyTree.treeNodes(copyTree.root));
		System.out.println("Leaves:" + copyTree.treeLeavesNode(copyTree.root));
		
		System.out.println("Btree  Height:" + btree.treeHeight(r));
		System.out.println("Nodes:" + btree.treeNodes(r));
		System.out.println("Leaves:" + btree.treeLeavesNode(r));
		
		System.out.println(copyTree.findNode(copyTree.root, 8));
		copyTree.inIterator(copyTree.root);
		
	/*	copyTree.delete();
		System.out.println(copyTree.root==null);
		System.out.println("deleteTree:");
		System.out.println("Height:" + copyTree.treeHeight(copyTree.root));
		System.out.println("Nodes:" + copyTree.treeNodes(copyTree.root));*/
		System.out.println("LevelOrder:");
		copyTree.levelOrderDisplay(copyTree.root);
		
		
	}

}