二叉樹詳解

1、二叉樹定義     

計算機中資料結構的一種，計算機中資料結構的一種每個節點最多有兩個子樹的樹結構。通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）。二叉樹常被用于實作二叉查找樹和二叉堆。

完全二叉樹：隻有最下面的兩層結點度能夠小于2，并且最下面一層的結點都集中在該層最左邊的若幹位置的二叉樹

滿二叉樹：除最後一層無任何子節點外，每一層上的所有結點都有兩個子結點二叉樹。

2、相關術語定義

樹的結點：包含一個資料元素及若幹指向子樹的分支；

孩子結點：結點的子樹的根稱為該結點的孩子；

雙親結點：B 結點是A 結點的孩子，則A結點是B 結點的雙親；

兄弟結點：同一雙親的孩子結點； 堂兄結點：同一層上結點；

祖先結點: 從根到該結點的所經分支上的所有結點子孫結點：以某結點為根的子樹中任一結點都稱為該結點的子孫

結點層：根結點的層定義為1；根的孩子為第二層結點，依此類推；

樹的深度：樹中最大的結點層

結點的度：結點子樹的個數

樹的度： 樹中最大的結點度。

葉子結點：也叫終端結點，是度為 0 的結點；

分枝結點：度不為0的結點；

3、二叉樹性質

(1) 在非空二叉樹中，第i層的結點總數不超過  , i>=1；

(2) 深度為h的二叉樹最多有  個結點(h>=1)，最少有h個結點；

(3) 對于任意一棵二叉樹，如果其葉結點數為N0，而度數為2的結點總數為N2，則N0=N2+1；

(4) 具有n個結點的完全二叉樹的深度為 

(5)有N個結點的完全二叉樹各結點如果用順序方式存儲，則結點之間有如下關系：

若I為結點編号則 如果I>1，則其父結點的編号為I/2；

如果2*I<=N，則其左兒子（即左子樹的根結點）的編号為2*I；若2*I>N，則無左兒子；

如果2*I+1<=N，則其右兒子的結點編号為2*I+1；若2*I+1>N，則無右兒子。

(6)給定N個節點，能構成h(N)種不同的二叉樹。

h(N)為卡特蘭數的第N項。h(n)=C(2*n，n)/(n+1)。

(7)設有i個枝點，I為所有枝點的道路長度總和，J為葉的道路長度總和J=I+2i

4、三種周遊順序

先序周遊

首先通路根，再先序周遊左（右）子樹，最後先序周遊右（左）子樹

中序周遊

首先中序周遊左（右）子樹，再通路根，最後中序周遊右（左）子樹

後序周遊

首先後序周遊左（右）子樹，再後序周遊右（左）子樹，最後通路根

5、根據其中兩種周遊方式重建二叉樹，java代碼實作

5.1 已知前序和中序周遊，用java重建二叉樹

方法一

package com.jason.algorithm;

import java.util.HashMap;

public class Solution {

	public static void main(String[] args) {
		int pre[] = { 1, 2, 4, 7, 3, 5, 6, 8 };
		int in[] = { 4, 7, 2, 1, 5, 3, 8, 6 };
		Solution solution = new Solution();
		solution.reConstructBinaryTree(pre, in);
	}

	public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
		if (pre == null || in == null) {
			return null;
		}
		HashMap<Integer, Integer> hashMap = new HashMap<Integer, Integer>();
		for (int i = 0; i < in.length; i++) {
			hashMap.put(in[i], i);
		}
		return preIn(pre, 0, pre.length - 1, in, 0, in.length - 1, hashMap);
	}

	// {1,2,4,7,3,5,6,8} pre 根左右
	// {4,7,2,1,5,3,8,6} in 左根右
	// {7,4,2,5,8,6,3,1} end

	//       1
	//     2    3
	//   4    5    6
	//    7      8
	// 根據前序和中序還原二叉樹
	public TreeNode preIn(int[] p, int pi, int pj, int[] n, int ni, int nj,
			HashMap<Integer, Integer> map) {
		if (pi > pj) {
			return null;
		}
		TreeNode head = new TreeNode(p[pi]);
		int index = map.get(p[pi]);
		// 根據前序周遊知道根節點，根據中序周遊知道根左邊的為左子樹，右邊的為右子樹
		head.left = preIn(p, pi + 1, pi + index - ni, n, ni, index - 1, map);
		head.right = preIn(p, pi + index - ni + 1, pj, n, index + 1, nj, map);
		System.out
				.println("head =" + (head != null ? head.val : " ")
						+ " head.left ="
						+ (head.left != null ? head.left.val : " ")
						+ " head.right ="
						+ (head.right != null ? head.right.val : " "));
		return head;
	}
}
           

方法二

public class BinaryTree {

	public static void main(String[] args) {
		int inorder[] = { 4, 7, 2, 1, 5, 3, 8, 6 };
		int preorder[] = { 1, 2, 4, 7, 3, 5, 6, 8 };
		BinaryTree binaryTree = new BinaryTree();
		// 利用前序和中序，建立二叉樹
		binaryTree.buildTree(preorder, inorder);
	}

	int pInorder;
	int pPreorder;

	public TreeNode buildTree(int[] preorder, int[] inorder, TreeNode node) {
		if (pPreorder > 7) {
			return null;
		}
		TreeNode head = new TreeNode(preorder[pPreorder++]);
		if (inorder[pInorder] != head.val) {
			head.right = buildTree(preorder, inorder, head);
		}
		pInorder++;
		if (node == null || inorder[pInorder] != node.val) {
			head.left = buildTree(preorder, inorder, node);
		}
		System.out
				.println("head =" + (head != null ? head.val : " ")
						+ " head.left ="
						+ (head.left != null ? head.left.val : " ")
						+ " head.right ="
						+ (head.right != null ? head.right.val : " "));
		return head;
	}

	public TreeNode buildTree(int[] preorder, int[] inorder) {
		return buildTree(preorder, inorder, null);
	}
}
           

TreeNode.java

package com.jason.algorithm;
 public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }
           

5.2 已知後序和中序遍，用java重建二叉樹

public class BinaryTree {

	public static void main(String[] args) {
		int inorder[] = { 4, 7, 2, 1, 5, 3, 8, 6 };
		int postorder[] = { 7, 4, 2, 5, 8, 6, 3, 1 };
		BinaryTree binaryTree = new BinaryTree();
		// 利用後序和中序，建立二叉樹
		binaryTree.buildTree(inorder, postorder);

	}

	int pInorder;
	int pPostorder;

	public TreeNode buildTree(int[] inorder, int[] postorder, TreeNode node) {
		if (pPostorder < 0) {
			return null;
		}
		TreeNode head = new TreeNode(postorder[pPostorder--]);
		if (inorder[pInorder] != head.val) {
			head.right = buildTree(inorder, postorder, head);
		}
		pInorder--;
		if (node == null || inorder[pInorder] != node.val) {
			head.left = buildTree(inorder, postorder, node);
		}
		System.out
				.println("head =" + (head != null ? head.val : " ")
						+ " head.left ="
						+ (head.left != null ? head.left.val : " ")
						+ " head.right ="
						+ (head.right != null ? head.right.val : " "));
		return head;
	}

	public TreeNode buildTree(int[] inorder, int[] postorder) {
		pInorder = inorder.length - 1;
		pPostorder = postorder.length - 1;
		return buildTree(inorder, postorder, null);
	}

}
           

5.3 已知前序和後序求中序周遊

如果隻有前序和後序周遊隻能确定樹的根，無法确定左子樹和右子樹，目前還沒想到求解方法。如果你有好的實作方法，歡迎留言一起學習，謝謝！