二叉樹(shù)概念總結(jié)
1、二叉樹(shù)的遞歸定義
二叉樹(shù)(Binary Tree)是個(gè)有限元素的集合，該集合或者為空、或者由一個(gè)稱為根(root)的元素及兩個(gè)不相交的、被分別稱為左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。
當(dāng)集合為空時(shí)，稱該二叉樹(shù)為空二叉樹(shù)。在二叉樹(shù)中，一個(gè)元素也稱作一個(gè)結(jié)點(diǎn)。二叉樹(shù)是有序的，即若將其左、右子樹(shù)顛倒，就成為另一棵不同的二叉樹(shù)。即使樹(shù)中結(jié)點(diǎn)只有一棵子樹(shù)，也要區(qū)分它是左子樹(shù)還是右子樹(shù)。(二叉樹(shù)有五種形態(tài))
2、二叉樹(shù)的相關(guān)概念
(1)結(jié)點(diǎn)的度。結(jié)點(diǎn)所擁有的子樹(shù)的個(gè)數(shù)稱為該結(jié)點(diǎn)的度。
(2)葉結(jié)點(diǎn)。度為0 的結(jié)點(diǎn)稱為葉結(jié)點(diǎn)，或者稱為終端結(jié)點(diǎn)。
(3)分枝結(jié)點(diǎn)。度不為0 的結(jié)點(diǎn)稱為分支結(jié)點(diǎn)，或者稱為非終端結(jié)點(diǎn)。
(4)左孩子、右孩子、雙親。樹(shù)中一個(gè)結(jié)點(diǎn)的子樹(shù)的根結(jié)點(diǎn)稱為這個(gè)結(jié)點(diǎn)的孩子。這個(gè)結(jié)點(diǎn)稱為它孩子結(jié)點(diǎn)的雙親。具有同一個(gè)雙親的孩子結(jié)點(diǎn)互稱為兄弟。
(5)路徑、路徑長(zhǎng)度。如果一棵樹(shù)的一串結(jié)點(diǎn)n1,n2,…,nk有如下關(guān)系：結(jié)點(diǎn)ni是ni+1的父結(jié)點(diǎn)(1≤i<k),就把n1,n2,…,nk稱為一條由n1至nk的路徑。這條路徑的長(zhǎng)度是k-1。
(6)祖先、子孫。在樹(shù)中，如果有一條路徑從結(jié)點(diǎn)M 到結(jié)點(diǎn)N，那么M 就稱為N的祖先，而N 稱為M 的孫。
(7)結(jié)點(diǎn)的層數(shù)。規(guī)定樹(shù)的根結(jié)點(diǎn)的層數(shù)為1，其余結(jié)點(diǎn)的層數(shù)等于它的雙親結(jié)點(diǎn)的層數(shù)加1。
(8)樹(shù)的深度。樹(shù)中所有結(jié)點(diǎn)的最大層數(shù)稱為樹(shù)的深度。
(9)樹(shù)的度。樹(shù)中各結(jié)點(diǎn)度的最大值稱為該樹(shù)的度。
3、二叉樹(shù)的主要性質(zhì)
性質(zhì)1： 在二叉樹(shù)的第i層上至多有2的i-1次方個(gè)結(jié)點(diǎn)(i>=1)。
性質(zhì)2： 深度為k的二叉樹(shù)至多有2的k次方減1個(gè)結(jié)點(diǎn)(k>=1)。
性質(zhì)3： 對(duì)任何一棵二叉樹(shù)T，如果其終端結(jié)點(diǎn)數(shù)為n0,度為2的結(jié)點(diǎn)數(shù)為n2,則n0=n2+1。
性質(zhì)4： 具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為|log2n|+1
性質(zhì)5： 如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的結(jié)點(diǎn)按層序編號(hào)，則對(duì)任一結(jié)點(diǎn)i(1≤i≤n)有：
(1) 如果i=1,則結(jié)點(diǎn)i是二叉樹(shù)的根,無(wú)雙親;如果i>1,則雙親PARENT(i)是結(jié)點(diǎn)i/2
(2) 如果2i>n,則結(jié)點(diǎn)i無(wú)左孩子(結(jié)點(diǎn)i為葉子結(jié)點(diǎn));否則其左孩子LCHILD(i)是結(jié)點(diǎn)2i
(3) 如果2i+1>n,則結(jié)點(diǎn)i無(wú)右孩子;否則其右孩子RCHILD(i)是結(jié)點(diǎn)2i+1?

?

圖片來(lái)源： http://sunlei.blog.51cto.com/525111/111063

?二叉樹(shù)實(shí)現(xiàn)

?

    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);
	}

	/* 拷貝構(gòu)造函數(shù) */
	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;
	}

	// 構(gòu)造二叉樹(shù)
	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);
			}
		}
	}

	/* 遍歷二叉樹(shù)  前中后*/
	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>();//創(chuàng)建鏈?zhǔn)疥?duì)列對(duì)象
        if(b == null)return;
        BinaryTreeNode curr;
        q.add(b);                     //根結(jié)點(diǎn)入隊(duì)列
        while(!q.isEmpty()){              //當(dāng)隊(duì)列非空時(shí)循環(huán)
            curr = (BinaryTreeNode)q.remove(); //出隊(duì)列
            System.out.println(curr.data);      //訪問(wèn)該結(jié)點(diǎn)
            if(curr.leftchild != null)
                q.add(curr.leftchild); //左孩子結(jié)點(diǎn)入隊(duì)列
            if(curr.rightchild != null)
                q.add(curr.rightchild);//右孩子結(jié)點(diǎn)入隊(duì)列
        }

	}

	/* 樹(shù)的高度 */
	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;
	}

	/* 求總節(jié)點(diǎn)數(shù) */
	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);
	}

	/* 求葉節(jié)點(diǎn)數(shù) */
	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);
	}

	/* 復(fù)制樹(shù) */
	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;
	}
	/*刪除樹(shù)*/
	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;
		}
	}
	/* 查找一個(gè)節(jié)點(diǎn) */
	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);
		
		
	}

}

  

?

二叉樹(shù)