目錄

• 二叉樹的定義
• 二叉樹的性質(zhì)(特性)
• 滿二叉樹與完全二叉樹
• 鏈?zhǔn)酱鎯Φ亩鏄?/li>
• 順序存儲的二叉樹
• 線索二叉樹(Threaded BinaryTree)
• 二叉排序樹（Binary Sort Tree）
• 平衡二叉樹（ Balanced Binary Tree）
• • 為什么使用平衡二叉樹？
  • 如何判斷平衡二叉樹？
  • 相關(guān)概念
  • 旋轉(zhuǎn)方式
  • 實例
  • 代碼實現(xiàn)

二叉樹的定義

任何一個節(jié)點的子節(jié)點數(shù)量不超過 2，那就是二叉樹；二叉樹的子節(jié)點分為左節(jié)點和右節(jié)點，不能顛倒位置

二叉樹的性質(zhì)(特性)

性質(zhì)1：在二叉樹的第i層上至多有2^(i-1)個結(jié)點（i>0）

性質(zhì)2：深度為k的二叉樹至多有2^k - 1個結(jié)點（k>0）

性質(zhì)3：對于任意一棵二叉樹，如果其葉結(jié)點數(shù)為N0，而度數(shù)為2的結(jié)點總數(shù)為N2，則N0=N2+1;

性質(zhì)4：具有n個結(jié)點的完全二叉樹的深度必為 log2(n+1)

性質(zhì)5：對完全二叉樹，若從上至下、從左至右編號，則編號為i 的結(jié)點，其左孩子編號必為2i，其右孩子編號必為2i＋1；其雙親的編號必為i/2（i＝1 時為根,除外）

滿二叉樹與完全二叉樹

滿二叉樹： 所有葉子結(jié)點都集中在二叉樹的最下面一層上，而且結(jié)點總數(shù)為：2^n-1 (n為層數(shù) / 高度）

完全二叉樹： 所有的葉子節(jié)點都在最后一層或者倒數(shù)第二層，且最后一層葉子節(jié)點在左邊連續(xù)，倒數(shù)第二層在右邊連續(xù)（滿二叉樹也是屬于完全二叉樹）（從上往下，從左往右能挨著數(shù)滿）

鏈?zhǔn)酱鎯Φ亩鏄?/h1>

創(chuàng)建二叉樹：首先需要一個樹的類，還需要另一個類用來存放節(jié)點，設(shè)置節(jié)點；將節(jié)點放入樹中，就形成了二叉樹；（節(jié)點中需要權(quán)值，左子樹，右子樹，并且都能對他們的值進行設(shè)置）。

樹的遍歷：

• 先序遍歷：根節(jié)點，左節(jié)點，右節(jié)點（如果節(jié)點有子樹，先從左往右遍歷子樹，再遍歷兄弟節(jié)點）
  先序遍歷結(jié)果為：A B D H I E J C F K G

• 中序遍歷：左節(jié)點，根節(jié)點，右節(jié)點（中序遍歷可以看成，二叉樹每個節(jié)點，垂直方向投影下來（可以理解為每個節(jié)點從最左邊開始垂直掉到地上），然后從左往右數(shù)）
  中遍歷結(jié)果為：H D I B E J A F K C G

• 后序遍歷：左節(jié)點，右節(jié)點，根節(jié)點
  后序遍歷結(jié)果：H I D J E B K F G C A

• 層次遍歷：從上往下，從左往右
  層次遍歷結(jié)果：A B C D E F G H I J K
  

查找節(jié)點：先對樹進行一次遍歷，然后找出要找的那個數(shù)；因為有三種排序方法，所以查找節(jié)點也分為先序查找，中序查找，后序查找；

刪除節(jié)點：由于鏈?zhǔn)酱鎯?#xff0c;不能找到要刪的數(shù)直接刪除，需要找到他的父節(jié)點，然后將指向該數(shù)設(shè)置為null；所以需要一個變量來指向父節(jié)點，找到數(shù)后，再斷開連接。

代碼實現(xiàn)：

• 樹類

public class BinaryTree {TreeNode root;//設(shè)置根節(jié)點public void setRoot(TreeNode root) {this.root = root;}//獲取根節(jié)點public TreeNode getRoot() {return root;}//先序遍歷public void frontShow() {if (root != null) {root.frontShow();}}//中序遍歷public void middleShow() {if (root != null) {root.middleShow();}}//后序遍歷public void afterShow() {if (root != null) {root.afterShow();}}//先序查找public TreeNode frontSearch(int i) {return root.frontSearch(i);}//刪除一個子樹public void delete(int i) {if (root.value == i) {root = null;} else {root.delete(i);}} }

• 節(jié)點類

public class TreeNode {//節(jié)點的權(quán)int value;//左兒子TreeNode leftNode;//右兒子TreeNode rightNode;public TreeNode(int value) {this.value = value;}//設(shè)置左兒子public void setLeftNode(TreeNode leftNode) {this.leftNode = leftNode;}//設(shè)置右兒子public void setRightNode(TreeNode rightNode) {this.rightNode = rightNode;}//先序遍歷public void frontShow() {//先遍歷當(dāng)前節(jié)點的值System.out.print(value + " ");//左節(jié)點if (leftNode != null) {leftNode.frontShow(); //遞歸思想}//右節(jié)點if (rightNode != null) {rightNode.frontShow();}}//中序遍歷public void middleShow() {//左節(jié)點if (leftNode != null) {leftNode.middleShow(); //遞歸思想}//先遍歷當(dāng)前節(jié)點的值System.out.print(value + " ");//右節(jié)點if (rightNode != null) {rightNode.middleShow();}}//后續(xù)遍歷public void afterShow() {//左節(jié)點if (leftNode != null) {leftNode.afterShow(); //遞歸思想}//右節(jié)點if (rightNode != null) {rightNode.afterShow();}//先遍歷當(dāng)前節(jié)點的值System.out.print(value + " ");}//先序查找public TreeNode frontSearch(int i) {TreeNode target = null;//對比當(dāng)前節(jié)點的值if (this.value == i) {return this;//當(dāng)前節(jié)點不是要查找的節(jié)點} else {//查找左兒子if (leftNode != null) {//查找的話t賦值給target，查不到target還是nulltarget = leftNode.frontSearch(i);}//如果target不為空，說明在左兒子中已經(jīng)找到if (target != null) {return target;}//如果左兒子沒有查到，再查找右兒子if (rightNode != null) {target = rightNode.frontSearch(i);}}return target;}//刪除一個子樹public void delete(int i) {TreeNode parent = this;//判斷左兒子if (parent.leftNode != null && parent.leftNode.value == i) {parent.leftNode = null;return;}//判斷右兒子if (parent.rightNode != null && parent.rightNode.value == i) {parent.rightNode = null;return;}//如果都不是，遞歸檢查并刪除左兒子parent = leftNode;if (parent != null) {parent.delete(i);}//遞歸檢查并刪除右兒子parent = rightNode;if (parent != null) {parent.delete(i);}} }

• 測試類

public class Demo {public static void main(String[] args) {//創(chuàng)建一棵樹BinaryTree binaryTree = new BinaryTree();//創(chuàng)建一個根節(jié)點TreeNode root = new TreeNode(1);//把根節(jié)點賦給樹binaryTree.setRoot(root);//創(chuàng)建左,右節(jié)點TreeNode rootLeft = new TreeNode(2);TreeNode rootRight = new TreeNode(3);//把新建的節(jié)點設(shè)置為根節(jié)點的子節(jié)點root.setLeftNode(rootLeft);root.setRightNode(rootRight);//為第二層的左節(jié)點創(chuàng)建兩個子節(jié)點rootLeft.setLeftNode(new TreeNode(4));rootLeft.setRightNode(new TreeNode(5));//為第二層的右節(jié)點創(chuàng)建兩個子節(jié)點rootRight.setLeftNode(new TreeNode(6));rootRight.setRightNode(new TreeNode(7));//先序遍歷binaryTree.frontShow(); //1 2 4 5 3 6 7System.out.println();//中序遍歷binaryTree.middleShow(); //4 2 5 1 6 3 7System.out.println();//后序遍歷binaryTree.afterShow(); //4 5 2 6 7 3 1System.out.println();//先序查找TreeNode result = binaryTree.frontSearch(5);System.out.println(result); //binarytree.TreeNode@1b6d3586//刪除一個子樹binaryTree.delete(2);binaryTree.frontShow(); //1 3 6 7 ，2和他的子節(jié)點被刪除了} }

順序存儲的二叉樹

概述：順序存儲使用數(shù)組的形式實現(xiàn)；由于非完全二叉樹會導(dǎo)致數(shù)組中出現(xiàn)空缺，有的位置不能填上數(shù)字，所以順序存儲二叉樹通常情況下只考慮完全二叉樹

原理： 順序存儲在數(shù)組中是按照第一層第二層一次往下存儲的，遍歷方式也有先序遍歷、中序遍歷、后續(xù)遍歷

性質(zhì)：

• 第n個元素的左子節(jié)點是：2*n+1；
• 第n個元素的右子節(jié)點是：2*n+2；
• 第n個元素的父節(jié)點是：（n-1)/2

代碼實現(xiàn)：

• 樹類

public class ArrayBinaryTree {int[] data;public ArrayBinaryTree(int[] data) {this.data = data;}//重載先序遍歷方法，不用每次傳參數(shù)了,保證每次從頭開始public void frontShow() {frontShow(0);}//先序遍歷public void frontShow(int index) {if (data == null || data.length == 0) {return;}//先遍歷當(dāng)前節(jié)點的內(nèi)容System.out.print(data[index] + " ");//處理左子樹：2*index+1if (2 * index + 1 < data.length) {frontShow(2 * index + 1);}//處理右子樹：2*index+2if (2 * index + 2 < data.length) {frontShow(2 * index + 2);}} }

• 測試類

public class Demo {public static void main(String[] args) {int[] data = {1,2,3,4,5,6,7};ArrayBinaryTree tree = new ArrayBinaryTree(data);//先序遍歷tree.frontShow(); //1 2 4 5 3 6 7} }

線索二叉樹(Threaded BinaryTree)

為什么使用線索二叉樹？

當(dāng)用二叉鏈表作為二叉樹的存儲結(jié)構(gòu)時，可以很方便的找到某個結(jié)點的左右孩子；但一般情況下，無法直接找到該結(jié)點在某種遍歷序列中的前驅(qū)和后繼結(jié)點

原理：n個結(jié)點的二叉鏈表中含有n+1(2n-(n-1)=n+1個空指針域。利用二叉鏈表中的空指針域，存放指向結(jié)點在某種遍歷次序下的前驅(qū)和后繼結(jié)點的指針。

例如：某個結(jié)點的左孩子為空，則將空的左孩子指針域改為指向其前驅(qū)；如果某個結(jié)點的右孩子為空，則將空的右孩子指針域改為指向其后繼（這種附加的指針稱為"線索"）

代碼實現(xiàn)：

• 樹類

public class ThreadedBinaryTree {ThreadedNode root;//用于臨時存儲前驅(qū)節(jié)點ThreadedNode pre = null;//設(shè)置根節(jié)點public void setRoot(ThreadedNode root) {this.root = root;}//中序線索化二叉樹public void threadNodes() {threadNodes(root);}public void threadNodes(ThreadedNode node) {//當(dāng)前節(jié)點如果為null，直接返回if (node == null) {return;}//處理左子樹threadNodes(node.leftNode);//處理前驅(qū)節(jié)點if (node.leftNode == null) {//讓當(dāng)前節(jié)點的左指針指向前驅(qū)節(jié)點node.leftNode = pre;//改變當(dāng)前節(jié)點左指針類型node.leftType = 1;}//處理前驅(qū)的右指針，如果前驅(qū)節(jié)點的右指針是null（沒有右子樹）if (pre != null && pre.rightNode == null) {//讓前驅(qū)節(jié)點的右指針指向當(dāng)前節(jié)點pre.rightNode = node;//改變前驅(qū)節(jié)點的右指針類型pre.rightType = 1;}//每處理一個節(jié)點，當(dāng)前節(jié)點是下一個節(jié)點的前驅(qū)節(jié)點pre = node;//處理右子樹threadNodes(node.rightNode);}//遍歷線索二叉樹public void threadIterate() {//用于臨時存儲當(dāng)前遍歷節(jié)點ThreadedNode node = root;while (node != null) {//循環(huán)找到最開始的節(jié)點while (node.leftType == 0) {node = node.leftNode;}//打印當(dāng)前節(jié)點的值System.out.print(node.value + " ");//如果當(dāng)前節(jié)點的右指針指向的是后繼節(jié)點，可能后繼節(jié)點還有后繼節(jié)點while (node.rightType == 1) {node = node.rightNode;System.out.print(node.value + " ");}//替換遍歷的節(jié)點node = node.rightNode;}}//獲取根節(jié)點public ThreadedNode getRoot() {return root;}//先序遍歷public void frontShow() {if (root != null) {root.frontShow();}}//中序遍歷public void middleShow() {if (root != null) {root.middleShow();}}//后序遍歷public void afterShow() {if (root != null) {root.afterShow();}}//先序查找public ThreadedNode frontSearch(int i) {return root.frontSearch(i);}//刪除一個子樹public void delete(int i) {if (root.value == i) {root = null;} else {root.delete(i);}} }

• 節(jié)點類

public class ThreadedNode {//節(jié)點的權(quán)int value;//左兒子ThreadedNode leftNode;//右兒子ThreadedNode rightNode;//標(biāo)識指針類型,1表示指向上一個節(jié)點，0int leftType;int rightType;public ThreadedNode(int value) {this.value = value;}//設(shè)置左兒子public void setLeftNode(ThreadedNode leftNode) {this.leftNode = leftNode;}//設(shè)置右兒子public void setRightNode(ThreadedNode rightNode) {this.rightNode = rightNode;}//先序遍歷public void frontShow() {//先遍歷當(dāng)前節(jié)點的值System.out.print(value + " ");//左節(jié)點if (leftNode != null) {leftNode.frontShow(); //遞歸思想}//右節(jié)點if (rightNode != null) {rightNode.frontShow();}}//中序遍歷public void middleShow() {//左節(jié)點if (leftNode != null) {leftNode.middleShow(); //遞歸思想}//先遍歷當(dāng)前節(jié)點的值System.out.print(value + " ");//右節(jié)點if (rightNode != null) {rightNode.middleShow();}}//后續(xù)遍歷public void afterShow() {//左節(jié)點if (leftNode != null) {leftNode.afterShow(); //遞歸思想}//右節(jié)點if (rightNode != null) {rightNode.afterShow();}//先遍歷當(dāng)前節(jié)點的值System.out.print(value + " ");}//先序查找public ThreadedNode frontSearch(int i) {ThreadedNode target = null;//對比當(dāng)前節(jié)點的值if (this.value == i) {return this;//當(dāng)前節(jié)點不是要查找的節(jié)點} else {//查找左兒子if (leftNode != null) {//查找的話t賦值給target，查不到target還是nulltarget = leftNode.frontSearch(i);}//如果target不為空，說明在左兒子中已經(jīng)找到if (target != null) {return target;}//如果左兒子沒有查到，再查找右兒子if (rightNode != null) {target = rightNode.frontSearch(i);}}return target;}//刪除一個子樹public void delete(int i) {ThreadedNode parent = this;//判斷左兒子if (parent.leftNode != null && parent.leftNode.value == i) {parent.leftNode = null;return;}//判斷右兒子if (parent.rightNode != null && parent.rightNode.value == i) {parent.rightNode = null;return;}//如果都不是，遞歸檢查并刪除左兒子parent = leftNode;if (parent != null) {parent.delete(i);}//遞歸檢查并刪除右兒子parent = rightNode;if (parent != null) {parent.delete(i);}} }

• 測試類

public class Demo {public static void main(String[] args) {//創(chuàng)建一棵樹ThreadedBinaryTree binaryTree = new ThreadedBinaryTree();//創(chuàng)建一個根節(jié)點ThreadedNode root = new ThreadedNode(1);//把根節(jié)點賦給樹binaryTree.setRoot(root);//創(chuàng)建左,右節(jié)點ThreadedNode rootLeft = new ThreadedNode(2);ThreadedNode rootRight = new ThreadedNode(3);//把新建的節(jié)點設(shè)置為根節(jié)點的子節(jié)點root.setLeftNode(rootLeft);root.setRightNode(rootRight);//為第二層的左節(jié)點創(chuàng)建兩個子節(jié)點rootLeft.setLeftNode(new ThreadedNode(4));ThreadedNode fiveNode = new ThreadedNode(5);rootLeft.setRightNode(fiveNode);//為第二層的右節(jié)點創(chuàng)建兩個子節(jié)點rootRight.setLeftNode(new ThreadedNode(6));rootRight.setRightNode(new ThreadedNode(7));//中序遍歷binaryTree.middleShow(); //4 2 5 1 6 3 7System.out.println();//中序線索化二叉樹binaryTree.threadNodes(); // //獲取5的后繼節(jié)點 // ThreadedNode afterFive = fiveNode.rightNode; // System.out.println(afterFive.value); //1binaryTree.threadIterate(); //4 2 5 1 6 3 7} }

二叉排序樹（Binary Sort Tree）

無序序列：
二叉排序樹圖解：

概述：二叉排序樹（Binary Sort Tree）也叫二叉查找樹或者是一顆空樹，對于二叉樹中的任何一個非葉子節(jié)點，要求左子節(jié)點比當(dāng)前節(jié)點值小，右子節(jié)點比當(dāng)前節(jié)點值大

特點：

• 查找性能與插入刪除性能都適中還不錯
• 中序遍歷的結(jié)果剛好是從大到小

創(chuàng)建二叉排序樹原理：其實就是不斷地插入節(jié)點，然后進行比較。

刪除節(jié)點

• 刪除葉子節(jié)點，只需要找到父節(jié)點，將父節(jié)點與他的連接斷開即可
• 刪除有一個子節(jié)點的就需要將他的子節(jié)點換到他現(xiàn)在的位置
• 刪除有兩個子節(jié)點的節(jié)點，需要使用他的前驅(qū)節(jié)點或者后繼節(jié)點進行替換，就是左子樹最右下方的數(shù)（最大的那個）或右子樹最左邊的樹（最小的數(shù)）；即離節(jié)點值最接近的值；（還要注解要去判斷這個值有沒有右節(jié)點，有就要將右節(jié)點移上來）

代碼實現(xiàn)：

• 樹類

public class BinarySortTree {Node root;//添加節(jié)點public void add(Node node) {//如果是一顆空樹if (root == null) {root = node;} else {root.add(node);}}//中序遍歷public void middleShow() {if (root != null) {root.middleShow(root);}}//查找節(jié)點public Node search(int value) {if (root == null) {return null;}return root.search(value);}//查找父節(jié)點public Node searchParent(int value) {if (root == null) {return null;}return root.searchParent(value);}//刪除節(jié)點public void delete(int value) {if (root == null) {return;} else {//找到這個節(jié)點Node target = search(value);//如果沒有這個節(jié)點if (target == null) {return;}//找到他的父節(jié)點Node parent = searchParent(value);//要刪除的節(jié)點是葉子節(jié)點if (target.left == null && target.left == null) {//要刪除的節(jié)點是父節(jié)點的左子節(jié)點if (parent.left.value == value) {parent.left = null;}//要刪除的節(jié)點是父節(jié)點的右子節(jié)點else {parent.right = null;}}//要刪除的節(jié)點有兩個子節(jié)點的情況else if (target.left != null && target.right != null) {//刪除右子樹中值最小的節(jié)點，并且獲取到值int min = deletMin(target.right);//替換目標(biāo)節(jié)點中的值target.value = min;}//要刪除的節(jié)點有一個左子節(jié)點或右子節(jié)點else {//有左子節(jié)點if (target.left != null) {//要刪除的節(jié)點是父節(jié)點的左子節(jié)點if (parent.left.value == value) {parent.left = target.left;}//要刪除的節(jié)點是父節(jié)點的右子節(jié)點else {parent.right = target.left;}}//有右子節(jié)點else {//要刪除的節(jié)點是父節(jié)點的左子節(jié)點if (parent.left.value == value) {parent.left = target.right;}//要刪除的節(jié)點是父節(jié)點的右子節(jié)點else {parent.right = target.right;}}}}}//刪除一棵樹中最小的節(jié)點private int deletMin(Node node) {Node target = node;//遞歸向左找最小值while (target.left != null) {target = target.left;}//刪除最小的節(jié)點delete(target.value);return target.value;} }

• 節(jié)點類

public class Node {int value;Node left;Node right;public Node(int value) {this.value = value;}//向子樹中添加節(jié)點public void add(Node node) {if (node == null) {return;}/*判斷傳入的節(jié)點的值比當(dāng)前紫薯的根節(jié)點的值大還是小*///添加的節(jié)點比當(dāng)前節(jié)點更小(傳給左節(jié)點）if (node.value < this.value) {//如果左節(jié)點為空if (this.left == null) {this.left = node;}//如果不為空else {this.left.add(node);}}//添加的節(jié)點比當(dāng)前節(jié)點更大(傳給右節(jié)點）else {if (this.right == null) {this.right = node;} else {this.right.add(node);}}}//中序遍歷二叉排序樹，結(jié)果剛好是從小到大public void middleShow(Node node) {if (node == null) {return;}middleShow(node.left);System.out.print(node.value + " ");middleShow(node.right);}//查找節(jié)點public Node search(int value) {if (this.value == value) {return this;} else if (value < this.value) {if (left == null) {return null;}return left.search(value);} else {if (right == null) {return null;}return right.search(value);}}//查找父節(jié)點public Node searchParent(int value) {if ((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) {return this;} else {if (this.value > value && this.left != null) {return this.left.searchParent(value);} else if (this.value < value && this.right != null) {return this.right.searchParent(value);}return null;}} }

• 測試類

public class Demo {public static void main(String[] args) {int[] arr = {8, 3, 10, 1, 6, 14, 4, 7, 13};//創(chuàng)建一顆二叉排序樹BinarySortTree bst = new BinarySortTree();//循環(huán)添加 /* for(int i=0;i< arr.length;i++) {bst.add(new Node(arr[i]));}*/for (int i : arr) {bst.add(new Node(i));}//中序遍歷bst.middleShow(); //1 3 4 6 7 8 10 13 14System.out.println();//查找節(jié)點Node node = bst.search(10);System.out.println(node.value);//10Node node2 = bst.search(20);System.out.println(node2); //null//查找父節(jié)點Node node3 = bst.searchParent(1);Node node4 = bst.searchParent(14);System.out.println(node3.value); //3System.out.println(node4.value); //10//刪除葉子節(jié)點 // bst.delete(13); // bst.middleShow(); //1 3 4 6 7 8 10 14 // System.out.println(); // //刪除只有一個子節(jié)點的節(jié)點 // bst.delete(10); // bst.middleShow(); //1 3 4 6 7 8 ；10和14都沒了//刪除有兩個子節(jié)點的節(jié)點bst.delete(3);bst.middleShow(); //1 4 6 7 8 10 13 14} }

平衡二叉樹（ Balanced Binary Tree）

為什么使用平衡二叉樹？

平衡二叉樹（Balanced Binary Tree）又被稱為AVL樹，且具有以下性質(zhì)：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。這個方案很好的解決了二叉查找樹退化成鏈表的問題，把插入，查找，刪除的時間復(fù)雜度最好情況和最壞情況都維持在O(logN)。但是頻繁旋轉(zhuǎn)會使插入和刪除犧牲掉O(logN)左右的時間，不過相對二叉查找樹來說，時間上穩(wěn)定了很多。

二叉排序樹插入 {1,2,3,4,5,6} 這種數(shù)據(jù)結(jié)果如下圖所示：

平衡二叉樹插入 {1,2,3,4,5,6} 這種數(shù)據(jù)結(jié)果如下圖所示：

如何判斷平衡二叉樹？

• 1、是二叉排序樹
• 2、任何一個節(jié)點的左子樹或者右子樹都是平衡二叉樹（左右高度差小于等于 1）

（1）下圖不是平衡二叉樹，因為它不是二叉排序樹違反第 1 條件

（2）下圖不是平衡二叉樹，因為有節(jié)點子樹高度差大于 1 違法第 2 條件（5的左子樹為0，右子樹為2）

（3）下圖是平衡二叉樹，因為符合 1、2 條件

相關(guān)概念

平衡因子 BF

• 定義：左子樹和右子樹高度差
• 計算：左子樹高度 - 右子樹高度的值
• 別名：簡稱 BF（Balance Factor）
• 一般來說 BF 的絕對值大于 1，,平衡樹二叉樹就失衡，需要旋轉(zhuǎn)糾正

最小不平衡子樹

• 距離插入節(jié)點最近的，并且 BF 的絕對值大于 1 的節(jié)點為根節(jié)點的子樹。

• 旋轉(zhuǎn)糾正只需要糾正最小不平衡子樹即可

• 例子如下圖所示：
  

旋轉(zhuǎn)方式

2 種旋轉(zhuǎn)方式:

左旋 :

• 舊根節(jié)點為新根節(jié)點的左子樹
• 新根節(jié)點的左子樹（如果存在）為舊根節(jié)點的右子樹

右旋：

• 舊根節(jié)點為新根節(jié)點的右子樹
• 新根節(jié)點的右子樹（如果存在）為舊根節(jié)點的左子樹

4 種旋轉(zhuǎn)糾正類型：

• 左左型：插入左孩子的左子樹，右旋
• 右右型：插入右孩子的右子樹，左旋
• 左右型：插入左孩子的右子樹，先左旋，再右旋
• 右左型：插入右孩子的左子樹，先右旋，再左旋
  

左左型：

第三個節(jié)點（1）插入的時候，BF(3) = 2，BF(2) = 1，右旋，根節(jié)點順時針旋轉(zhuǎn)

右右型：

第三個節(jié)點（3）插入的時候，BF(1)=-2 BF(2)=-1，RR 型失衡，左旋，根節(jié)點逆時針旋轉(zhuǎn)

左右型：

第三個節(jié)點（3）插入的 時候，BF(3)=2 BF(1)=-1 LR 型失衡，先 左旋 再 右旋


右左型：

第三個節(jié)點（1）插入的 時候，BF(1)=-2 BF(3)=1 RL 型失衡，先 右旋 再 左旋

實例

（1）、依次插入 3、2、1 插入第三個點 1 的時候 BF(3)=2 BF(2)=1，LL 型失衡，對最小不平衡樹 {3,2,1}進行 右旋

• 舊根節(jié)點（節(jié)點 3）為新根節(jié)點（節(jié)點 2）的右子樹
• 新根節(jié)點（節(jié)點 2）的右子樹（這里沒有右子樹）為舊根節(jié)點的左子樹
  

（2）依次插入 4 ，5 插入 5 點的時候 BF(3) = -2 BF(4)=-1，RR 型失衡，對最小不平衡樹 {3,4,5} 進行左旋

• 舊根節(jié)點（節(jié)點 3）為新根節(jié)點（節(jié)點 4）的左子樹
• 新根節(jié)點（節(jié)點 4）的左子樹（這里沒有左子樹）為舊根節(jié)點的右子樹
  

（3）插入 4 ，5 插入 5 點的時候 BF(2)=-2 BF(4)=-1 ，RR 型失衡 對最小不平衡樹{1,2,4}進行左旋

• 舊根節(jié)點（節(jié)點 2）為新根節(jié)點（節(jié)點 4）的左子樹
  
• 新根節(jié)點（節(jié)點 4）的 左子樹（節(jié)點 3）為舊根節(jié)點的右子樹
  

（4）插入 7 節(jié)點的時候 BF(5)=-2, BF(6)=-1 ，RR 型失衡，對最小不平衡樹 進行左旋

• 舊根節(jié)點（節(jié)點 5）為新根節(jié)點（節(jié)點 6）的左子樹
• 新根節(jié)點的左子樹（這里沒有）為舊根節(jié)點的右子樹
  

（5）依次插入 10 ，9 。插入 9 點的時候 BF(10) = 1，BF(7) = -2 ，RL 型失衡，對先右旋再左旋，右子樹先右旋

• 舊根節(jié)點（節(jié)點 10）為新根節(jié)點（節(jié)點 9）的右子樹
• 新根節(jié)點（節(jié)點 9）的右子樹（這里沒有右子樹）為舊根節(jié)點的左子樹
  
  最小不平衡子樹再左旋：
• 舊根節(jié)點（節(jié)點 7）為新根節(jié)點（節(jié)點 9）的左子樹
• 新根節(jié)點（節(jié)點 9）的左子樹（這里沒有左子樹）為舊根節(jié)點的右子樹
  

代碼實現(xiàn)

• 節(jié)點類

public class Node {int value;Node left;Node right;public Node(int value) {this.value = value;}//獲取當(dāng)前節(jié)點高度public int height() {return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;}//獲取左子樹高度public int leftHeight() {if (left == null) {return 0;}return left.height();}//獲取右子樹高度public int rightHeight() {if (right == null) {return 0;}return right.height();}//向子樹中添加節(jié)點public void add(Node node) {if (node == null) {return;}/*判斷傳入的節(jié)點的值比當(dāng)前紫薯的根節(jié)點的值大還是小*///添加的節(jié)點比當(dāng)前節(jié)點更小(傳給左節(jié)點）if (node.value < this.value) {//如果左節(jié)點為空if (this.left == null) {this.left = node;}//如果不為空else {this.left.add(node);}}//添加的節(jié)點比當(dāng)前節(jié)點更大(傳給右節(jié)點）else {if (this.right == null) {this.right = node;} else {this.right.add(node);}}//查詢是否平衡//右旋轉(zhuǎn)if (leftHeight() - rightHeight() >= 2) {//雙旋轉(zhuǎn)，當(dāng)左子樹左邊高度小于左子樹右邊高度時if (left != null && left.leftHeight() < left.rightHeight()) {//左子樹先進行左旋轉(zhuǎn)left.leftRotate();//整體進行右旋轉(zhuǎn)rightRotate();}//單旋轉(zhuǎn)else {rightRotate();}}//左旋轉(zhuǎn)if (leftHeight() - rightHeight() <= -2) {//雙旋轉(zhuǎn)if (right != null && right.rightHeight() < right.leftHeight()) {right.rightRotate();leftRotate();}//單旋轉(zhuǎn)else {leftRotate();}}}//右旋轉(zhuǎn)private void rightRotate() {//創(chuàng)建一個新的節(jié)點，值等于當(dāng)前節(jié)點的值Node newRight = new Node(value);//把新節(jié)點的右子樹設(shè)置為當(dāng)前節(jié)點的右子樹newRight.right = right;//把新節(jié)點的左子樹設(shè)置為當(dāng)前節(jié)點的左子樹的右子樹newRight.left = left.right;//把當(dāng)前節(jié)點的值換位左子節(jié)點的值value = left.value;//把當(dāng)前節(jié)點的左子樹設(shè)置為左子樹的左子樹left = left.left;//把當(dāng)前節(jié)點設(shè)置為新節(jié)點right = newRight;}//左旋轉(zhuǎn)private void leftRotate() {//創(chuàng)建一個新的節(jié)點，值等于當(dāng)前節(jié)點的值Node newLeft = new Node(value);//把新節(jié)點的左子樹設(shè)置為當(dāng)前節(jié)點的左子樹newLeft.left = left;//把新節(jié)點的右子樹設(shè)置為當(dāng)前節(jié)點的右子樹的左子樹newLeft.right = right.left;//把當(dāng)前節(jié)點的值換位右子節(jié)點的值value = right.value;//把當(dāng)前節(jié)點的右子樹設(shè)置為右子樹的右子樹right = right.right;//把當(dāng)前節(jié)點設(shè)置為新節(jié)點left = newLeft;}//中序遍歷二叉排序樹，結(jié)果剛好是從小到大public void middleShow(Node node) {if (node == null) {return;}middleShow(node.left);System.out.print(node.value + " ");middleShow(node.right);}//查找節(jié)點public Node search(int value) {if (this.value == value) {return this;} else if (value < this.value) {if (left == null) {return null;}return left.search(value);} else {if (right == null) {return null;}return right.search(value);}}//查找父節(jié)點public Node searchParent(int value) {if ((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) {return this;} else {if (this.value > value && this.left != null) {return this.left.searchParent(value);} else if (this.value < value && this.right != null) {return this.right.searchParent(value);}return null;}} }

• 測試類

public class Demo {public static void main(String[] args) {int[] arr = {1,2,3,4,5,6};//創(chuàng)建一顆二叉排序樹BinarySortTree bst = new BinarySortTree();//循環(huán)添加for (int i : arr) {bst.add(new Node(i));}//查看高度System.out.println(bst.root.height()); //3//查看節(jié)點值System.out.println(bst.root.value); //根節(jié)點為4System.out.println(bst.root.left.value); //左子節(jié)點為2System.out.println(bst.root.right.value); //右子節(jié)點為5} }

總結(jié)

以上是生活随笔為你收集整理的数据结构与算法之二叉树大全的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。