樹形結(jié)構(gòu)是一種非常重要的非線性的數(shù)據(jù)結(jié)構(gòu)研侣。樹結(jié)構(gòu)與線性結(jié)構(gòu)不同之處：線性結(jié)構(gòu)中任意一個(gè)元素最多只有一個(gè)后繼元素谱邪，而樹形結(jié)構(gòu)中每個(gè)元素可以有多個(gè)后繼；線性結(jié)構(gòu)和樹形結(jié)構(gòu)中每個(gè)元素最多只有一個(gè)前驅(qū)元素庶诡。這篇文章為本人原創(chuàng)惦银，謝絕轉(zhuǎn)載。具體的內(nèi)容目錄如下：
一末誓、樹的屬性
二扯俱、二叉樹
三、二叉樹與樹喇澡、森林的轉(zhuǎn)換
四迅栅、二叉排序樹
五、平衡二叉樹
一晴玖、樹的屬性
樹又一個(gè)特定的稱為根的節(jié)點(diǎn)读存，這個(gè)節(jié)點(diǎn)無(wú)前驅(qū)節(jié)點(diǎn)。樹可以用遞歸的方式來定義呕屎，也就是說樹是由若干個(gè)子樹構(gòu)成让簿。如下圖所示，A是根節(jié)點(diǎn)秀睛，沒有前驅(qū)節(jié)點(diǎn)尔当，B、C是A的子節(jié)點(diǎn)琅催，也是一棵樹居凶。這里要簡(jiǎn)單說下樹的一些術(shù)語(yǔ)虫给。
1.節(jié)點(diǎn)：表示樹中的一個(gè)數(shù)據(jù)元素藤抡。如下圖中侠碧，A、B缠黍、C、D、E乍炉、F责球、G、H贸典、I都是是節(jié)點(diǎn)视卢。
2.孩子節(jié)點(diǎn)：表示樹中節(jié)點(diǎn)的直接后驅(qū)節(jié)點(diǎn)。如下圖中廊驼，A的孩子節(jié)點(diǎn)為B据过、C。
3.雙親節(jié)點(diǎn)：表示樹中節(jié)點(diǎn)的直接前驅(qū)節(jié)點(diǎn)妒挎，如下圖中绳锅，D、E酝掩、F的雙親節(jié)點(diǎn)是B鳞芙。
4.兄弟節(jié)點(diǎn)：表示具有相同雙親節(jié)點(diǎn)的節(jié)點(diǎn)。如下圖中期虾，D原朝、E、F是兄弟節(jié)點(diǎn)镶苞。
5.祖先節(jié)點(diǎn)：表示從根節(jié)點(diǎn)到該節(jié)點(diǎn)的雙親節(jié)點(diǎn)都是祖先節(jié)點(diǎn)喳坠。如下圖中，I的祖先節(jié)點(diǎn)為A宾尚、B丙笋、E。
6.子孫節(jié)點(diǎn)：表示該節(jié)點(diǎn)下所有孩子節(jié)點(diǎn)煌贴，包括子節(jié)點(diǎn)的子節(jié)點(diǎn)御板。如下圖中，A的子孫節(jié)點(diǎn)為B牛郑、C怠肋、D、E淹朋、F笙各、G钉答、H、I杈抢。
7.節(jié)點(diǎn)的度：該節(jié)點(diǎn)的子樹的個(gè)數(shù)数尿，可以理解為該節(jié)點(diǎn)后代的代數(shù)。如下圖中惶楼，A的度為3右蹦，D的度為0。
8.葉子節(jié)點(diǎn)：度為0的節(jié)點(diǎn)歼捐，也就是沒有后驅(qū)節(jié)點(diǎn)何陆。如下圖中，D豹储、H贷盲、I、G都是葉子節(jié)點(diǎn)剥扣。
9.分支節(jié)點(diǎn)：度不為0的節(jié)點(diǎn)巩剖，可以理解為樹枝，有后驅(qū)節(jié)點(diǎn)朦乏。B球及、C、E都是分支節(jié)點(diǎn)呻疹。
10.樹的層數(shù)：樹的根節(jié)點(diǎn)所在的層樹為1吃引，其他節(jié)點(diǎn)的層數(shù)等于他的雙親節(jié)點(diǎn)的層數(shù)+1。如下圖中刽锤，A樹的層數(shù)為4镊尺，B樹的層數(shù)為3。
11.樹的深度：表示整棵樹的最大層數(shù)并思，也叫高度庐氮。如下圖中，深度為4宋彼。
12.森林：零棵樹或有限棵樹互不相交的樹的集合叫森林弄砍。如下圖中，將A節(jié)點(diǎn)去掉输涕，B樹與C樹可以構(gòu)成森林音婶。
13.有序樹與無(wú)序樹：樹中節(jié)點(diǎn)的子樹從左到右是有次序的稱為有序樹，否則為無(wú)序樹莱坎。
二衣式、二叉樹
二叉樹是一顆每個(gè)節(jié)點(diǎn)有不超過兩個(gè)孩子節(jié)點(diǎn)的樹。兩顆子樹有左右之分，稱為左子樹和右子樹碴卧，左子樹和右子樹都可以為空弱卡，如果不為空時(shí)，子樹也是一顆二叉樹住册。二叉樹也有一種遞歸的概念婶博。二叉樹有五種基本形態(tài)
1.空樹：根節(jié)點(diǎn)為空的二叉樹
2.只有根節(jié)點(diǎn)：只有根節(jié)點(diǎn)，根節(jié)點(diǎn)沒有左右子樹
3.只有左子樹：只有左子樹界弧，沒有右子樹
4.只有右子樹：只有右子樹凡蜻，沒有左子樹
5.有左右子樹：該節(jié)點(diǎn)同時(shí)有左右子樹
二叉樹的性質(zhì)
1.二叉樹第i(i>=1)層上最多有2^(i-1)個(gè)節(jié)點(diǎn)搭综。
2.深度為k(k>=1)的二叉樹最陡有2^k-1個(gè)節(jié)點(diǎn)垢箕。
3.滿二叉樹：深度為k并且含有2k-1個(gè)節(jié)點(diǎn)的二叉樹《医恚可以理解為条获，樹枝節(jié)點(diǎn)都有左右子樹。通俗地講蒋歌，在不增加樹的深度的前提下帅掘，無(wú)法再多添加一個(gè)節(jié)點(diǎn)的二叉樹稱為滿二叉樹。
4.完全二叉樹：深度為k堂油，有n個(gè)節(jié)點(diǎn)的二叉樹修档，當(dāng)且僅當(dāng)每個(gè)節(jié)點(diǎn)的編號(hào)與相應(yīng)滿二叉樹節(jié)點(diǎn)順序編號(hào)從1～n相對(duì)應(yīng)時(shí)，則稱為完全二叉樹府框。通俗地講吱窝，完全二叉樹相當(dāng)于刪除滿二叉樹的最底層最右邊的連續(xù)若干個(gè)節(jié)點(diǎn)。
二叉樹的存儲(chǔ)結(jié)構(gòu)
1.順序存儲(chǔ)結(jié)構(gòu)
將二叉樹中所有節(jié)點(diǎn)元素存儲(chǔ)到一維數(shù)組中迫靖，這是最簡(jiǎn)單的順序存儲(chǔ)結(jié)構(gòu)院峡。設(shè)一維數(shù)組list，list[0]空置不用系宜，從第一個(gè)開始照激，每個(gè)數(shù)組元素存儲(chǔ)樹的每一個(gè)節(jié)點(diǎn)元素。按照完全二叉樹編號(hào)從上到下盹牧，從左到右的順序?qū)⒚總€(gè)節(jié)點(diǎn)元素存儲(chǔ)到數(shù)組中俩垃。如下圖所示，第i個(gè)節(jié)點(diǎn)的雙親節(jié)點(diǎn)為i/2汰寓，左右孩子節(jié)點(diǎn)分別為2i口柳、2i+1。
如果二叉樹是一顆單邊二叉樹(只有左子樹或只有右子樹)踩寇，對(duì)于每個(gè)二叉樹而言啄清，有插入新元素的可以，所以需要保留存儲(chǔ)空間。如下圖中辣卒，紅色表示可以插入新元素掷贾，用虛線連接。
下圖表示單邊二叉樹的順序存儲(chǔ)結(jié)構(gòu)荣茫，本來只有四個(gè)元素想帅，卻要分配8個(gè)存儲(chǔ)空間。如果一顆深度為k的單邊二叉樹啡莉，至少要
2^k個(gè)存儲(chǔ)空間港准，則有2^k-k個(gè)空間為空，這樣造成資源浪費(fèi)咧欣。這種存儲(chǔ)結(jié)構(gòu)適合于滿二叉樹和完全二叉樹浅缸，一般的二叉樹很少采用這種存儲(chǔ)結(jié)構(gòu)。
2.鏈表存儲(chǔ)結(jié)構(gòu)
二叉樹的鏈表結(jié)構(gòu)有常見的兩種：二叉鏈表魄咕、三叉鏈表衩椒。
- 二叉鏈表：包含一個(gè)數(shù)據(jù)元素，左子樹指針哮兰，右子樹指針毛萌。可以很容易找到該節(jié)點(diǎn)的子孫節(jié)點(diǎn)喝滞，但是不容易找到其雙親節(jié)點(diǎn)阁将。
-
三叉鏈表：包含一個(gè)數(shù)據(jù)元素，左子樹指針右遭，右子樹指針做盅，還有一個(gè)雙親節(jié)點(diǎn)指針，方便找出其雙親節(jié)點(diǎn)狸演。
存儲(chǔ)結(jié)構(gòu)
一般樹的存儲(chǔ)結(jié)構(gòu)
1.雙親表示法：存儲(chǔ)父節(jié)點(diǎn)的序號(hào)言蛇，方便于查找父節(jié)點(diǎn)。下圖中的左邊為一般的樹形結(jié)構(gòu)宵距，右邊為存儲(chǔ)結(jié)構(gòu)腊尚。
2.孩子表示法：存儲(chǔ)孩子節(jié)點(diǎn)的指針，方便于查找孩子節(jié)點(diǎn)满哪。下圖中的左邊為一般的樹形結(jié)構(gòu)婿斥，右邊為存儲(chǔ)結(jié)構(gòu)。
3.雙親孩子表示法：結(jié)合上述兩種方式哨鸭∶袼蓿可方便查找雙親和孩子節(jié)點(diǎn)。
4.二叉樹表示法：將一個(gè)普通樹轉(zhuǎn)換為二叉樹像鸡，具體規(guī)則如下：
-左指針域指向該節(jié)點(diǎn)的第一個(gè)子節(jié)點(diǎn)活鹰；
-右指針域指向該節(jié)點(diǎn)的第一個(gè)兄弟節(jié)點(diǎn)；
二叉樹的遍歷
遍歷二叉樹就是以一定的順序訪問每個(gè)節(jié)點(diǎn)，并且每個(gè)節(jié)點(diǎn)只能被訪問一次志群。
假設(shè)有一顆二叉樹有7個(gè)節(jié)點(diǎn)着绷，為了方便理解，為每個(gè)沒有同時(shí)存在左右子樹的節(jié)點(diǎn)補(bǔ)充一個(gè)空的節(jié)點(diǎn)锌云。如下圖所示荠医，圖中的紅色表示補(bǔ)充的空的節(jié)點(diǎn)，外圍虛線表示搜索路徑桑涎。
按照從左到右的方式彬向，可以分為三種遍歷方式
注意：遞歸算法實(shí)現(xiàn)簡(jiǎn)單，但效率較低攻冷，這是因?yàn)橄到y(tǒng)需要維護(hù)一個(gè)工作棧以保證遞歸方法的正確執(zhí)行娃胆，所有在實(shí)際使用中推薦非遞歸方式。
1.先序遍歷：先訪問根節(jié)點(diǎn)讲衫，再訪問左子樹缕棵，再訪問右子樹。如上圖中涉兽，第一次搜索經(jīng)過的節(jié)點(diǎn)為A、B篙程、D枷畏、G、C虱饿、E拥诡、F。具體的算法如下：
/**
* 二叉樹的先序遍歷(非遞歸)
* @param root 根節(jié)點(diǎn)
*/
public static void fristOrderTraversalByStack(WLTreeNode root) {
Stack<WLTreeNode> stack = new Stack<>();
WLTreeNode node = root;
//將所有左孩子壓棧
while (node != null || stack.size() > 0) {
if(node != null) {
printTreeNode(node);
stack.push(node);
node = node.getLeft();
}else {
node = stack.pop();
node = node.getRight();
}
}
}
/**
* 二叉樹的先序遍歷
* @param root 根節(jié)點(diǎn)
*/
public static void firstOrderTraversal(WLTreeNode root) {
if(root != null) {
printTreeNode(root);
if(root.getLeft() != null) {
firstOrderTraversal(root.getLeft());
}
if(root.getRight() != null) {
firstOrderTraversal(root.getRight());
}
}
}
2.中序遍歷：先訪問左子樹氮发，再訪問根節(jié)點(diǎn)渴肉，再訪問右子樹。如上圖中爽冕，第二次搜索經(jīng)過的節(jié)點(diǎn)為G仇祭、D、B颈畸、A乌奇、E、C眯娱、F礁苗。具體的算法如下：
/**
* 二叉樹的中序遍歷(非遞歸)
* @param root 根節(jié)點(diǎn)
*/
public static void inOrderTraversalByStack(WLTreeNode root) {
Stack<WLTreeNode> stack = new Stack<>();
WLTreeNode node = root;
while (node != null || stack.size() > 0) {
if(node != null) {
stack.push(node);
node = node.getLeft();
}else {
node = stack.pop();
printTreeNode(node);
node = node.getRight();
}
}
}
/**
* 二叉樹的中序遍歷
* @param root 根節(jié)點(diǎn)
*/
public static void inOrderTraversal(WLTreeNode root) {
if(root != null) {
if(root.getLeft() != null) {
inOrderTraversal(root.getLeft());
}
printTreeNode(root);
if(root.getRight() != null) {
inOrderTraversal(root.getRight());
}
}
}
3.后序遍歷：先訪問左子樹，在訪問右子樹徙缴，在訪問根節(jié)點(diǎn)试伙。如上圖中，第三次搜索經(jīng)過的節(jié)點(diǎn)為G、D疏叨、B吱抚、E、F考廉、C秘豹、A。具體的算法如下：
/**
* 二叉樹的后序遍歷(非遞歸)
* @param root 根節(jié)點(diǎn)
*/
public static void postOrderTraversalByStack(WLTreeNode root) {
Stack<WLTreeNode> stack = new Stack<>();
Stack<WLTreeNode> output = new Stack<>();
WLTreeNode node = root;
while (node != null || stack.size() > 0) {
if(node != null) {
stack.push(node);
output.push(node);
node = node.getRight();
}else {
node = stack.pop();
node = node.getLeft();
}
}
while (output.size() > 0) {
printTreeNode(output.pop());
}
}
/**
* 二叉樹的后序遍歷
* @param root 根節(jié)點(diǎn)
*/
public static void postOrderTraversal(WLTreeNode root) {
if(root != null) {
if(root.getLeft() != null) {
postOrderTraversal(root.getLeft());
}
if(root.getRight() != null) {
postOrderTraversal(root.getRight());
}
printTreeNode(root);
}
}
二叉樹的其他操作
/**
* 按層遍歷二叉樹
* 1.將二叉樹根節(jié)點(diǎn)入隊(duì)列
* 2.將隊(duì)頭節(jié)點(diǎn)出隊(duì)列昌粤，并判斷此節(jié)點(diǎn)算法有左右孩子既绕，如果有，則將其左右孩子入隊(duì)列
* @param root 根節(jié)點(diǎn)
*/
public static void levelTraversal(WLTreeNode root) {
if(root != null) {
List<WLTreeNode> list = new ArrayList<>();
//1.根節(jié)點(diǎn)入隊(duì)列
list.add(root);
while (list.size() > 0) {
//取出隊(duì)頭節(jié)點(diǎn)
WLTreeNode node = list.get(0);
printTreeNode(node);
list.remove(0);
//判斷是否有左右孩子
if(node.getLeft() != null) {
list.add(node.getLeft());
}
if(node.getRight() != null) {
list.add(node.getRight());
}
}
}
}
/**
* 按層遍歷二叉樹
* @param root 根節(jié)點(diǎn)
* @param index 第幾個(gè)節(jié)點(diǎn)涮坐，從0開始
* @return 節(jié)點(diǎn)
*/
public static WLTreeNode findNodeByIndex(WLTreeNode root,int index) {
if(root != null && index >= 0) {
List<WLTreeNode> list = new ArrayList<>();
//根節(jié)點(diǎn)入隊(duì)列
list.add(root);
while (list.size() > 0) {
//取出隊(duì)頭節(jié)點(diǎn)
WLTreeNode node = list.get(0);
//==0凄贩，則找到
if(index == 0) {
return node;
}
//彈出隊(duì)頭節(jié)點(diǎn)
list.remove(0);
index --;
//如果該節(jié)點(diǎn)有左右節(jié)點(diǎn)，則入隊(duì)列
if(node.getLeft() != null) {
list.add(node.getLeft());
}
if(node.getRight() != null) {
list.add(node.getRight());
}
}
}
return null;
}
/**
* 二叉樹的深度
* @param root 根節(jié)點(diǎn)
* @return 深度值 根節(jié)點(diǎn)深度為1
*/
public static int depthOfBinaryTree(WLTreeNode root) {
if(root != null) {
if(root.getLeft() == null && root.getRight() == null) {
return 1;
}
int leftDepth = depthOfBinaryTree(root.getLeft());
int rightDepth = depthOfBinaryTree(root.getRight());
return Math.max(leftDepth, rightDepth)+1;
}
return 0;
}
/**
* 二叉樹的寬度是指二叉樹各層結(jié)點(diǎn)個(gè)數(shù)的最大值
* @param root 根節(jié)點(diǎn)
* @return 深度值 根節(jié)點(diǎn)深度為1
*/
public static int widthOfBinaryTree(WLTreeNode root) {
if(root != null) {
List<WLTreeNode>list = new ArrayList<>();
list.add(root);
int maxWidth = 1;//已有根節(jié)點(diǎn)
int curWidth = 0;
while (list.size() > 0) {
curWidth = list.size();
if(maxWidth < curWidth) {
maxWidth = curWidth;
}
for (int i = 0; i < curWidth; i++) {
WLTreeNode node = list.get(0);
list.remove(0);
if(node.getLeft() != null) {
list.add(node.getLeft());
}
if(node.getRight() != null) {
list.add(node.getRight());
}
}
}
return maxWidth;
}
return 0;
}
/**
* 二叉樹的節(jié)點(diǎn)個(gè)數(shù)
* @param root 根節(jié)點(diǎn)
* @return 全部節(jié)點(diǎn)個(gè)數(shù)
*/
public static int numberOfBinaryTree(WLTreeNode root) {
if(root != null) {
int count = 0;
List<WLTreeNode>list = new ArrayList<>();
list.add(root);
while (list.size() > 0) {
WLTreeNode node = list.get(0);
list.remove(0);
if(node.getLeft() != null) {
list.add(node.getLeft());
}
if(node.getRight() != null) {
list.add(node.getRight());
}
count++;
}
return count;
}
return 0;
}
/**
* 二叉樹某一層的全部節(jié)點(diǎn)個(gè)數(shù)
* @param root 根節(jié)點(diǎn)
* @return 節(jié)點(diǎn)個(gè)數(shù)
*/
public static int numberOfNodeOnLevel(WLTreeNode root,int level) {
if(root != null && level >= 0) {
//根節(jié)點(diǎn)只有一個(gè)節(jié)點(diǎn)
if(level == 1) {
return 1;
}
return numberOfNodeOnLevel(root.getLeft(), level-1) + numberOfNodeOnLevel(root.getRight(), level-1);
}
return 0;
}
/**
* 二叉樹的葉子節(jié)點(diǎn)個(gè)數(shù)
* @param root 根節(jié)點(diǎn)
* @return
*/
public static int numberOfLeafNode(WLTreeNode root) {
if(root != null) {
if(root.getLeft() == null && root.getRight() == null) {
return 1;
}
return numberOfLeafNode(root.getLeft()) + numberOfLeafNode(root.getRight());
}
return 0;
}
/**
* 二叉樹中某個(gè)節(jié)點(diǎn)到根節(jié)點(diǎn)的路徑
* 1.將根節(jié)點(diǎn)壓入棧袱讹，再?gòu)淖笞訕渲胁檎移Ｔ绻麤]找到，再?gòu)挠易訕渲胁檎医莸瘢绻麤]找到椒丧，則彈出根節(jié)點(diǎn)，再遍歷棧中上一個(gè)節(jié)點(diǎn)
* 2.如果找到救巷，則棧中存放的節(jié)點(diǎn)就是路徑經(jīng)過的節(jié)點(diǎn)
* @param root 根節(jié)點(diǎn)
* @param node 起點(diǎn)節(jié)點(diǎn)
* @return 路徑數(shù)組
*/
public static List<WLTreeNode> pathOfTreeNode(WLTreeNode root,WLTreeNode node){
List<WLTreeNode>list = new ArrayList<>();
boolean isFound = isFoundTreeNode(root, node, list);
System.out.println("isFound = "+isFound);
return list;
}
/**
* 查找二叉樹中是否包含該節(jié)點(diǎn)
* @param root 根節(jié)點(diǎn)
* @param node 待查找節(jié)點(diǎn)
* @param list 路徑數(shù)組
* @return 是否找到
*/
public static boolean isFoundTreeNode(WLTreeNode root,WLTreeNode node,List<WLTreeNode>list) {
if(root == null || node == null) {
return false;
}
//判斷是否為當(dāng)前節(jié)點(diǎn)
if(root.getValue() == node.getValue()) {
return true;
}
System.out.println("find root value = "+root.getValue());
//將根節(jié)點(diǎn)壓入棧
list.add(root);
//先從左子樹中查找
boolean isFound = isFoundTreeNode(root.getLeft(),node,list);
if(!isFound) {
//左子樹中沒找到壶熏，則從右子樹中查找
isFound = isFoundTreeNode(root.getRight(),node,list);
}
//左右子樹中都沒找到，則彈出此根節(jié)點(diǎn)
if(!isFound) {
list.remove(list.size()-1);
}
return isFound;
}
/**
* 是否為滿二叉樹
* 除了葉子節(jié)點(diǎn)浦译，每個(gè)節(jié)點(diǎn)都有左右子節(jié)點(diǎn)
* @param root 根節(jié)點(diǎn)
* @return
*/
public static boolean isFullBinaryTree(WLTreeNode root) {
if(root != null) {
int depth = depthOfBinaryTree(root);
int nodeCount = numberOfBinaryTree(root);
if(nodeCount == Math.pow(2, depth)-1) {
return true;
}
}
return false;
}
/**
* 是否為平衡二叉樹
* 定義：一顆空樹或左右子樹的高度差的絕對(duì)值不超過1棒假，并且左右子樹都是一個(gè)平衡二叉樹
* @param root 根節(jié)點(diǎn)
* @return
*/
public static boolean isAVLBinaryTree(WLTreeNode root) {
//一顆空樹
if(root == null) {
avlHeight = 0;
return false;
}
//只有根節(jié)點(diǎn)
if(root.getLeft() == null && root.getRight() == null) {
avlHeight = 1;
return true;
}
boolean isLeft = isAVLBinaryTree(root.getLeft());
int leftHeight = avlHeight;
boolean isRight = isAVLBinaryTree(root.getRight());
int rightHeight = avlHeight;
avlHeight = Math.max(leftHeight, rightHeight);
if(isLeft && isRight && Math.abs(leftHeight-rightHeight) <= 1) {
return true;
}
return false;
}
/**
* 反轉(zhuǎn)二叉樹 非遞歸
* @param root
* @return
*/
public static WLTreeNode invertBinaryTreeByQueue(WLTreeNode root) {
if(root == null) {
return root;
}
List<WLTreeNode>list = new ArrayList<>();
list.add(root);
while (list.size() > 0) {
WLTreeNode node = list.get(0);
list.remove(0);
WLTreeNode tmpNode = node.getLeft();
node.setLeft(node.getRight());
node.setRight(tmpNode);
if(node.left != null) {
list.add(node.getLeft());
}
if(node.right != null) {
list.add(node.getRight());
}
}
return root;
}
/**
* 打印樹形結(jié)構(gòu)
*/
private static void printTreeNode(WLTreeNode node) {
System.out.println(node.getValue());
}
三、二叉樹與樹精盅、森林的轉(zhuǎn)換
1.樹轉(zhuǎn)換為二叉樹
(1)加線：在樹中所有相鄰的兄弟節(jié)點(diǎn)之間加一條線帽哑。
(2)抹線：對(duì)樹中的每個(gè)節(jié)點(diǎn)，只保留與第一個(gè)孩子節(jié)點(diǎn)之間的連線叹俏，刪除與其他孩子節(jié)點(diǎn)之間的連線妻枕。
(3)調(diào)整：以每個(gè)節(jié)點(diǎn)為軸心，將其右側(cè)所有節(jié)點(diǎn)按順時(shí)針轉(zhuǎn)動(dòng)45度她肯，使之稱為一顆二叉樹佳头。
2.二叉樹轉(zhuǎn)換為樹
樹與二叉樹之間的轉(zhuǎn)換是可逆的，將二叉樹轉(zhuǎn)換為樹也分為三步：
(1)加線：若某個(gè)節(jié)點(diǎn)是其雙親節(jié)點(diǎn)的左孩子晴氨，則把該節(jié)點(diǎn)的所有右子孫節(jié)點(diǎn)都與該節(jié)點(diǎn)的雙親節(jié)點(diǎn)用線連起來康嘉。
(2)抹線：刪除二叉樹中所有雙親節(jié)點(diǎn)與右孩子節(jié)點(diǎn)之間的連線。
(3)調(diào)整：把虛線改為實(shí)線籽前，把節(jié)點(diǎn)按層次排列亭珍。
3.森林轉(zhuǎn)換為二叉樹
森林是樹的集合敷钾，樹可以和二叉樹相互轉(zhuǎn)換，森林也可以肄梨，只不過要麻煩一點(diǎn)點(diǎn)阻荒。
(1)轉(zhuǎn)換：將森林中的每棵子樹轉(zhuǎn)換為二叉樹，給每棵子樹編號(hào)為1,2,3,......n棵二叉樹众羡。
(2)加線：在所有的二叉樹的根節(jié)點(diǎn)之間加一條線侨赡，也就是從第二棵二叉樹開始，將第i+1棵二叉樹作為第i棵樹的右子樹粱侣。
4.二叉樹轉(zhuǎn)換為森林
(1)抹線：從二叉樹的根節(jié)點(diǎn)開始搜索所有的右子孫節(jié)點(diǎn)羊壹，將其之間的連線抹去，這樣就得到包含若干棵二叉樹的森林齐婴。
(2)還原：將每棵二叉樹還原為一般的樹油猫。
四、二叉排序樹
二叉排序樹柠偶，顧名思義就是用二叉樹實(shí)現(xiàn)排序功能情妖，是一種特殊的二叉樹，需要滿足一下性質(zhì)
1.若左子樹不為空诱担，則左子樹中所有節(jié)點(diǎn)的數(shù)據(jù)值均小于根節(jié)點(diǎn)的數(shù)據(jù)值毡证。
2.若右子樹不為空，則右子樹中所有節(jié)點(diǎn)的數(shù)據(jù)值均大于根接待你的數(shù)據(jù)值该肴。
3.左子樹和右子樹也分別是二叉排序樹情竹。
面試的時(shí)候可能會(huì)遇到這樣的問題，給出一組數(shù)字匀哄，按照順序插入，畫出二叉排序樹的結(jié)構(gòu)圖雏蛮。下面舉個(gè)例子涎嚼，畫出10,20,16,6,4,8,30,55這組數(shù)字的二叉排序樹的結(jié)構(gòu)。這里要說明一下插入的原理挑秉，插入的元素比上一個(gè)元素大法梯，則插入在元素的右邊，否則插入在元素的左邊犀概。
二叉排序樹的插入
二叉排序樹是動(dòng)態(tài)查找立哑，動(dòng)態(tài)插入的樹表，不是一次完成的姻灶。在查找的過程中铛绰，當(dāng)書中不存在待插入的值時(shí)才進(jìn)行插入操作。新插入的節(jié)點(diǎn)一定是葉子節(jié)點(diǎn)产喉。
/**
* 二叉排序樹的插入節(jié)點(diǎn)操作
* @param root 樹的根節(jié)點(diǎn)
* @param value 插入值
* @return 插入的新節(jié)點(diǎn)
*/
public static WLTreeNode binaryTreeInsertion(WLTreeNode root,int value) {
//創(chuàng)建新節(jié)點(diǎn)
WLTreeNode node = new WLTreeNode(null, null, value);
if(root == null) {
return node;
}
WLTreeNode pNode = root;
WLTreeNode fNode = null;//找出新節(jié)點(diǎn)的直接父節(jié)點(diǎn)
//遍歷二叉樹捂掰，查找新節(jié)點(diǎn)添加位置
while (pNode != null) {
fNode = pNode;
if (value < pNode.getValue()) {
pNode = pNode.getLeft();
}else if(value > pNode.getValue()){
pNode = pNode.getRight();
}else {
break;
}
}
if(value < fNode.getValue()) {
fNode.setLeft(node);
}else if(value > fNode.getValue()){
fNode.setRight(node);
}
return node;
}
二叉排序樹的查找
二叉排序樹的查找就是遍歷每個(gè)節(jié)點(diǎn)敢会，比較關(guān)鍵字與每個(gè)節(jié)點(diǎn)的值是否相等，如果相等这嚣，則查找成功鸥昏；否則在根節(jié)點(diǎn)的左子樹或右子樹中繼續(xù)查找，這是一個(gè)遞歸的過程姐帚。
(1)如果二叉排序樹為空吏垮，則查找失敗，返回空指針罐旗。
(2)如果查找關(guān)鍵字和根節(jié)點(diǎn)值相等膳汪，則查找成功，返回根節(jié)點(diǎn)指針尤莺。
(3)如果查找關(guān)鍵字小于根節(jié)點(diǎn)值旅敷，則在根節(jié)點(diǎn)的左子樹中查找。
(4)如果查找關(guān)鍵字大于根節(jié)點(diǎn)值颤霎，則在根節(jié)點(diǎn)的右子樹中查找媳谁。
/**
* 二叉排序樹的查找
* @param root 根節(jié)點(diǎn)
* @param x 關(guān)鍵字
* @return 關(guān)鍵字節(jié)點(diǎn)
*/
public static WLTreeNode binaryTreeSearch(WLTreeNode root,int x) {
if(root == null) {
return null;
}else if (x == root.getValue()) {
return root;
}else if (x < root.getValue()) {
return binaryTreeSearch(root.getLeft(), x);
}else {
return binaryTreeSearch(root.getRight(), x);
}
}
/**
* 二叉排序樹的查找 非遞歸
* @param root 根節(jié)點(diǎn)
* @param x 關(guān)鍵字
* @return 關(guān)鍵字節(jié)點(diǎn)
*/
public static WLTreeNode binaryTreeSearchByStack(WLTreeNode root,int x) {
if(root != null) {
Stack<WLTreeNode> stack = new Stack<>();
while (root != null) {
if(root.getValue() == x) {
return root;
}else if (root.getValue() > x) {
stack.push(root);
root = root.getLeft();
}else {
stack.push(root);
root = root.getRight();
}
}
}
return null;
}
二叉排序樹的刪除
二叉排序樹的刪除操作是在查找的基礎(chǔ)上進(jìn)行的，也就是在二叉排序樹中查找是否存在待刪除關(guān)鍵字的節(jié)點(diǎn)友酱，如果存在晴音，則刪除。二叉排序樹的刪除節(jié)點(diǎn)比較麻煩缔杉，可以分為一下四種情況：
(1)待刪除節(jié)點(diǎn)為葉子節(jié)點(diǎn)锤躁，則直接刪除
(2)待刪除節(jié)點(diǎn)只有左子樹，沒有右子樹或详，則用左子樹代替該節(jié)點(diǎn)
(3)待刪除節(jié)點(diǎn)只有右子樹系羞，沒有左子樹，則用右子樹代替該節(jié)點(diǎn)
(4)待刪除節(jié)點(diǎn)有左右子樹霸琴，找出右子樹中最小值的節(jié)點(diǎn)椒振，將最小值節(jié)點(diǎn)替換該節(jié)點(diǎn)，
具體的實(shí)現(xiàn)方法如下：
/**
* 二叉排序樹刪除節(jié)點(diǎn)操作
* 1.如果節(jié)點(diǎn)為葉子節(jié)點(diǎn)梧乘，直接刪除
* 2.如果節(jié)點(diǎn)只有左子樹澎迎，無(wú)右子樹，則用左子樹代替該節(jié)點(diǎn)
* 3.如果節(jié)點(diǎn)只有右子樹选调，無(wú)左子樹夹供，則用右子樹代替該節(jié)點(diǎn)
* 4.如果節(jié)點(diǎn)有左、右子樹仁堪，則找出其右子樹最小值節(jié)點(diǎn)代替該節(jié)點(diǎn)
* @param root 樹的根節(jié)點(diǎn)
* @param value 刪除值
* @return 刪除后的樹
*/
public static WLTreeNode binaryTreeDelete(WLTreeNode root,int value) {
if(root != null) {
WLTreeNode pNode = root;//待刪除節(jié)點(diǎn)
WLTreeNode fNode = null;//fNode為pNode的直接父節(jié)點(diǎn)
//找出pNode節(jié)點(diǎn)和pNode的直接父節(jié)點(diǎn)
while(pNode != null) {
if(value == pNode.getValue()) {
break;
}else if (value < pNode.getValue()) {
fNode = pNode;
pNode = pNode.getLeft();
}else {
fNode = pNode;
pNode = pNode.getRight();
}
}
//沒有該節(jié)點(diǎn)
if(pNode == null) {
return root;
}
if(pNode.getLeft() == null && pNode.getRight() == null) {//待刪除節(jié)點(diǎn)為葉子節(jié)點(diǎn)
//判斷是否為根節(jié)點(diǎn)
if(fNode != null) {
if (pNode == fNode.getLeft()) {
fNode.setLeft(pNode.getLeft());
}else if (pNode == fNode.getRight()) {
fNode.setRight(pNode.getRight());
}
fNode = null;
}else {
root = null;
}
pNode = null;
}else if (pNode.getLeft() != null && pNode.getRight() == null) {//待刪除節(jié)點(diǎn)只有左子樹哮洽，沒有右子樹
if(fNode != null) {
if(pNode == fNode.getLeft()) {
fNode.setLeft(pNode.getLeft());
}else if (pNode == fNode.getRight()) {
fNode.setRight(pNode.getLeft());
}
fNode = null;
}else {
root = root.getLeft();
}
pNode = null;
}else if (pNode.getLeft() == null && pNode.getRight() != null) {//待刪除節(jié)點(diǎn)只有右子樹，沒有左子樹
if(fNode != null) {
if(pNode == fNode.getLeft()) {
fNode.setLeft(pNode.getRight());
}else if (pNode == fNode.getRight()) {
fNode.setRight(pNode.getRight());
}
}else {
root = root.getRight();
}
}else {//待刪除節(jié)點(diǎn)同時(shí)有左右子樹
//1.查找待刪除節(jié)點(diǎn)的直接后驅(qū)節(jié)點(diǎn)枝笨，也就是該節(jié)點(diǎn)右子樹中最小值節(jié)點(diǎn)qNode
//2.將qNode節(jié)點(diǎn)替換待刪除節(jié)點(diǎn)
WLTreeNode sNode = pNode.getRight();//直接后驅(qū)節(jié)點(diǎn)
WLTreeNode qNode = sNode;//直接后驅(qū)節(jié)點(diǎn)的直接父節(jié)點(diǎn)
while (sNode.getLeft() != null) {
qNode = sNode;
sNode = sNode.getLeft();
}
if(sNode == qNode) {
fNode.setRight(qNode);
qNode.setLeft(pNode.getLeft());
}else {
qNode.setLeft(sNode.getLeft());
fNode.setRight(sNode);
sNode.setLeft(pNode.getLeft());
sNode.setRight(pNode.getRight());
}
pNode = null;
qNode = null;
fNode = null;
sNode = null;
}
return root;
}
return root;
}
五袁铐、平衡二叉樹
在說平衡二叉樹之前揭蜒，需要先講講二叉排序樹的查找的時(shí)間復(fù)雜度。對(duì)于含有n個(gè)節(jié)點(diǎn)的二叉排序樹剔桨，查找關(guān)鍵字節(jié)點(diǎn)是從根節(jié)點(diǎn)開始屉更，所需要比較次數(shù)就是該節(jié)點(diǎn)所在的層數(shù)。例如下圖中洒缀，分別查找關(guān)鍵字10瑰谜，6，16树绩，55萨脑，查找的次數(shù)分別為1，2饺饭，3渤早，4。假設(shè)每個(gè)節(jié)點(diǎn)的查找概率相等瘫俊，所以平均查找次數(shù)為(1+22+34+4)/8 ≈ 2.6鹊杖。如果是一顆單邊二叉排序樹(全部只有左子樹或只有右子樹)，則平均查找次數(shù)為(1+2+3+4+6+7+8)/8 = 4.5扛芽。
總結(jié)一下骂蓖，在最好的情況下，一顆包含n個(gè)節(jié)點(diǎn)的二叉排序樹的查找復(fù)雜度為O(log2(n))川尖；在最壞的情況下登下，復(fù)雜度為O(n)。一般的情況下叮喳，復(fù)雜度介于O(log2(n))到O(n)之間被芳。因此才需要構(gòu)造一顆平衡的二叉排序樹。
平衡二叉樹的定義
平衡二叉樹又叫AVL樹馍悟，具有以下性質(zhì)
1.左子樹和右子樹的深度的差值的絕對(duì)值不大于1
2.左子樹和右子樹都是平衡二叉樹
以上的第二點(diǎn)很好理解筐钟，第一點(diǎn)怎么理解呢？如下圖中赋朦，左邊是平衡二叉樹，右邊是非平衡二叉樹李破。圖中節(jié)點(diǎn)右邊是該節(jié)點(diǎn)左右子樹深度的差值宠哄。
平衡二叉樹的調(diào)整
在構(gòu)建二叉排序樹過程中，每插入一個(gè)新的節(jié)點(diǎn)嗤攻，先判斷插入是否會(huì)破壞樹的平衡性毛嫉。如果會(huì)，則找出最小不平衡子樹妇菱，在保持二叉排序樹的前提下承粤，調(diào)整最小平衡子樹中個(gè)節(jié)點(diǎn)之間的關(guān)系暴区。可以根據(jù)失衡的原因分為以下四種類型：
(1)LL型調(diào)整
假設(shè)在A節(jié)點(diǎn)左孩子B的左子樹上插入新的節(jié)點(diǎn)辛臊，導(dǎo)致A二叉排序樹失去平衡仙粱。如下圖中，插入值為2的新節(jié)點(diǎn)彻舰，A節(jié)點(diǎn)的值為10伐割，B節(jié)點(diǎn)的值為6，此時(shí)A樹的平衡差值從1變?yōu)?刃唤，從而失去了平衡隔心。
調(diào)整操作：向右順時(shí)針旋轉(zhuǎn)一次，就是將B作為根節(jié)點(diǎn)尚胞，A作為B的有孩子硬霍，同時(shí)將B的原來的右子樹作為A節(jié)點(diǎn)的左子樹。
(2)RR型調(diào)整
在A節(jié)點(diǎn)右孩子B的右子樹上插入新的節(jié)點(diǎn)笼裳，導(dǎo)致A二叉排序樹失去平衡唯卖。如下圖中，插入值為60的新節(jié)點(diǎn)侍咱，A節(jié)點(diǎn)的值為10耐床，B節(jié)點(diǎn)的值為20，此時(shí)A楔脯、B樹的平衡差值從1變?yōu)?撩轰，從而失去了平衡。
調(diào)整操作：向左逆時(shí)針旋轉(zhuǎn)一次昧廷，就是將B作為根節(jié)點(diǎn)堪嫂，A作為B的左孩子，同時(shí)B原來的左子樹調(diào)整為A子樹的右子樹木柬。
(3)LR型調(diào)整
在A節(jié)點(diǎn)的左孩子B的右子樹C上插入新節(jié)點(diǎn)導(dǎo)致二叉排序樹A失去平衡皆串。如下圖中，插入值為9的新節(jié)點(diǎn)眉枕，A節(jié)點(diǎn)的值為10恶复，B節(jié)點(diǎn)的值為5，C節(jié)點(diǎn)值為7速挑，此時(shí)A谤牡、B、C樹的平衡差值從1變?yōu)?姥宝，從而失去平衡翅萤。
調(diào)整操作：進(jìn)行兩次選轉(zhuǎn)，先順時(shí)針在逆時(shí)針腊满。就是將C作為根節(jié)點(diǎn)套么，A作為C的右孩子培己，B作為C的左孩子，同時(shí)調(diào)整C原來的兩棵子樹胚泌。將C原來的左子樹作為B的右子樹省咨，C的右子樹作為A的左子樹。
(4)RL型調(diào)整
在A的右孩子B的左子樹C上插入新的節(jié)點(diǎn)導(dǎo)致A樹失去平衡诸迟。如下圖中茸炒，插入值為9的新節(jié)點(diǎn)，A節(jié)點(diǎn)的值為10阵苇，B節(jié)點(diǎn)的值為20壁公，C節(jié)點(diǎn)的值為16，此時(shí)A绅项、B樹的平衡差值從1變?yōu)?紊册，C樹的平衡差值從0變?yōu)?，從而失去平衡快耿。
調(diào)整操作：將C節(jié)點(diǎn)作為根節(jié)點(diǎn)囊陡，A作為C的左孩子，B作為C的右孩子掀亥，同時(shí)調(diào)整C原來的兩棵子樹撞反，將C原來的左子樹調(diào)整為A的右子樹，C原來的右子樹調(diào)整為B的左孩子搪花。
