溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章將為大家詳細講解有關詳解Java中的樹結構，文章內容質量較高，因此小編分享給大家做個參考，希望大家閱讀完這篇文章后對相關知識有一定的了解。
1.SpringMVC，Spring Web MVC是一種基于Java的實現了Web MVC設計模式的請求驅動類型的輕量級Web框架。2.Shiro，Apache Shiro是Java的一個安全框架。3.Mybatis，MyBatis 是支持普通 SQL查詢，存儲過程和高級映射的優秀持久層框架。4.Dubbo，Dubbo是一個分布式服務框架。5.Maven，Maven是個項目管理和構建自動化工具。6.RabbitMQ，RabbitMQ是用Erlang實現的一個高并發高可靠AMQP消息隊列服務器。7.Ehcache，EhCache 是一個純Java的進程內緩存框架。
與線性表表示的一一對應的線性關系不同，樹表示的是數據元素之間更為復雜的非線性關系。
直觀來看，樹是以分支關系定義的層次結構。 樹在客觀世界中廣泛存在，如人類社會的族譜和各種社會組織機構都可以用樹的形象來表示。
簡單來說，樹表示的是1對多的關系。
定義（邏輯結構）：
樹(Tree)是n( n>=0 )個結點的有限集合，沒有結點的樹稱為空樹，在任意一顆非空樹中： 有且僅有一個特定的稱為根(root)的結點 。
當n>1的時，其余結點可分為 m( m>0 ) 個互不相交的有限集T1，T2，…, Tm，其中每一個集合 Ti 本身又是一棵樹，并且稱之為根的子樹。
注意：樹的定義是一個遞歸定義，即在樹的定義中又用到樹的概念。
（1）一個結點的子樹的根，稱為該結點的孩子(兒子)，相應的該結點稱為子樹的根的父親。
（2）沒有孩子的結點稱為樹葉，又叫葉子結點 。(國外, nil叫葉子) 具有相同父親的結點互為兄弟(同胞, 姐妹)。
（3）從結點n1 到 nk 的路徑定義為節點 n1 n2 … nk 的一個序列，使得對于 1 <= i < k，節點 ni是 ni+1 的父親。這條路徑的長是為該路徑上邊的條數，即 k-1。從每一個結點到它自己有一條長為 0 的路徑。注意，在一棵樹中從根到每個結點恰好存在一條路徑。 如果存在從n1到n2的一條路徑，那么n1是n2的一位祖先 ，而n2是n1的一個后裔。如果n1 != n2，那么n1是n2的真祖先, 而n2是n1的真后裔。
（4）結點的層級從根開始定義，根為第一層，根的孩子為第二層。若某結點在第i層，則其孩子就在i+1層。(樹有層級定義)
（5）對任意結點ni，ni的深度為從根到ni的唯一路徑的長。因此，根的深度為0。(深度)
（6）一顆樹的高等于它根的高。一顆樹的深度等于它最深的樹葉的深度; 該深度總是等于這棵樹的高。
（7）性質：如果一棵樹有n個結點，那么它有n-1條邊。(為什么呢?)
每一結點都有一個邊指向它(除了根節點)
每一條邊都指向一個結點
（8） 概念： 度 (圖這種數據結構) 對圖這種數據結構: 每個結點的度: 一般指有幾個結點和我這個結點相關
樹這種數據結構: 度: 一般指有幾個孩子
怎么通過代碼來模擬一個樹
集合類： 數據容器
數組 鏈表, 數組+鏈表
數據結構表現形式：樹
如果非要用數組存儲一棵樹的話, 也可以, 不過會存在各種問題。
如果用鏈表存儲一棵樹也會有一些問題( 1, 犧牲內存, 2, 多種結點類型)
（1）經過轉化的樹比較容易存儲: 這種根據下面特點轉化的樹 被稱為 二叉樹。
① 如果一個結點 有孩子, 那么讓他的第一個孩子, 作為這個結點的left子結點。
②如果一個結點有兄弟結點, 那么讓他的兄弟結點, 作為這個結點的right子結點。
概念： 一個樹, 每一個結點最多有兩個孩子, 孩子有嚴格的左右之分
（1）二叉樹具有以下重要性質：
①二叉樹在第i層至多有2的(i-1)次方個節點
②層次為k的二叉樹至多有2的k次方 - 1個節點
（2）對任何一顆二叉樹T，如果其葉子節點數為n0 , 度為2的節點數為n2，則n0 = n2 + 1
（3）具有n個節點的完全二叉樹，樹的高度為log2n (向下取整)。
（4）如果對一顆有n個結點的完全二叉樹的結點按層序從1開始編號，則對任意一結點有：
如果編號i為1，則該結點是二叉樹的根;
如果編號i > 1，則其雙親結點編號為 parent(i) = i/2,
若 2i > n 則該結點沒有左孩子，否則其左孩子的編號為 2i,
若 2i + 1 > n 則該結點沒有右孩子，否則其右孩子的編號為 2i + 1。
（5）二叉樹的父子結點關系: 2倍 或者 2倍+1關系
–> 二叉樹可以用數組存儲 就是根據上述性質(但是一般在實際應用和開發中, 我們一般用鏈表存儲二叉樹)
深度優先遍歷： 棧
（1）先序遍歷：先遍歷根結點, 再遍歷左子樹, 再遍歷右子樹
（2）中序遍歷：先遍歷左子樹, 再遍歷根結點, 再遍歷右子樹
（3）后序遍歷：先遍歷左子樹, 再遍歷右子樹, 再遍歷根結點
廣度優先遍歷： 隊列
樹的廣度優先遍歷一般為層級遍歷。（廣度優先遍歷–>圖的廣度遍歷）
給一些序列(前中后序), 我們還原出一顆樹原本的樣子
Q1: 如果我們只知道前序，中序，后序中的某一種，能否構建出一棵二叉樹？如果能，為什么？如果不能，試著舉出反例。
答： 能構建一顆二叉樹, 但是不能構建出一顆唯一的二叉樹
Q2:如果我們只知道前序，中序，后序中的某兩種，能否構建出一棵唯一的二叉樹？如果能，為什么？如果不能，試著舉出反例。
前序 + 中序 可以–> 前序可以確定根節點, 中序可以根據根節點劃分左右子樹
后序 + 中序 可以–> 后序可以確定根節點, 中序可以根據根節點劃分左右子樹
前序 + 后序, 不可以, 都只能確定根節點
就是在二叉樹的基礎上增減一個限定條件: 對樹中每一個結點 它的左子樹的結點比這個結點都小, 右子樹上的結點比這個結點都大
注意: 遞歸需要注意的事情
1, 遞歸的核心思想: 設計的時候不要考慮開始和結束是怎么回事, 抓住核心邏輯, 局部樣本
2, 注意出口問題: 遞歸要有出口
3, 如果實現一個遞歸方法, 不要讓這個方法被外界直接訪問(沒有語法問題, 只不過操作行為比較危險)
4, 一定要注意問題規模。
/**
* @author: Mr.Du
* @description: 二叉搜索樹
* @date: 2021/05/04 17:00
*/
public class MyBSTree<T extends Comparable<T>> {
private Node root;//二叉搜索樹根節點
private int size;//二叉搜索樹結點個數
//添加結點
public boolean add(T value) {
// 對于一個二叉搜索樹來講我們不存儲null: null不能比較大小
if (value == null)
throw new IllegalArgumentException("The param is null");
//判斷原本的樹是否為空
if (root == null) {
// 如果原本的樹是一個空樹, 那么這個添加的元素就是根節點
root = new Node(value, null, null);
size++;
return true;
}
//目前來看，樹不空，值也不是null
Node index = root;//比較結點
Node indexF = null;//比較結點的父結點
int com = 0;//比較value大小結果
while (index != null) {
// 把要存儲的值, 和遍歷結點作比較, 進一步確定相對于mid存儲的位置
com = index.value.compareTo(value);
indexF = index;
if (com > 0) {
index = index.left;
} else if (com < 0) {
index = index.right;
} else {
// com = 0
// value 和 index存儲的值一樣
// 對于重復元素的處理方式
// 理論上:
// 1, 計數法: 對于每一個結點都額外維護一個參數, 記錄這個元素的重復數量
// 2, 拉鏈法: 在某個結點位置維護一個鏈表, 用一個鏈表代表一個結點
// 3, 修正的BST: 如果比較的過程中發現了重復元素, 向左存儲
// 實際上:
// 不讓存
return false;
}
}
if (com > 0) {
indexF.left = new Node(value, null, null);
} else {
indexF.right = new Node(value, null, null);
}
size++;
return true;
}
//是否存在指定值
public boolean contains(T value) {
// 對于一個二叉搜索樹來講我們不存儲null: null不能比較大小
if (value == null)
throw new IllegalArgumentException("The param is null");
Node index = root;
int com = 0;
while (index != null) {
com = value.compareTo(index.value);
if (com > 0) {
index = index.right;
} else if (com < 0) {
index = index.left;
} else return true;
}
//如果代碼走到這個位置, 意味著上述循環跳出條件是: index == null 意味著沒有這個元素
return false;
}
//遞歸方法刪除二叉搜索樹結點
public boolean removeByRecursive(T value){
int oldSize = size;
root = removeByRe(root,value);
return size<oldSize;
}
// 實現以root為根節點的子樹上刪除值為value的結點
private Node removeByRe(Node root,T value){
if (root == null) return null;
int com = value.compareTo(root.value);
if (com>0){
//如果value存在, 在right子樹上
root.right = removeByRe(root.right,value);
return root;
}else if (com<0){
//如果value存在, 在left子樹上
root.left = removeByRe(root.left,value);
return root;
}else{
// 找到了要刪除的結點
if (root.left!=null&&root.right!=null){
// 刪除的結點是雙分支結點
// 獲取right子樹的最小值
Node rightMin = root.right;
while (rightMin.left!=null){
rightMin = rightMin.left;
}
//替換
root.value = rightMin.value;
// 接下來, 去right子樹上刪除rightMin(此時rightMin一定不是雙分支結點)
// 遞歸調用刪除方法, 在這個root的right子樹上刪除這個替換值
root.right = removeByRe(root.right,root.value);
return root;
}
// 刪除的是葉子或者單分支
Node node = root.left != null? root.left : root.right;
size--;
return node;
}
}
//非遞歸方法刪除二叉搜索樹結點
public boolean removeByNonRecursive(T value) {
//不存儲null: null不能比較大小
if (value == null)
throw new IllegalArgumentException("The param is null");
/*
思路:
先找到要刪除的結點
判斷要刪除的結點是不是雙分支: 如果是雙分支, 先替換
刪除單分支或者葉子
*/
Node index = root;
Node indexF = null;
int com;
while (index != null) {
com = value.compareTo(index.value);
if (com > 0) {
indexF = index;
index = index.right;
} else if (com < 0) {
indexF = index;
index = index.left;
} else
break;
}
// indexF 是要刪除結點的父結點
// index 是找到的要刪除的結點
//如果index是null,沒有包含刪除的元素，返回false
if (index == null)
return false;
//到這里，說明包含需要刪除的元素
if (index.left != null && index.right != null) {
//去right子樹找一個最小值, 替換這個刪除結點
Node rightMin = index.right;
//替換結點的父結點
Node rightMinF = index;
//找index.right子樹的最小值, 最left的元素
while (rightMin.left != null) {
rightMinF = rightMin;
rightMin = rightMinF.left;
}
//到達這里：rightMin.left=null
//用查找的right子樹上的最小值, 替換這個要刪除的雙分支結點
index.value = rightMin.value;
//將替換結點設置為后面需要刪除的單分支結點
indexF = rightMinF;
index = rightMin;
}
// 有可能原本就是葉子或者單分支
// 也有可能雙分支已經替換了, 現在要刪除的是哪個替換了的, 葉子或者單分支
// 必定是個葉子或者單分支: index
// 同時我們還記錄了index 的 父結點 indexF
//尋找index的兒子結點ch:
// 如果index是葉子 ,那么ch = null
// 如果index是單分支, ch = 不為null單分支子結點
Node ch = index.left != null ? index.left : index.right;
// 如果刪除的是根節點, 并且根節點還是個單分支的結點, 對于上述代碼會導致midF = null
if (indexF == null) {
root = ch;
size--;
return true;
}
//刪除結點
if (indexF.left == index) {
indexF.left = ch;
} else
indexF.right = ch;
size--;
return true;
}
//用棧來實現先中后序遍歷：
//①先序
public List<T> preOrder() {
//保存遍歷結果
List<T> list = new ArrayList<>();
//用棧來臨時存儲結點
MyLinkedStack<Node> stack = new MyLinkedStack<>();
//根節點入棧
stack.push(root);
while (!stack.isEmpty()) {
Node pop = stack.pop();
list.add(pop.value);
if (pop.right != null)
stack.push(pop.right);
if (pop.left != null)
stack.push(pop.left);
}
return list;
}
//②中序
public List<T> inOrder() {
Stack<Node> stack = new Stack<>();
List<T> list = new ArrayList<>();
Node index = root;
while (index != null || !stack.empty()) {
while (index != null) {
stack.push(index);
index = index.left;
}
Node pop = stack.pop();
list.add(pop.value);
index = pop.right;
}
return list;
}
//③后序
public List<T> postOrder() {
Stack<Node> stack = new Stack<>();
List<T> list = new ArrayList<>();
stack.push(root);
while (!stack.empty()) {
Node pop = stack.pop();
list.add(0, pop.value);
if (pop.left != null)
stack.push(pop.left);
if (pop.right != null)
stack.push(pop.right);
}
return list;
}
//用遞歸來實現先中后序遍歷
//①先序
public List<T> preOrderRecursive() {
List<T> list = new LinkedList<>();
preRecursive(list, root);
return list;
}
// 先序：根 左 右
private void preRecursive(List<T> list, Node node) {
if (node == null)
return;
list.add(node.value);
preRecursive(list, node.left);
preRecursive(list, node.right);
}
//②中序
public List<T> inOrderRecursive() {
List<T> list = new LinkedList<>();
inRecursive(list, root);
return list;
}
// 中序遍歷： 左 根 右
private void inRecursive(List<T> list, Node node) {
if (node == null)
return;
inRecursive(list, node.left);
list.add(node.value);
inRecursive(list, node.right);
}
//③ 后序遍歷
public List<T> postOrderRecursive() {
List<T> list = new LinkedList<>();
postRecursive(list, root);
return list;
}
// 后序： 左 右 根
private void postRecursive(List<T> list, Node node) {
if (node == null)
return;
preRecursive(list, node.left);
preRecursive(list, node.right);
list.add(node.value);
}
// 層級： 廣度優先搜索(BFS)
public List<T> levOrder() {
List<T> list = new ArrayList<>();
Queue<Node> queue = new LinkedBlockingQueue<>();
//根節點入隊列
queue.offer(root);
while (!queue.isEmpty()) {
//出隊列元素
Node poll = queue.poll();
//遍歷
list.add(poll.value);
//把出隊列元素的左右子節點入隊列
if (poll.left != null)
queue.offer(poll.left);
if (poll.right != null)
queue.offer(poll.right);
}
return list;
}
// 建樹: 給定前中序, 或者給定中后序, 構建出一棵二叉樹
// 中序 [-50, -25, -20, -10, -5, 1, 2, 7, 10, 25, 30, 100]
// 后序 [-20, -25, -50, -10, -5, 7, 2, 25, 30, 100, 10, 1]
public Node buildTreeByInAndPostOrder(List<T> inOrder, List<T> postOrder) {
Node treeRoot = buildTreeByInAndPostOrder2(inOrder, postOrder);
return treeRoot;
}
private Node buildTreeByInAndPostOrder2(List<T> inOrder, List<T> postOrder) {
if (inOrder.size() == 0) return null;
if (inOrder.size() == 1) return new Node(inOrder.get(0), null, null);
//找根結點: 后序的最后一個元素
T rootValue = postOrder.get(postOrder.size() - 1);
//獲得根節點在中序的位置
int rootAtInOrderIndex = inOrder.indexOf(rootValue);
// 左子樹的中序(中序中切割): 0 ~ rootAtInOrderIndex-1
// 左子樹的后序(后序中切割): 0 ~ rootAtInOrderIndex -1
// 右子樹的中序(中序中切割): rootAtInOrderIndex + 1 ~ size -1
// 右子樹的后序(后序中切割): rootAtInOrderIndex ~ size - 2
//左子樹
//subList()：左閉右開
List<T> leftInOrder = inOrder.subList(0, rootAtInOrderIndex);
List<T> leftPostOrder = postOrder.subList(0, rootAtInOrderIndex);
//右子樹
//subList()：左閉右開
List<T> rightInOrder = inOrder.subList(rootAtInOrderIndex + 1, inOrder.size());
List<T> rightPostOrder = postOrder.subList(rootAtInOrderIndex, postOrder.size() - 1);
//構建這次遞歸的根節點
Node node = new Node(rootValue, null, null);
// 用遞歸方法處理, 獲得左子樹
node.left = buildTreeByInAndPostOrder2(leftInOrder, leftPostOrder);
// 用遞歸方法處理, 獲得右子樹
node.right = buildTreeByInAndPostOrder2(rightInOrder, rightPostOrder);
return node;
}
// 中序 [-50, -25, -20, -10, -5, 1, 2, 7, 10, 25, 30, 100]
// 前序 1 -5 -10 -50 -25 -20 10 2 7 100 30 25
public Node buildTreeByInAndPreOrder(List<T> inOrder, List<T> preOrder) {
Node treeRoot = buildTreeByInAndPreOrder2(inOrder, preOrder);
return treeRoot;
}
private Node buildTreeByInAndPreOrder2(List<T> inOrder, List<T> preOrder) {
if (inOrder.size() == 0) return null;
if (inOrder.size() == 1) return new Node(inOrder.get(0), null, null);
T rootValue = preOrder.get(0);
int rootAtInOrderIndex = inOrder.indexOf(rootValue);
//左子樹
//subList()：左閉右開
List<T> leftInOrder = inOrder.subList(0, rootAtInOrderIndex);
List<T> leftPreOrder = preOrder.subList(1, rootAtInOrderIndex + 1);
//右子樹
//subList()：左閉右開
List<T> rightInOrder = inOrder.subList(rootAtInOrderIndex+1,inOrder.size());
List<T> rightPreOrder = preOrder.subList(rootAtInOrderIndex+1,preOrder.size());
Node node = new Node(rootValue,null,null);
node.left = buildTreeByInAndPreOrder2(leftInOrder,leftPreOrder);
node.right = buildTreeByInAndPreOrder2(rightInOrder,rightPreOrder);
return node;
}
//判空
public boolean isEmpty() {
return size == 0;
}
//返回結點個數
public int size() {
return size;
}
class Node {
T value;
Node left;
Node right;
public Node(T value, Node left, Node right) {
this.value = value;
this.left = left;
this.right = right;
}
}
}關于詳解Java中的樹結構就分享到這里了，希望以上內容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
