Java數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)之樹
一、樹
1.1 概念
與線性表表示的一一對應(yīng)的線性關(guān)系不同，樹表示的是數(shù)據(jù)元素之間更為復(fù)雜的非線性關(guān)系。
直觀來看，樹是以分支關(guān)系定義的層次結(jié)構(gòu)。 樹在客觀世界中廣泛存在，如人類社會的族譜和各種社會組織機構(gòu)都可以用樹的形象來表示。
簡單來說，樹表示的是1對多的關(guān)系。
定義（邏輯結(jié)構(gòu)）：
樹(Tree)是n( n>=0 )個結(jié)點的有限集合，沒有結(jié)點的樹稱為空樹，在任意一顆非空樹中： 有且僅有一個特定的稱為根(root)的結(jié)點 。
當(dāng)n>1的時，其余結(jié)點可分為 m( m>0 ) 個互不相交的有限集T1，T2，…, Tm，其中每一個集合 Ti 本身又是一棵樹，并且稱之為根的子樹。
注意：樹的定義是一個遞歸定義，即在樹的定義中又用到樹的概念。
1.2 術(shù)語
（1）一個結(jié)點的子樹的根，稱為該結(jié)點的孩子(兒子)，相應(yīng)的該結(jié)點稱為子樹的根的父親。
（2）沒有孩子的結(jié)點稱為樹葉，又叫葉子結(jié)點 。(國外, nil叫葉子) 具有相同父親的結(jié)點互為兄弟(同胞, 姐妹)。
（3）從結(jié)點n1 到 nk 的路徑定義為節(jié)點 n1 n2 … nk 的一個序列，使得對于 1 <= i < k，節(jié)點 ni是 ni+1 的父親。這條路徑的長是為該路徑上邊的條數(shù)，即 k-1。從每一個結(jié)點到它自己有一條長為 0 的路徑。注意，在一棵樹中從根到每個結(jié)點恰好存在一條路徑。 如果存在從n1到n2的一條路徑，那么n1是n2的一位祖先 ，而n2是n1的一個后裔。如果n1 != n2，那么n1是n2的真祖先, 而n2是n1的真后裔。
（4）結(jié)點的層級從根開始定義，根為第一層，根的孩子為第二層。若某結(jié)點在第i層，則其孩子就在i+1層。(樹有層級定義)
（5）對任意結(jié)點ni，ni的深度為從根到ni的唯一路徑的長。因此，根的深度為0。(深度)
（6）一顆樹的高等于它根的高。一顆樹的深度等于它最深的樹葉的深度; 該深度總是等于這棵樹的高。
（7）性質(zhì)：如果一棵樹有n個結(jié)點，那么它有n-1條邊。(為什么呢?)
每一結(jié)點都有一個邊指向它(除了根節(jié)點)
每一條邊都指向一個結(jié)點
（8） 概念： 度 (圖這種數(shù)據(jù)結(jié)構(gòu)) 對圖這種數(shù)據(jù)結(jié)構(gòu): 每個結(jié)點的度: 一般指有幾個結(jié)點和我這個結(jié)點相關(guān)
樹這種數(shù)據(jù)結(jié)構(gòu): 度: 一般指有幾個孩子
1.3 樹的實現(xiàn)
怎么通過代碼來模擬一個樹
集合類： 數(shù)據(jù)容器
數(shù)組 鏈表, 數(shù)組+鏈表
數(shù)據(jù)結(jié)構(gòu)表現(xiàn)形式：樹
1.3.1 用數(shù)組來實現(xiàn)一棵樹？
如果非要用數(shù)組存儲一棵樹的話, 也可以, 不過會存在各種問題。
1.3.2 用鏈表實現(xiàn)一棵樹？
如果用鏈表存儲一棵樹也會有一些問題( 1, 犧牲內(nèi)存, 2, 多種結(jié)點類型)
1.3.3 樹的轉(zhuǎn)化
（1）經(jīng)過轉(zhuǎn)化的樹比較容易存儲: 這種根據(jù)下面特點轉(zhuǎn)化的樹 被稱為 二叉樹。
① 如果一個結(jié)點 有孩子, 那么讓他的第一個孩子, 作為這個結(jié)點的left子結(jié)點。
②如果一個結(jié)點有兄弟結(jié)點, 那么讓他的兄弟結(jié)點, 作為這個結(jié)點的right子結(jié)點。
1.4 二叉樹
概念： 一個樹, 每一個結(jié)點最多有兩個孩子, 孩子有嚴(yán)格的左右之分
1.4.1 二叉樹的性質(zhì)
（1）二叉樹具有以下重要性質(zhì)：
①二叉樹在第i層至多有2的(i-1)次方個節(jié)點
②層次為k的二叉樹至多有2的k次方 - 1個節(jié)點
（2）對任何一顆二叉樹T，如果其葉子節(jié)點數(shù)為n0 , 度為2的節(jié)點數(shù)為n2，則n0 = n2 + 1
（3）具有n個節(jié)點的完全二叉樹，樹的高度為log2n (向下取整)。
（4）如果對一顆有n個結(jié)點的完全二叉樹的結(jié)點按層序從1開始編號，則對任意一結(jié)點有：
如果編號i為1，則該結(jié)點是二叉樹的根;
如果編號i > 1，則其雙親結(jié)點編號為 parent(i) = i/2,
若 2i > n 則該結(jié)點沒有左孩子，否則其左孩子的編號為 2i,
若 2i + 1 > n 則該結(jié)點沒有右孩子，否則其右孩子的編號為 2i + 1。
（5）二叉樹的父子結(jié)點關(guān)系: 2倍 或者 2倍+1關(guān)系
–> 二叉樹可以用數(shù)組存儲 就是根據(jù)上述性質(zhì)(但是一般在實際應(yīng)用和開發(fā)中, 我們一般用鏈表存儲二叉樹)
1.4.2 二叉樹的遍歷
深度優(yōu)先遍歷： 棧
（1）先序遍歷：先遍歷根結(jié)點, 再遍歷左子樹, 再遍歷右子樹
（2）中序遍歷：先遍歷左子樹, 再遍歷根結(jié)點, 再遍歷右子樹
（3）后序遍歷：先遍歷左子樹, 再遍歷右子樹, 再遍歷根結(jié)點
廣度優(yōu)先遍歷： 隊列
樹的廣度優(yōu)先遍歷一般為層級遍歷。（廣度優(yōu)先遍歷–>圖的廣度遍歷）
1.4.3 二叉樹的建樹
給一些序列(前中后序), 我們還原出一顆樹原本的樣子
Q1: 如果我們只知道前序，中序，后序中的某一種，能否構(gòu)建出一棵二叉樹？如果能，為什么？如果不能，試著舉出反例。
答： 能構(gòu)建一顆二叉樹, 但是不能構(gòu)建出一顆唯一的二叉樹
Q2:如果我們只知道前序，中序，后序中的某兩種，能否構(gòu)建出一棵唯一的二叉樹？如果能，為什么？如果不能，試著舉出反例。
前序 + 中序 可以–> 前序可以確定根節(jié)點, 中序可以根據(jù)根節(jié)點劃分左右子樹
后序 + 中序 可以–> 后序可以確定根節(jié)點, 中序可以根據(jù)根節(jié)點劃分左右子樹
前序 + 后序, 不可以, 都只能確定根節(jié)點
二、BST(二叉查找樹, 二分查找樹, 二叉排序樹)
就是在二叉樹的基礎(chǔ)上增減一個限定條件: 對樹中每一個結(jié)點 它的左子樹的結(jié)點比這個結(jié)點都小, 右子樹上的結(jié)點比這個結(jié)點都大
2.1 代碼實現(xiàn)
注意: 遞歸需要注意的事情
1, 遞歸的核心思想: 設(shè)計的時候不要考慮開始和結(jié)束是怎么回事, 抓住核心邏輯, 局部樣本
2, 注意出口問題: 遞歸要有出口
3, 如果實現(xiàn)一個遞歸方法, 不要讓這個方法被外界直接訪問(沒有語法問題, 只不過操作行為比較危險)
4, 一定要注意問題規(guī)模。
/**
* @author: Mr.Du
* @description: 二叉搜索樹
* @date: 2021/05/04 17:00
*/
public class MyBSTree<T extends Comparable<T>> {
private Node root;//二叉搜索樹根節(jié)點
private int size;//二叉搜索樹結(jié)點個數(shù)
//添加結(jié)點
public boolean add(T value) {
// 對于一個二叉搜索樹來講我們不存儲null: null不能比較大小
if (value == null)
throw new IllegalArgumentException("The param is null");
//判斷原本的樹是否為空
if (root == null) {
// 如果原本的樹是一個空樹, 那么這個添加的元素就是根節(jié)點
root = new Node(value, null, null);
size++;
return true;
}
//目前來看，樹不空，值也不是null
Node index = root;//比較結(jié)點
Node indexF = null;//比較結(jié)點的父結(jié)點
int com = 0;//比較value大小結(jié)果
while (index != null) {
// 把要存儲的值, 和遍歷結(jié)點作比較, 進(jìn)一步確定相對于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存儲的值一樣
// 對于重復(fù)元素的處理方式
// 理論上:
// 1, 計數(shù)法: 對于每一個結(jié)點都額外維護(hù)一個參數(shù), 記錄這個元素的重復(fù)數(shù)量
// 2, 拉鏈法: 在某個結(jié)點位置維護(hù)一個鏈表, 用一個鏈表代表一個結(jié)點
// 3, 修正的BST: 如果比較的過程中發(fā)現(xiàn)了重復(fù)元素, 向左存儲
// 實際上:
// 不讓存
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;
}
//如果代碼走到這個位置, 意味著上述循環(huán)跳出條件是: index == null 意味著沒有這個元素
return false;
}
//遞歸方法刪除二叉搜索樹結(jié)點
public boolean removeByRecursive(T value){
int oldSize = size;
root = removeByRe(root,value);
return size<oldSize;
}
// 實現(xiàn)以root為根節(jié)點的子樹上刪除值為value的結(jié)點
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{
// 找到了要刪除的結(jié)點
if (root.left!=null&&root.right!=null){
// 刪除的結(jié)點是雙分支結(jié)點
// 獲取right子樹的最小值
Node rightMin = root.right;
while (rightMin.left!=null){
rightMin = rightMin.left;
}
//替換
root.value = rightMin.value;
// 接下來, 去right子樹上刪除rightMin(此時rightMin一定不是雙分支結(jié)點)
// 遞歸調(diào)用刪除方法, 在這個root的right子樹上刪除這個替換值
root.right = removeByRe(root.right,root.value);
return root;
}
// 刪除的是葉子或者單分支
Node node = root.left != null? root.left : root.right;
size--;
return node;
}
}
//非遞歸方法刪除二叉搜索樹結(jié)點
public boolean removeByNonRecursive(T value) {
//不存儲null: null不能比較大小
if (value == null)
throw new IllegalArgumentException("The param is null");
/*
思路:
先找到要刪除的結(jié)點
判斷要刪除的結(jié)點是不是雙分支: 如果是雙分支, 先替換
刪除單分支或者葉子
*/
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 是要刪除結(jié)點的父結(jié)點
// index 是找到的要刪除的結(jié)點
//如果index是null,沒有包含刪除的元素，返回false
if (index == null)
return false;
//到這里，說明包含需要刪除的元素
if (index.left != null && index.right != null) {
//去right子樹找一個最小值, 替換這個刪除結(jié)點
Node rightMin = index.right;
//替換結(jié)點的父結(jié)點
Node rightMinF = index;
//找index.right子樹的最小值, 最left的元素
while (rightMin.left != null) {
rightMinF = rightMin;
rightMin = rightMinF.left;
}
//到達(dá)這里：rightMin.left=null
//用查找的right子樹上的最小值, 替換這個要刪除的雙分支結(jié)點
index.value = rightMin.value;
//將替換結(jié)點設(shè)置為后面需要刪除的單分支結(jié)點
indexF = rightMinF;
index = rightMin;
}
// 有可能原本就是葉子或者單分支
// 也有可能雙分支已經(jīng)替換了, 現(xiàn)在要刪除的是哪個替換了的, 葉子或者單分支
// 必定是個葉子或者單分支: index
// 同時我們還記錄了index 的 父結(jié)點 indexF
//尋找index的兒子結(jié)點ch:
// 如果index是葉子 ,那么ch = null
// 如果index是單分支, ch = 不為null單分支子結(jié)點
Node ch = index.left != null ? index.left : index.right;
// 如果刪除的是根節(jié)點, 并且根節(jié)點還是個單分支的結(jié)點, 對于上述代碼會導(dǎo)致midF = null
if (indexF == null) {
root = ch;
size--;
return true;
}
//刪除結(jié)點
if (indexF.left == index) {
indexF.left = ch;
} else
indexF.right = ch;
size--;
return true;
}
//用棧來實現(xiàn)先中后序遍歷：
//①先序
public List<T> preOrder() {
//保存遍歷結(jié)果
List<T> list = new ArrayList<>();
//用棧來臨時存儲結(jié)點
MyLinkedStack<Node> stack = new MyLinkedStack<>();
//根節(jié)點入棧
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;
}
//用遞歸來實現(xiàn)先中后序遍歷
//①先序
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);
}
// 層級： 廣度優(yōu)先搜索(BFS)
public List<T> levOrder() {
List<T> list = new ArrayList<>();
Queue<Node> queue = new LinkedBlockingQueue<>();
//根節(jié)點入隊列
queue.offer(root);
while (!queue.isEmpty()) {
//出隊列元素
Node poll = queue.poll();
//遍歷
list.add(poll.value);
//把出隊列元素的左右子節(jié)點入隊列
if (poll.left != null)
queue.offer(poll.left);
if (poll.right != null)
queue.offer(poll.right);
}
return list;
}
// 建樹: 給定前中序, 或者給定中后序, 構(gòu)建出一棵二叉樹
// 中序 [-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);
//找根結(jié)點: 后序的最后一個元素
T rootValue = postOrder.get(postOrder.size() - 1);
//獲得根節(jié)點在中序的位置
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);
//構(gòu)建這次遞歸的根節(jié)點
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;
}
//返回結(jié)點個數(shù)
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;
}
}
}
到此這篇關(guān)于Java數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)之樹的文章就介紹到這了,更多相關(guān)Java樹內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
springboot集成Swagger的方法(讓你擁有屬于自己的api管理器)
在大型的項目中，如果你有非常多的接口需要統(tǒng)一管理，或者需要進(jìn)行接口測試，那么我們通常會在繁雜地api中找到需要進(jìn)行測試或者管理的接口,接下來通過本文給大家介紹springboot集成Swagger的方法讓你擁有屬于自己的api管理器，感興趣的朋友一起看看吧2021-11-11
一文帶你掌握J(rèn)ava8中函數(shù)式接口的使用和自定義
函數(shù)式接口是?Java?8?引入的一種接口,用于支持函數(shù)式編程,下面我們就來深入探討函數(shù)式接口的概念、用途以及如何創(chuàng)建和使用函數(shù)式接口吧2023-08-08
本篇文章意在幫助大家了解CRM的一些基本概念，介紹相關(guān)業(yè)務(wù)，后文也將會將基于筆者所在公司的業(yè)務(wù)詳細(xì)闡述CRM各模塊，感興趣的朋友快來看看吧2021-11-11
這篇文章主要為大家詳細(xì)介紹了JavaWeb實現(xiàn)簡單文件上傳功能，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-06-06
使用Jenkins配置Git+Maven的自動化構(gòu)建的方法
這篇文章主要介紹了使用Jenkins配置Git+Maven的自動化構(gòu)建的方法，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-01-01
Java中的HashMap和Hashtable區(qū)別解析
這篇文章主要介紹了Java中的HashMap和Hashtable區(qū)別解析,HashMap和Hashtable都實現(xiàn)了Map接口,但決定用哪一個之前先要弄清楚它們之間的區(qū)別,主要的區(qū)別有線程安全性、同步和速度,需要的朋友可以參考下2023-11-11
Java五種方式實現(xiàn)多線程循環(huán)打印問題
本文主要介紹了Java五種方式實現(xiàn)多線程循環(huán)打印問題，文中通過示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-12-12
經(jīng)常需要提供接口與用戶交互(獲取數(shù)據(jù)、上傳數(shù)據(jù)等),由于這個過程需要用戶進(jìn)行相關(guān)的操作,為了避免出現(xiàn)一些錯誤的數(shù)據(jù)等,一般需要對數(shù)據(jù)進(jìn)行校驗,下面這篇文章主要給大家介紹了關(guān)于SpringBoot各種參數(shù)校驗的相關(guān)資料,需要的朋友可以參考下2022-03-03
這篇文章主要為大家介紹了SpringIOC容器Bean的作用域及生命周期實例，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-05-05
Java數(shù)據(jù)導(dǎo)出功能之導(dǎo)出Excel文件實例
這篇文章主要介紹了Java數(shù)據(jù)導(dǎo)出功能之導(dǎo)出Excel文件實例,本文給出了jar包的下載地址,并給出了導(dǎo)出Excel文件代碼實例,需要的朋友可以參考下2015-06-06