目錄：
一、樹(shù)
1. 概述
2. 一些基本術(shù)語(yǔ)
二乱凿、二叉樹(shù)
1. 概述
2. 重要特性
三、二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)
1. 順序存儲(chǔ)
2. 鏈?zhǔn)酱鎯?chǔ)
四、二叉樹(shù)的遍歷
1. 由遍歷序列確定二叉樹(shù)
2. 根據(jù)遍歷序列估計(jì)二叉樹(shù)
3. 遍歷和建樹(shù)代碼
一绑蔫、樹(shù)
1. 概述
與線性表表示的一一對(duì)應(yīng)的線性關(guān)系不同，樹(shù)表示的是更為復(fù)雜的數(shù)據(jù)元素之間的非線性關(guān)系泵额。
直觀來(lái)看配深，樹(shù)是以分支關(guān)系定義的層次結(jié)構(gòu)，是 一對(duì)多 的關(guān)系
樹(shù)的定義：樹(shù) (Tree) 是 n( n>=0 ) 個(gè)結(jié)點(diǎn)的有限集合
有且僅有一個(gè) 根結(jié)點(diǎn) (Root)
當(dāng)n>1的時(shí)嫁盲，其余結(jié)點(diǎn)可分為 m( m>0 ) 個(gè)互不相交的有限集T1篓叶，T2，..., Tm，其中每一個(gè)集合本身又是一棵樹(shù)澜共，并且稱之為根的子樹(shù)向叉。
樹(shù)的定義本身是一個(gè)遞歸定義，即在樹(shù)的定義中又用到樹(shù)的概念
2. 一些基本術(shù)語(yǔ)
- 樹(shù)的結(jié)點(diǎn)：包含一個(gè)數(shù)據(jù)元素和若干指向其子樹(shù)的分支
- 度（degree）：結(jié)點(diǎn)擁有的子樹(shù)的數(shù)目
- 度為** 0 **的結(jié)點(diǎn)稱為 葉子嗦董，或 終端結(jié)點(diǎn)母谎。度不為 0 的結(jié)點(diǎn)稱為 非終端結(jié)點(diǎn) 或 分支節(jié)點(diǎn)
- 結(jié)點(diǎn)的子樹(shù)的根，稱為該結(jié)點(diǎn)的 孩子（child）京革，相應(yīng)的該結(jié)點(diǎn)稱為孩子的 雙親（parent）
- 同一個(gè)雙親的孩子之間互稱兄弟（sibling）
- 結(jié)點(diǎn)的 祖先 是從根到該結(jié)點(diǎn)所經(jīng)分支上所有的結(jié)點(diǎn)奇唤。
- 以某結(jié)點(diǎn)為根的子樹(shù)中的任意一結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的 子孫
- 結(jié)點(diǎn)的 層次（Level）從根開(kāi)始定義，根為第一層匹摇，根的孩子為第二層廊勃，以此類(lèi)推
- 樹(shù)中結(jié)點(diǎn)的最大層次稱為樹(shù)的 深度（depth）或 高度
二、二叉樹(shù)
1. 概述
-
定義：對(duì)一般的樹(shù)加了約束：
- 每個(gè)結(jié)點(diǎn)最多兩棵子樹(shù)，即二叉樹(shù)中不存在 度大于2 的結(jié)點(diǎn)
- 子樹(shù)有 左右次序 之分
-
有 5 種形態(tài)：
二叉樹(shù)的形態(tài)
- **滿二叉樹(shù) **和 完全二叉樹(shù)（對(duì)滿二叉樹(shù)最底層伏尼，從右至左刪除結(jié)點(diǎn)）
2. 重要特性
- 二叉樹(shù)，在第 i 層至多有 2i-1 個(gè)結(jié)點(diǎn)
- 深度為 k 的二叉樹(shù)至多有 **2k-1 **個(gè)結(jié)點(diǎn)
- 高度（或深度）為 K 的完全二叉樹(shù)至少有 2k-2 個(gè) 葉子結(jié)點(diǎn)
- 非空二叉樹(shù)的 葉子結(jié)點(diǎn)數(shù) 等于度為 2 的結(jié)點(diǎn)數(shù)加 1芭碍，即：
n0 = n2 + 1
完全二叉樹(shù)的 n1 只能是 0 或者 1
一顆度為 m 的二叉樹(shù)杉女，度為 1 的結(jié)點(diǎn)為 n1晌砾，度為 2 的結(jié)點(diǎn)為 n2，... ...，度為 m 的結(jié)點(diǎn)數(shù)為 nm，則葉子結(jié)點(diǎn)數(shù)：n0 = 1 + n2 + 2n3 +...+ (m-1)nm
具有 n 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，深度為 log2n + 1
編號(hào)性質(zhì)：n 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)（其深度為 log2n + 1）漱病，對(duì)各結(jié)點(diǎn)從上到下漓穿，從左到右依次編號(hào)（1~n）則：若 i 是某結(jié)點(diǎn) a 的編號(hào)：
如果 i 不等于 1，則 a 的雙親結(jié)點(diǎn)的編號(hào)為： **? i/2 ? **
如果 2i ≤ n, 則 a 的左孩子編號(hào)為 2i；如果** 2i > n, 則 a 無(wú)左孩子**；
如果** 2i + 1 ≤ n, 則 a 的右孩子編號(hào)為 2i + 1；如果 2i + 1> n**, 則 a 無(wú)右孩子画切；
三丧枪、二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)
1. 順序存儲(chǔ)
- 用 數(shù)組 來(lái)存儲(chǔ)數(shù)據(jù)元素
- 從存儲(chǔ)的角度來(lái)看，這種順序存儲(chǔ)結(jié)構(gòu)庞萍，僅適用于 完全二叉樹(shù)
因?yàn)樵谧顗牡那闆r下拧烦，一個(gè)深度為 k 且只有 k 個(gè)結(jié)點(diǎn)的單支樹(shù)( 樹(shù)中不存在度為 2 的結(jié)點(diǎn) )，卻需要長(zhǎng)度為 2k-1 的一維數(shù)組钝计。
2. 鏈?zhǔn)酱鎯?chǔ)
- 以 鏈表 的形式恋博，存儲(chǔ)數(shù)據(jù)元素以及數(shù)據(jù)元素之間的關(guān)系。
四私恬、二叉樹(shù)的遍歷
1. 由遍歷序列確定二叉樹(shù)
- 由 先序和中序债沮，可以確定
- 由 后序和中序，可以確定（但是注意后序最后一個(gè)為根本鸣，下一個(gè)是右子樹(shù)根）
- 由 層次和中序疫衩，可以確定
2. 根據(jù)遍歷序列估計(jì)二叉樹(shù)
前序 遍歷序列 和 后序 遍歷序列 相同 的樹(shù)：只有根結(jié)點(diǎn)
前序 遍歷 和 中序 遍歷 相同 的二叉樹(shù)：所有結(jié)點(diǎn)沒(méi)有左子樹(shù)（右單分支樹(shù)
中序 遍歷 和 后序 遍歷 相同 的二叉樹(shù)：所有結(jié)點(diǎn)沒(méi)有右子樹(shù)（左單分支樹(shù)）
前序遍歷 和 后序 遍歷 相反 的二叉樹(shù)：沒(méi)有左子樹(shù)或者沒(méi)有右子樹(shù)（只有一個(gè)葉子結(jié)點(diǎn)）<u>**高度等于其結(jié)點(diǎn)數(shù) **</u>
前序 遍歷 和 中序 遍歷 相反 的二叉樹(shù)：所有結(jié)點(diǎn)沒(méi)有右子樹(shù)（左單分支樹(shù)）
中序 遍歷 和 后序 遍歷 相反 的二叉樹(shù)：所有結(jié)點(diǎn)沒(méi)有左子樹(shù)（右單分支樹(shù)）
3. 遍歷和建樹(shù)代碼
- 二叉樹(shù)的建樹(shù)
- 深度優(yōu)先遍歷（先序，中序和后序）
- 廣度優(yōu)先遍歷（先序荣德，后序）
/* BitTree.java */
package com.java.tree;
import java.util.LinkedList;
import java.util.Queue;
/**
* Created by Jaco.Young.
* 2018-06-13 18:26
*/
public class BitTree {
//代表由先序和中序唯一確定的樹(shù)的根結(jié)點(diǎn)
private TreeNode root;
/**
* 提供給外部調(diào)用的方法
* 字符數(shù)組pre表示先序遍歷序列闷煤，mid表示中序遍歷序列
*/
public void build(char[] pre, char[] mid){
//將創(chuàng)建樹(shù)的根結(jié)點(diǎn)賦值給 root
root = buildTree(pre,0, pre.length-1, mid, 0, mid.length-1);
}
/**
* 前提條件，樹(shù)中不存在重復(fù)元素
* 由先序遍歷序列和中序遍歷序列涮瞻，構(gòu)造二叉樹(shù)的方法
* 我們建樹(shù)的過(guò)程總是將序列不斷地分割成左子樹(shù)鲤拿、右子樹(shù)
* lPre、rPre和lMid署咽、rMid近顷，分別就表示要對(duì)先序和中序的哪一部分進(jìn)行建樹(shù)
*/
private TreeNode buildTree(char[] pre, int lPre, int rPre, char[] mid, int lMid, int rMid){
//在先序遍歷序列中，找到當(dāng)前這棵樹(shù)的根結(jié)點(diǎn)
char root = pre[lPre];
//在中序遍歷序列中宁否，根據(jù)先序中的根結(jié)點(diǎn)來(lái)查找在中序中的位置
int rootIndex = getRootIndex(mid, lMid, rMid, root);
//如果沒(méi)有找到窒升，說(shuō)明所給的參數(shù)異常
if(rootIndex == -1){
throw new IllegalArgumentException("Illegal Argument!");
}
//計(jì)算當(dāng)前這棵樹(shù)，左右子樹(shù)的個(gè)數(shù)
//整個(gè)中序序列：[左子樹(shù)(lMid) root(rootIndex) 右子樹(shù)(rMid)]
//左子樹(shù)[lMid,rootIndex-1]
int lNum = rootIndex - lMid; //rootIndex-1 -lMid + 1
//右子樹(shù)[rootIndex+1,rMid]
int rNum = rMid - rootIndex; //rMid - (rootIndex + 1) + 1
//開(kāi)始構(gòu)建當(dāng)前根結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)
//先構(gòu)建左子樹(shù)
TreeNode lchild; //作為左子樹(shù)的根結(jié)點(diǎn)
//以當(dāng)前結(jié)點(diǎn)為根的樹(shù)慕匠，沒(méi)有左子樹(shù)
if(lNum == 0){
lchild = null;
}else{
//當(dāng)前這個(gè)樹(shù)的左子樹(shù)异剥，仍然是一棵樹(shù)，遞歸構(gòu)造這棵樹(shù)的左子樹(shù)
//設(shè)x為當(dāng)前樹(shù)先序中左子樹(shù)最后一個(gè)元素的下標(biāo)絮重，則：x - (lpre + 1) = lNum
//得：x = lPre + lNum
lchild = buildTree(pre, lPre + 1, lPre+lNum, mid, lMid, rootIndex - 1);
}
//構(gòu)建右子樹(shù)
TreeNode rchild;
if(rNum == 0){
rchild = null;
}else{
//當(dāng)前結(jié)點(diǎn)的右子樹(shù)冤寿，仍然包含很多節(jié)點(diǎn)歹苦，需要遞歸的構(gòu)造其右子樹(shù)
rchild = buildTree(pre, lPre + lNum + 1, rPre, mid, rootIndex + 1, rMid);
}
//構(gòu)造完整的二叉樹(shù)
return new TreeNode(root,lchild,rchild);
}
//在中序遍歷序列中，根據(jù)先序中的根結(jié)點(diǎn)來(lái)查找在中序中的位置
private int getRootIndex(char[] mid, int lMid, int rMid, char root) {
for(int i = lMid; i <= rMid; i++){
if(mid[i] == root){
return i;
}
}
return -1;
}
//二叉樹(shù)每一個(gè)結(jié)點(diǎn)的結(jié)構(gòu)
private class TreeNode{
//結(jié)點(diǎn)中存儲(chǔ)的數(shù)據(jù)
char item;
//指向左孩子結(jié)點(diǎn)
TreeNode lChild;
//指向右孩子結(jié)點(diǎn)
TreeNode rChild;
//構(gòu)造方法,完成初始化
public TreeNode(char item, TreeNode lChild, TreeNode rChild){
this.item = item;
this.lChild = lChild;
this.rChild = rChild;
}
}
//提供三個(gè)讓外界調(diào)用的方法
public void preTraverse() {
preOrder(root);
}
public void midTraverse() {
midOrder(root);
}
public void postTraverse() {
postOrder(root);
}
//先序遍歷 DLR
private void preOrder(TreeNode root) {
if( root != null) {
//先訪問(wèn)根節(jié)點(diǎn)
System.out.print(root.item + " ");
//遞歸訪問(wèn)左子樹(shù)
preOrder(root.lChild);
//遞歸訪問(wèn)右子樹(shù)
preOrder(root.rChild);
}
}
//中序遍歷 LDR
private void midOrder(TreeNode root) {
if(root != null) {
//遞歸訪問(wèn)左子樹(shù)
midOrder(root.lChild);
//訪問(wèn)根
System.out.print(root.item + " ");
//遞歸訪問(wèn)右子樹(shù)
midOrder(root.rChild);
}
}
//后續(xù)遍歷
// LRD
private void postOrder(TreeNode root) {
if(root != null) {
//遞歸訪問(wèn)左子樹(shù)
postOrder(root.lChild);
//遞歸訪問(wèn)右子樹(shù)
postOrder(root.rChild);
//訪問(wèn)根
System.out.print(root.item + " ");
}
}
//廣度優(yōu)先遍歷 BFS
public void BFS() {
//創(chuàng)建一個(gè)能放TreeNode對(duì)象的隊(duì)列
Queue<TreeNode> queue = new LinkedList<>();
//將樹(shù)的根節(jié)點(diǎn)入隊(duì)列
queue.add(root);
//循環(huán)執(zhí)行廣度優(yōu)先遍歷
while(!queue.isEmpty()) {
//將當(dāng)前的隊(duì)頭元素出隊(duì)列
TreeNode node = queue.remove();
//訪問(wèn)出隊(duì)列的節(jié)點(diǎn)
System.out.print(node.item + " ");
//出隊(duì)列的節(jié)點(diǎn)是否有左孩子督怜，有則將其左孩子入隊(duì)列
if(node.lChild != null) {
//有左孩子
queue.add(node.lChild);
}
//出隊(duì)列的節(jié)點(diǎn)是否有右孩子殴瘦，如果右，將其右孩子如隊(duì)列
if(node.rChild != null) {
queue.add(node.rChild);
}
}
}
}
/* Test.java*/
package com.java.tree;
/**
* 測(cè)試類(lèi)
* Created by Jaco.Young.
* 2018-06-13 20:16
*/
public class Test {
public static void main(String[] args){
//構(gòu)造先序遍歷序列和中序遍歷序列
char[] pre = {'A','B','E', 'K', 'L', 'F', 'D', 'H', 'J'};
char[] mid = {'K', 'E', 'L', 'B', 'F', 'A', 'H', 'D', 'J'};
BitTree bitTree = new BitTree();
//根據(jù)遍歷序列構(gòu)建二叉樹(shù)
bitTree.build(pre, mid);
//先序遍歷
bitTree.preTraverse();
System.out.println();
//中序遍歷
bitTree.midTraverse();
System.out.println();
//后序遍歷
bitTree.postTraverse();
System.out.println();
//廣度優(yōu)先遍歷
bitTree.BFS();
}
}
運(yùn)行結(jié)果為：
A B E K L F D H J
K E L B F A H D J
K L E F B H J D A
A B D E F H J K L
