Java數(shù)據(jù)結構學習之樹
更新時間：2021年05月07日 09:44:20 作者：愿美夢成真
這篇文章主要介紹了Java數(shù)據(jù)結構學習之樹,文中有非常詳細的代碼示例,對正在學習java數(shù)據(jù)結構的小伙伴們有非常好的幫助,需要的朋友可以參考下
一、樹
1.1 概念
與線性表表示的一一對應的線性關系不同，樹表示的是數(shù)據(jù)元素之間更為復雜的非線性關系。
直觀來看，樹是以分支關系定義的層次結構。 樹在客觀世界中廣泛存在，如人類社會的族譜和各種社會組織機構都可以用樹的形象來表示。
簡單來說，樹表示的是1對多的關系。
定義（邏輯結構）：
樹(Tree)是n( n>=0 )個結點的有限集合，沒有結點的樹稱為空樹，在任意一顆非空樹中： 有且僅有一個特定的稱為根(root)的結點 。
當n>1的時，其余結點可分為 m( m>0 ) 個互不相交的有限集T1，T2，…, Tm，其中每一個集合 Ti 本身又是一棵樹，并且稱之為根的子樹。
注意：樹的定義是一個遞歸定義，即在樹的定義中又用到樹的概念。
1.2 術語
（1）一個結點的子樹的根，稱為該結點的孩子(兒子)，相應的該結點稱為子樹的根的父親。
（2）沒有孩子的結點稱為樹葉，又叫葉子結點 。(國外, nil叫葉子) 具有相同父親的結點互為兄弟(同胞, 姐妹)。
（3）從結點n1 到 nk 的路徑定義為節(jié)點 n1 n2 … nk 的一個序列，使得對于 1 <= i < k，節(jié)點 ni是 ni+1 的父親。這條路徑的長是為該路徑上邊的條數(shù)，即 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條邊。(為什么呢?)
每一結點都有一個邊指向它(除了根節(jié)點)
每一條邊都指向一個結點
（8） 概念： 度 (圖這種數(shù)據(jù)結構) 對圖這種數(shù)據(jù)結構: 每個結點的度: 一般指有幾個結點和我這個結點相關
樹這種數(shù)據(jù)結構: 度: 一般指有幾個孩子
1.3 樹的實現(xiàn)
怎么通過代碼來模擬一個樹
集合類： 數(shù)據(jù)容器
數(shù)組 鏈表, 數(shù)組+鏈表
數(shù)據(jù)結構表現(xiàn)形式：樹
1.3.1 用數(shù)組來實現(xiàn)一棵樹？
如果非要用數(shù)組存儲一棵樹的話, 也可以, 不過會存在各種問題。
1.3.2 用鏈表實現(xiàn)一棵樹？
如果用鏈表存儲一棵樹也會有一些問題( 1, 犧牲內存, 2, 多種結點類型)
1.3.3 樹的轉化
（1）經(jīng)過轉化的樹比較容易存儲: 這種根據(jù)下面特點轉化的樹 被稱為 二叉樹。
① 如果一個結點 有孩子, 那么讓他的第一個孩子, 作為這個結點的left子結點。
②如果一個結點有兄弟結點, 那么讓他的兄弟結點, 作為這個結點的right子結點。
1.4 二叉樹
概念： 一個樹, 每一個結點最多有兩個孩子, 孩子有嚴格的左右之分
1.4.1 二叉樹的性質
（1）二叉樹具有以下重要性質：
①二叉樹在第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個結點的完全二叉樹的結點按層序從1開始編號，則對任意一結點有：
如果編號i為1，則該結點是二叉樹的根;
如果編號i > 1，則其雙親結點編號為 parent(i) = i/2,
若 2i > n 則該結點沒有左孩子，否則其左孩子的編號為 2i,
若 2i + 1 > n 則該結點沒有右孩子，否則其右孩子的編號為 2i + 1。
（5）二叉樹的父子結點關系: 2倍 或者 2倍+1關系
–> 二叉樹可以用數(shù)組存儲 就是根據(jù)上述性質(但是一般在實際應用和開發(fā)中, 我們一般用鏈表存儲二叉樹)
1.4.2 二叉樹的遍歷
深度優(yōu)先遍歷： 棧
（1）先序遍歷：先遍歷根結點, 再遍歷左子樹, 再遍歷右子樹
（2）中序遍歷：先遍歷左子樹, 再遍歷根結點, 再遍歷右子樹
（3）后序遍歷：先遍歷左子樹, 再遍歷右子樹, 再遍歷根結點
廣度優(yōu)先遍歷： 隊列
樹的廣度優(yōu)先遍歷一般為層級遍歷。（廣度優(yōu)先遍歷–>圖的廣度遍歷）
1.4.3 二叉樹的建樹
給一些序列(前中后序), 我們還原出一顆樹原本的樣子
Q1: 如果我們只知道前序，中序，后序中的某一種，能否構建出一棵二叉樹？如果能，為什么？如果不能，試著舉出反例。
答： 能構建一顆二叉樹, 但是不能構建出一顆唯一的二叉樹
Q2:如果我們只知道前序，中序，后序中的某兩種，能否構建出一棵唯一的二叉樹？如果能，為什么？如果不能，試著舉出反例。
前序 + 中序 可以–> 前序可以確定根節(jié)點, 中序可以根據(jù)根節(jié)點劃分左右子樹
后序 + 中序 可以–> 后序可以確定根節(jié)點, 中序可以根據(jù)根節(jié)點劃分左右子樹
前序 + 后序, 不可以, 都只能確定根節(jié)點
二、BST(二叉查找樹, 二分查找樹, 二叉排序樹)
就是在二叉樹的基礎上增減一個限定條件: 對樹中每一個結點 它的左子樹的結點比這個結點都小, 右子樹上的結點比這個結點都大
2.1 代碼實現(xiàn)
注意: 遞歸需要注意的事情
1, 遞歸的核心思想: 設計的時候不要考慮開始和結束是怎么回事, 抓住核心邏輯, 局部樣本
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;//二叉搜索樹結點個數(shù)
//添加結點
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;//比較結點
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, 計數(shù)法: 對于每一個結點都額外維護一個參數(shù), 記錄這個元素的重復數(shù)量
// 2, 拉鏈法: 在某個結點位置維護一個鏈表, 用一個鏈表代表一個結點
// 3, 修正的BST: 如果比較的過程中發(fā)現(xiàn)了重復元素, 向左存儲
// 實際上:
// 不讓存
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;
}
//遞歸方法刪除二叉搜索樹結點
public boolean removeByRecursive(T value){
int oldSize = size;
root = removeByRe(root,value);
return size<oldSize;
}
// 實現(xiàn)以root為根節(jié)點的子樹上刪除值為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;
}
// 有可能原本就是葉子或者單分支
// 也有可能雙分支已經(jīng)替換了, 現(xiàn)在要刪除的是哪個替換了的, 葉子或者單分支
// 必定是個葉子或者單分支: index
// 同時我們還記錄了index 的 父結點 indexF
//尋找index的兒子結點ch:
// 如果index是葉子 ,那么ch = null
// 如果index是單分支, ch = 不為null單分支子結點
Node ch = index.left != null ? index.left : index.right;
// 如果刪除的是根節(jié)點, 并且根節(jié)點還是個單分支的結點, 對于上述代碼會導致midF = null
if (indexF == null) {
root = ch;
size--;
return true;
}
//刪除結點
if (indexF.left == index) {
indexF.left = ch;
} else
indexF.right = ch;
size--;
return true;
}
//用棧來實現(xiàn)先中后序遍歷：
//①先序
public List<T> preOrder() {
//保存遍歷結果
List<T> list = new ArrayList<>();
//用棧來臨時存儲結點
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;
}
// 建樹: 給定前中序, 或者給定中后序, 構建出一棵二叉樹
// 中序 [-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);
//獲得根節(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);
//構建這次遞歸的根節(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;
}
//返回結點個數(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;
}
}
}
到此這篇關于Java數(shù)據(jù)結構學習之樹的文章就介紹到這了,更多相關Java樹內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要為大家詳細介紹了java實現(xiàn)多個文件壓縮成壓縮包，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-07-07
大家好，本篇文章主要講的是Java多線程中的Balking模式詳解，感興趣的同學趕快來看一看吧，對你有幫助的話記得收藏一下2022-01-01
這篇文章主要介紹了Java多線程 中斷機制及實例詳解,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2019-09-09
這篇文章主要介紹了關于RequestMapping注解的作用說明，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教。2022-01-01
本文主要介紹了Mybatis自定義攔截器實現(xiàn)權限功能,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2024-12-12
這篇文章主要給大家介紹了Spring中Bean的生命周期和作用域及實現(xiàn)方式的相關資料，文中介紹的非常詳細，對大家具有一定的參考價值，需要的朋友們下面來一起看看吧2021-08-08
Jenkins?Pipline實現(xiàn)及原理示例解析
這篇文章主要為大家介紹了Jenkins?Pipline實現(xiàn)及原理示例解析，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-07-07
這篇文章主要介紹了Scala入門教程詳解,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2019-06-06
下面小編就為大家?guī)硪黄P于集合和字符串的互轉實現(xiàn)方法。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2016-08-08
周末天氣不好，在家無事，把常用排序算法理了一遍，收獲不小，特寫文章紀念。這些算法在學校的時候學過一遍，很多原理都忘記了2013-06-06