資料結構---二叉樹（手動建立及周遊）

二叉樹

1.定義：每個結點至多隻有兩棵子樹（二叉樹的度不大于2），二叉樹的子樹有左右之分，其次序不能任意颠倒。

2.性質：

性質一：在二叉樹的第i層至多有個2^(i-1)節點（i>=1）。

性質二：深度為k的二叉樹至多有2^k-1個節點(k>=1)。（可求得4的定理）

性質三：對任何一個二叉樹T，如果其葉子樹為n0,度為2的結點數為n2,則n0=n2+1。

性質四：具有n個結點的完全二叉樹的深度為（logn+1）向下取整。

性質五：如果對一棵有n個結點的完全二叉樹編号，則對任一結點i(1<=i<=n），有（1）如果i=1,則結點i是二叉樹的根，無雙親；如果i>1,則其雙親是結點i/2;(整數，注意在程式的/)。（2）如果2i>n,則結點i無左孩子（結點i為葉子節點）；否則其左孩子是結點2i。（3）如果2i+1>n，則結點i無右孩子，否則其右孩子是結點2i+1。

3.補充

（1）一棵深度為k且有2^k-1個結點的二叉樹稱為滿二叉樹。

（2）對滿二叉樹連續編号，約定編号從根開始，自上至下，自左至右。深度為k的，有n個結點的二叉樹，當其僅當其每一個結點都與深度為k的滿二叉樹中編号從1至n的結點一一對應時，稱之為完全二叉樹。

4.二叉樹的存儲結構

（1）順序存儲結構

用一組位址連續的存儲單元依次自上而下、自左至右存儲完全二叉樹上的結點元素，即将完全二叉樹上編号為i的結點元素存儲在如上定義的一維數組中下标為i-1的分量中。這種順序存儲結構僅适用于完全二叉樹。

（2）鍊式存儲結構

二叉樹的結點由一個資料元素和分别指向其左右子樹的兩個分支構成.則表示二又樹的連結清單中的結點至少包含3個域:資料域和左、右指針域。在含有理n個結點的二又連結清單中有n+1個空鍊域。

5.java代碼的實作—二叉樹的建立及周遊

package tree01;
/**
 * 二叉樹的建立以及三種周遊（前序，中序，後序）
 * @author Administrator
 *
 */
public class BinaryTreeTest {

	public static void main(String[] args) {
		BinaryTree bt=new BinaryTree();
		System.out.println("前序周遊為:");
		bt.preOrder();
		System.out.println();
		System.out.println("******************");
		System.out.println("中序周遊為:");
		bt.inOrder();
		System.out.println();
		System.out.println("******************");
		System.out.println("後序周遊為:");
		bt.postOrder();
	}
}
//二叉樹的建立
class BinaryTree{
	//二叉樹的根結點
	private Node root;
	//構造器
	public BinaryTree() {
		root=new Node("A");
		createBinaryTree();
	}
	
	public void createBinaryTree() {
		//手動生成結點對象
		Node node2=new Node("B");
		Node node3=new Node("C");
		Node node4=new Node("D");
		Node node5=new Node("E");
		Node node6=new Node("F");
		
		root.leftchild=node2;
		root.rightchild=node3;
		
		node2.leftchild=node4;
		node2.rightchild=node5;
		
		node3.leftchild=node6;
	}

	//前序周遊
	public void preOrder() {
		if(root!=null) {
			root.preOrder();
		}
		else {
			System.out.println("空");
		}
	}
	
	//中序周遊
		public void inOrder() {
			if(root!=null) {
				root.inOrder();
			}
			else {
				System.out.println("空");
			}
		}
		
		//後序周遊
		public void postOrder() {
			if(root!=null) {
				root.postOrder();
			}
			else {
				System.out.println("空");
			}
		}
}
//結點類
class Node{
	//存儲結點的資料
	String data;
	//結點左孩子的位址
	Node leftchild;
	//結點右孩子的位址
	Node rightchild;
	//構造器，每生成一個節點對象，傳遞一個值
	public Node(String data) {
		this.data = data;
	}
	//前序周遊----根->左->右(該方法為非靜态方法，一旦調用，必是該類的對象調用)
	public void preOrder() {
		System.out.print(this.data+"->");
		if(this.leftchild!=null) {
			this.leftchild.preOrder();
		}
		if(this.rightchild!=null) {
			this.rightchild.preOrder();
		}
	}
	//中序周遊----左->根->右(該方法為非靜态方法，一旦調用，必是該類的對象調用)
		public void inOrder() {		
			if(this.leftchild!=null) {
				this.leftchild.inOrder();
			}
			System.out.print(this.data+"->");
			if(this.rightchild!=null) {
				this.rightchild.inOrder();
			}
		}
		//後序周遊----左->右->根(該方法為非靜态方法，一旦調用，必是該類的對象調用)
		public void postOrder() {
			if(this.leftchild!=null) {
				this.leftchild.postOrder();
			}
			if(this.rightchild!=null) {
				this.rightchild.postOrder();
			}
			System.out.print(this.data+"->");
		}
}

           

結果如下：

如有不足，望大家指教。