樹的概述
樹是一種重要的非線性資料結構，直觀地看，它是資料元素（在樹中稱為結點）按分支關系組織起來的結構，很象自然界中的樹那樣，形同下圖，
樹有如下基本概念：
-
根結點
根結點是樹的一個組成部分，也叫樹根，每一顆樹都有且僅有一個根結點，它是同一棵樹中除本身外所有結點的祖先，沒有父結點，按上圖的樹結構來看，根節點就是 1，
-
父結點
也叫雙親結點，一個結點如果有上一級，則稱這個上一級是它的父結點，如果沒有上一級，則該結點無父結點，按上圖的樹結構來看，可以說是父節點有 1、2、3、5、6、22，
-
子結點
一個結點如果有下一級，則稱這個下一級是它的子結點，如果沒有下一級，則該結點無子結點，按上圖的樹結構來看，其實除了根結點以外，各個結點都是它們對應父結點的子結點，
-
路徑
從根結點訪問其他結點所需要經過的結點，比如從 1 要走到 31，則路徑是 1、3、31，
-
結點的度
一個結點擁有多少個子結點，就認為它的度是多少，比如根結點 1，它的度就是 5，
-
結點的權
結點的權值，圖中每個結點都有對應的數字，這些數字就是對應結點的權，
-
葉子結點
沒有子結點的結點，按上圖的樹結構來看，葉子結點有 21、221、222、223、31、51、52、61，
-
子樹
還是上圖，試著把結點 2 單獨拿出來看，會發現它和它的子結點也能構成樹結構，這顆樹在整顆大的樹里邊，所以稱為子樹，
-
層
結點的層次從根開始定義起，根為第一層，根的孩子是二層，依次累計，上圖的樹結構層次就是 4，
-
樹的高度
樹的最大層數，上圖的樹結構最大層數就是從根結點開始，到最底層的葉子結點，高度是 4，
-
森林
多個樹組成的集合，想象現在有好多顆樹，每一顆樹結構不一，它們共同構成森林，
二叉樹的概述
任何子結點的數量都不超過 2，就是一顆二叉樹，比如之前舉例的圖，明顯就不是二叉樹，二叉樹的子結點分左結點和右結點，不能隨意顛倒位置，
二叉樹也有分類：
-
滿二叉樹
所有葉子結點都在最后一層，而且結點總數為 2^n - 1，n 是樹的高度，
-
完全二叉樹
所有葉子結點都在最后一層或倒數第二層，且最后一層葉子結點在左邊延續，倒數第二層的葉子結點在右邊連續，即最后一層的葉子結點總是從左往右，倒數第二層總是從右到左，滿二叉樹也是一顆完全二叉樹，
鏈式存盤的二叉樹
顧名思義，用鏈表的方式去實作二叉樹結構，用代碼去實作，首先我們要創建一個結點類，
public class TreeNode {
// 節點的權
private int value;
// 左子結點
private TreeNode leftNode;
// 右子結點
private TreeNode rightNode;
public TreeNode(int value) {
this.value = https://www.cnblogs.com/Yee-Q/p/value;
}
// 剩下的都是 set/get 方法了
...
}
其次，和鏈表有頭結點一樣，二叉樹也需要有根結點輔助操作，作為創建二叉樹的基礎，
public class BinaryTree {
private TreeNode root;
public TreeNode getRoot() {
return root;
}
public void setRoot(TreeNode root) {
this.root = root;
}
}
萬事具備，向根結點添加左右子結點即可，
public class TestBinaryTree {
public static void main(String[] args) {
// 創建二叉樹
BinaryTree binaryTree = new BinaryTree();
// 創建根結點
TreeNode root = new TreeNode(1);
// 設定根結點
binaryTree.setRoot(root);
// 創建一個左結點
TreeNode rootL = new TreeNode(2);
// 把新創建的結點設定為根結點的左子結點
root.setLeftNode(rootL);
// 創建一個右結點
TreeNode rootR = new TreeNode(3);
// 把新創建的結點設定為根結點的右子結點
root.setRightNode(rootR);
// 為第二層的左結點創建兩個子結點
rootL.setLeftNode(new TreeNode(4));
rootL.setRightNode(new TreeNode(5));
// 為第二層的右結點創建兩個子結點
rootR.setLeftNode(new TreeNode(6));
rootR.setRightNode(new TreeNode(7));
}
}
遍歷二叉樹
二叉樹的遍歷方式有三種，分別是：前序遍歷、中序遍歷、后序遍歷，
以上圖為例，記住一點，所謂的前序、中序、后序都是參考當前結點的位置，前序遍歷，即是先取當前結點的權，然后是它的左子結點，最后是右子結點，從根結點開始，遍歷程序中每一個結點都要遵守這個規矩，
因此上圖前序遍歷得到的結果是：1、2、4、5、3、6、7；中序遍歷得到的結果是：4、2、5、1、6、3、7；后序遍歷得到的結果是：4、5、2、6、3、7、1，代碼實作用到遞回的思想，
public class TestBinaryTree {
public static void main(String[] args) {
// 之前創建二叉樹的代碼，這里就省略不寫了
...
// 前序遍歷樹
binaryTree.frontShow();
System.out.println("-----------------");
// 中序遍歷樹
binaryTree.midShow();
System.out.println("-----------------");
// 后序遍歷樹
binaryTree.afterShow();
}
}
public class BinaryTree {
private TreeNode root;
public TreeNode getRoot() {
return root;
}
public void setRoot(TreeNode root) {
this.root = root;
}
// 前序遍歷
public void frontShow() {
if (root != null) {
root.frontShow();
}
}
// 中序遍歷
public void midShow() {
if (root != null) {
root.midShow();
}
}
// 后序遍歷
public void afterShow() {
if (root != null) {
root.afterShow();
}
}
}
public class TreeNode {
// 節點的權
private int value;
// 左子結點
private TreeNode leftNode;
// 右子結點
private TreeNode rightNode;
public TreeNode(int value) {
this.value = https://www.cnblogs.com/Yee-Q/p/value;
}
// set/get 方法
...
// 前序遍歷
public void frontShow() {
// 先輸出當前結點內容
System.out.println(value);
// 輸出左結點內容
if (leftNode != null) {
leftNode.frontShow();
}
// 輸出右結點內容
if (rightNode != null) {
rightNode.frontShow();
}
}
// 中序遍歷
public void midShow() {
// 輸出左結點內容
if (leftNode != null) {
leftNode.midShow();
}
// 輸出當前結點內容
System.out.println(value);
// 輸出右結點內容
if (rightNode != null) {
rightNode.midShow();
}
}
// 后序遍歷
public void afterShow() {
// 輸出左結點內容
if (leftNode != null) {
leftNode.afterShow();
}
// 輸出右結點內容
if (rightNode != null) {
rightNode.afterShow();
}
// 輸出當前結點內容
System.out.println(value);
}
}
二叉樹中結點的查找
查找結點，實際就是把整顆二叉樹遍歷一次，依次比對，找出結果并回傳，這里以前序查找為例，其余的大同小異，
public class TestBinaryTree {
public static void main(String[] args) {
// 創建二叉樹
...
// 前序查找
TreeNode result = binaryTree.frontSearch(5);
System.out.println(result);
}
}
public class BinaryTree {
private TreeNode root;
public TreeNode getRoot() {
return root;
}
public void setRoot(TreeNode root) {
this.root = root;
}
/**
* 前序查找
* @return 目標結點
*/
public TreeNode frontSearch(int value) {
return root.frontSearch(value);
}
}
public class TreeNode {
// 節點的權
private int value;
// 左子結點
private TreeNode leftNode;
// 右子結點
private TreeNode rightNode;
public TreeNode(int value) {
this.value = https://www.cnblogs.com/Yee-Q/p/value;
}
/**
* 前序查找
* @return 目標結點
*/
public TreeNode frontSearch(int value) {
TreeNode target = null;
// 回傳本結點
if (this.value == value) {
return this;
}
// 向左子結點方向查找
if (leftNode != null) {
target = leftNode.frontSearch(value);
}
// 如果不為空，證明找到結點，回傳
if (target != null) {
return target;
}
// 向右子結點方向查找
if (rightNode != null) {
target = rightNode.frontSearch(value);
}
return target;
}
}
洗掉二叉樹的結點
對于一顆普通的二叉樹而言，洗掉一個結點就等同于把對應的整顆子樹一并刪掉，之后講到二叉排序樹時，就不是這樣操作了，
洗掉時要區分是根結點還是其他結點，如果是根結點的話，直接置為 null 就好了，但如果不是，則依次比較左右兩個子結點，符合就直接置為 null，如果都不符合，那就遞回呼叫左右結點的 delete 方法，
public class TestBinaryTree {
public static void main(String[] args) {
// 創建一顆子樹
...
// 洗掉一個結點
binaryTree.delete(5);
binaryTree.frontShow();
}
}
public class BinaryTree {
private TreeNode root;
...
/**
* 根據權值洗掉結點
* @param value 依據權值
*/
public void delete(int value) {
// 要洗掉的是根結點
if (root.getValue() == value) {
root = null;
} else {
// 要洗掉的是其他結點
root.delete(value);
}
}
}
public class TreeNode {
// 節點的權
private int value;
// 左子結點
private TreeNode leftNode;
// 右子結點
private TreeNode rightNode;
...
/**
* 根據權值洗掉結點
* @param value 依據權值
*/
public void delete(int value) {
TreeNode parent = this;
// 判斷左子結點
if (parent.leftNode != null && parent.leftNode.value =https://www.cnblogs.com/Yee-Q/p/= value) {
parent.leftNode = null;
return;
}
// 判斷右子結點
if (parent.rightNode != null && parent.rightNode.value == value) {
parent.rightNode = null;
return;
}
parent = leftNode;
if (parent != null) {
parent.delete(value);
}
parent = rightNode;
if (parent != null) {
parent.delete(value);
}
}
}
順序存盤的二叉樹
二叉樹還可以用陣列實作，或者說，任意一個陣列都可以轉化為二叉樹，就上圖二叉樹而言，它對應的陣列實作就是 [1,2,3,4,5,6,7]，
并不是每顆二叉樹都長得這么規矩，有可能會出現缺胳膊少腿的情況，通常情況下，順序存盤的二叉樹只考慮完全二叉樹（滿二叉樹也是完全二叉樹），否則沒有意義，
順序存盤的二叉樹還有其對應的性質公式，常用的有如下三個：
- 陣列中第 n 個元素的左子結點下標為：2*n + 1
- 陣列中第 n 個元素的左子結點下標為：2*n + 2
- 陣列中第 n 個元素的父節點下標為：(n-1)/ 2
順序存盤的二叉樹的遍歷
我們把一個陣列當成二叉樹作前序遍歷，剩下的中序和后序遍歷也大同小異了，
public class TestBinaryTree {
public static void main(String[] args) {
int[] data = https://www.cnblogs.com/Yee-Q/p/new int[]{1, 2, 3, 4, 5, 6, 7};
ArrayBinaryTree arrayBinaryTree = new ArrayBinaryTree(data);
// 前序遍歷
arrayBinaryTree.frontShow();
}
}
public class ArrayBinaryTree {
private int[] data;
public ArrayBinaryTree(int[] data) {
this.data = https://www.cnblogs.com/Yee-Q/p/data;
}
public int[] getData() {
return data;
}
public void setData(int[] data) {
this.data = data;
}
public void frontShow() {
frontShow(0);
}
public void frontShow(int index) {
if (data == null || data.length == 0) {
return;
}
// 先遍歷當前結點的內容
System.out.println(data[index]);
// 遍歷左子結點
if (2 * index + 1 < data.length) {
frontShow(2 * index + 1);
}
// 遍歷右子結點
if (2 * index + 2 < data.length) {
frontShow(2 * index + 2);
}
}
}
線索二叉樹
可以發現，無論二叉樹的形態如何，總會有一些結點（尤其是葉子結點）的域是沒有被使用的（左右子樹為空），為了提高利用率，讓原來的空域存放指標，指向樹中其他結點，這種指標稱為線索，
在二叉樹的結點加上線索的二叉樹稱為線索二叉樹，對二叉樹以某種遍歷方式（如前序、中序、后序或層次等）進行遍歷，使其變為線索二叉樹的程序稱為對二叉樹進行線索化，
以中序遍歷為例，經過中序線索化的二叉樹應該具有如下結構：對于非子結點的域，左域指向自身的前一個結點，右域指向自身的后一個結點
使用 Java 實作的線索二叉樹如下：
/**
* 結點類
*/
public class ThreadedNode {
int value;
// 左子結點
ThreadedNode left;
// 右子結點
ThreadedNode right;
// 標識指標型別，為 0 表示指向左/右子結點，為 1 表示指向前驅/后繼結點
int leftType;
int rightType;
public ThreadedNode(int value) {
this.value = https://www.cnblogs.com/Yee-Q/p/value;
}
...
}
public class ThreadedBinaryTree {
private ThreadedNode root;
// 用于臨時存盤前驅結點
private ThreadedNode pre;
public ThreadedNode getRoot() {
return root;
}
/**
* 設定根結點
*/
public void setRoot(ThreadedNode root) {
this.root = root;
}
/**
* 線索化二叉樹
*/
public void threadNodes() {
threadNodes(root);
}
public void threadNodes(ThreadedNode node) {
// 當前結點為 null，直接回傳
if (node == null) {
return;
}
// 處理左子樹
threadNodes(node.left);
// 處理前驅結點
if (node.left == null) {
// 讓當前結點的左指標指向前驅結點
node.left = pre;
// 改變當前結點左指標的型別
node.leftType = 1;
}
// 處理前驅結點的右指標，如果前驅結點的右指標是 null（沒有指向右子樹）
if (pre != null && pre.right == null) {
// 讓前驅結點的右指標指向當前結點
pre.right = node;
// 改變前驅結點的右指標型別
pre.rightType = 1;
}
// 每處理一個結點，當前結點就是下一個結點的前驅結點
pre = node;
// 處理右子樹
threadNodes(node.right);
}
/**
* 遍歷線索二叉樹
*/
public void threadIterate() {
// 用于臨時存盤當前遍歷結點
ThreadedNode node = root;
while (node != null) {
// 回圈找到最開始的結點
while (node.leftType == 0) {
node = node.left;
}
// 列印當前結點的值
System.out.println(node.value);
// 如果當前結點的右指標指向的是后繼結點，可能后繼結點之后還有后繼結點
while (node.rightType == 1) {
node = node.right;
System.out.println(node.value);
}
node = node.right;
}
}
/**
* 中序遍歷
*/
public void midShow() {
if (root != null) {
root.midShow();
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/186250.html
標籤：其他
上一篇：準備以后都在博客園寫博客了