溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要講解了“Java中二叉樹的原理和應用”，文中的講解內容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“Java中二叉樹的原理和應用”吧！
在之前的筆記中，我們介紹的鏈表、棧、隊列、數組和字符串都是以線性結構來組織數據的。本篇筆記要介紹的樹采用的是樹狀結構，這是一種非線性的數據組織形式。
樹結構由節點和邊構成，且不存在環。我們曾在線性表型的數據結構中介紹過循環鏈表和循環隊列，這兩種數據結構使得存儲容器中的元素形成一個閉環，具體可參看“數據結構學習筆記”系列的相關博文，鏈接貼在下面：
鏈表：http://www.neiyidaogou.com/article/215278.htm
隊列：http://www.neiyidaogou.com/article/211502.htm
樹狀結構與線性結構最重要的區別在于：樹只能有分叉，不能有閉環。如下圖所示：
樹結構不允許有環其實是樹的層級性決定的。樹結構中最頂端的結點是根節點， 根節點即整棵樹的頂級父節點。除了根節點只有子節點，最底層的節點只有父節點，其余各層的節點都是上層節點的子節點、下層節點的父節點。也就是說，樹中的數據只與其上下層的數據有關，同層數據間不能有直接聯系，這也就是樹結構不能有環的原因。
樹層級的多少往往被描述為樹的高度(height)，由于我們是從上往下觀察樹結構的，因此也被描述為樹的深度(depth)。上面圖示中兩顆樹的深度都是3.
二叉樹顧名思義，即每個父節點最多只有兩個分叉的樹，這是數據結構領域使用頻率極高的一種樹結構，這與我們常常用二元對立的觀點認識世界的思維習慣有關。
二叉樹的結構不僅具有層級性，還具有遞歸性，一個父節點連接左子節點和右子節點，而左右子節點又可以作為父節點再各自連接兩個子節點，以此類推。因此二叉樹是一種層次嵌套的數據結構，除了根節點外，樹中任意一個父節點都能作為一棵子樹的根，位于上層父節點左側的子樹被稱為左子樹，位于右側的子樹被稱為右子樹。
二叉樹體現了人們用二元思維認識自然的方式。筆者的本行是語言學，語言學界主流的對句法結構的分析方法就是類似于二叉樹的二分法。拿漢語的句法結構來說，有主謂、述賓、定中、狀中、述補等基本的結構類型。句法結構具有層次嵌套和遞歸的特點，同時也有對語序的要求，即句法二叉樹中的左右節點的位置并不是任意的。這種分析方法語言學上被稱為層次分析法，如果我們用該方法分析句子“文程同學熱愛編程”，傳統圖示和句法樹圖示分別如下：
二叉樹中有兩個特殊的結構類型：滿二叉樹和完全二叉樹。滿二叉樹的結構特點是除了最后一層外，所有層級的節點都有兩個子節點；完全二叉樹的結構特點是除了最后兩層外，所有層級的節點都有兩個子節點，倒數第二層的子節點（即最后一層節點）全部靠左排列。如下圖所示：
由此可見，滿二叉樹一定是完全二叉樹，完全二叉樹可滿可不滿。這兩種二叉樹體現了我們采用樹狀結構存儲數據時，對于空間利用率的追求。比如我們設計一個深度為n的二叉樹，那么整個二叉樹能容納的最大節點數為2^n-1，滿二叉樹就是達到了最大節點數，用足了二叉樹的容量。完全二叉樹除了n層沒有子節點，除n-1層外各層父節點都充分利用了自己擁有子節點的名額，也算是盡可能做到了對空間的充分利用。
為了更好地理解完全二叉樹的空間利用率，我們看一個非完全二叉樹的例子，如下圖所示：
上圖是一個深度為4的非完全二叉樹，前3層的父節點都預留了左右兩個子節點的位置，然而第二層的第2個結點只使用了右子節點的空間，浪費了左子節點的空間。如果二叉樹的深度很深，其中很多層級的父節點都存在浪費子節點“名額”的現象，那么會造成相當大的空間資源的浪費，二叉樹也失去了“二叉”的意義。但是完全二叉樹最多浪費倒數第二層父節點的子節點名額， 整體上能夠保證較高的空間利用率。
二叉樹的形狀整體上構成一個三角形，最小的二叉樹由一個位于中間的父節點和位于左右兩側的子節點構成，這導致遍歷訪問一棵二叉樹的所有節點有三種順序：前序遍歷（Preorder Traversal , VLR）、中序遍歷（Inorder Traversal , LDR）和后序遍歷（Inorder Traversal , LRD）。
無論哪種遍歷方式，二叉樹都是從上到下、從左到右遍歷的，即從父節點層到子節點層、從左子樹到右子樹。2.1解釋了二叉樹的遞歸性，遍歷二叉樹時采用的也是遞歸(recursion)的方式。對于整棵樹或某一子樹，都是從根開始，先遍歷其左子樹，再遍歷其右子樹；分別遍歷左右子樹時，同樣是從根開始，從左向右遍歷；以此類推，直到遍歷到最后一個右子節點。
如果我們以打印節點數據的方式來表示對節點的訪問，那么前序、中序和后序的區別就在于打印節點的時機不同。前序遍歷的操作順序是打印節點在遍歷左子樹和遍歷右子樹之前，中序遍歷的操作順序是打印節點在遍歷左子樹和遍歷右子樹之間，后序遍歷的操作順序是打印節點在遍歷左子樹和遍歷右子樹之后。子樹遍歷的過程是遞歸實現的。
如果我們想遍歷2.1演示的“文程同學熱愛編程”的句法二叉樹，那么用三種遍歷方法得到的遍歷結果分別如下：
我們用Java語言實現“文程同學熱愛編程”這個句子對應的句法二叉樹，設計思路是：將同層級的父節點（二叉樹及其各子樹的根節點）存入數組中，數組中存入的是結點，包括數據和左右指針，左右指針分別指向位于下一層節點的左右子節點，如果沒有子節點則指針為空指針。
用數組的好處是，可以通過節點所在的索引建立上下層級父節點和子節點的指針聯系。假設父節點在它所在的層級數組中的索引為i，那么左子節點在它所在層級數組中的索引為(i+1)*2-2，右子節點的索引為(i+1)*2-1，即左子節點的索引＋1。
遍歷默認從整棵二叉樹的根節點開始，通過方法的重寫實現默認參數的效果。
準備工作1：MyBinaryTree.java，創建一個二叉樹的類
package com.notes.data_structure6;
import com.notes.data_structure6.NumberOfNodesException;
public class MyBinaryTree {
// 樹的根結點
private Node[] root;
// 樹的深度（當前層級數）
private int depth;
// 將每一層所有的 結點 都存儲在數組中，結點數是 2的 層數 次冪
private Node[] currentLevel;
public MyBinaryTree(String data) {
Node[] rootArray = new Node[] {new Node(data)};
this.root = rootArray;
this.currentLevel = rootArray;
}
// 定義一個結點類
private class Node{
private String data; // 數據
private Node leftNext; // 左指針
private Node rightNext; // 右指針
// 構造方法：Node實例化時傳入數據
public Node(String data) {
this.data = data;
}
}
// 向樹中增加一層結點
public void add(String[] datas) throws NumberOfNodesException {
// 層級數增加1
depth++;
// 新增 層級 的最大結點數
int nodeNum = numberOfNextNodes();
// 如果傳入的 數據數 與 當前層級 最大結點數 不符，拋出異常
if(datas.length != nodeNum) {
throw new NumberOfNodesException("第"+depth+"層最大父節點數為"+nodeNum);
}
// 將傳入的 數據數組 轉換為 結點數組
Node[] newLevel = new Node[nodeNum];
// 當前 層級的 結點數量（新增層級的父）
int nodeNum2 = (int) Math.pow(2, depth-1);
// 讓每一個結點都與上層 父結點 建立連接
for(int i=0;i<nodeNum2;i++) {
// 讓父結點 的左指針 指向 左子結點
int leftIndex = (i+1)*2-2; // 計算左子結點對應的新層級數組的索引
currentLevel[i].leftNext = new Node(datas[leftIndex]); // 建立指針指向
newLevel[leftIndex] = currentLevel[i].leftNext; // 將結點加入新層級結點數組
// 讓父結點 的右指針 指向 右子結點
int rightIndex = leftIndex+1; // 計算右子結點對應的新層級數組的索引
currentLevel[i].rightNext = new Node(datas[rightIndex]); // 建立指針指向
newLevel[rightIndex] = currentLevel[i].rightNext; // 將結點加入新層級結點數組
}
// 讓新增層級的數組成為當前層級的數組
currentLevel = newLevel;
}
// 前序遍歷所有結點
public void preTraversal(Node node) {
if(node==null) {
return;
}
System.out.print(node.data+" ");
preTraversal(node.leftNext);
preTraversal(node.rightNext);
}
// 重寫 前序遍歷 方法，讓遍歷從 根結點 開始
public void preTraversal() {
Node node = root[0];
if(node==null) {
return;
}
// 遞歸時調用帶參數的方法
System.out.print(node.data+" ");
preTraversal(node.leftNext);
preTraversal(node.rightNext);
}
// 中序遍歷所有結點
public void midTraversal(Node node) {
if(node==null) {
return;
}
midTraversal(node.leftNext);
System.out.print(node.data+" ");
midTraversal(node.rightNext);
}
// 重寫中序遍歷 方法，讓遍歷從 根結點 開始
public void midTraversal() {
Node node = root[0];
if(node==null) {
return;
}
// 遞歸時調用帶參數的方法
midTraversal(node.leftNext);
System.out.print(node.data+" ");
midTraversal(node.rightNext);
}
// 后序遍歷所有結點
public void posTraversal(Node node) {
if(node==null) {
return;
}
posTraversal(node.leftNext);
posTraversal(node.rightNext);
System.out.print(node.data+" ");
}
// 重寫后序遍歷 方法，讓遍歷從 根結點 開始
public void posTraversal() {
Node node = root[0];
if(node==null) {
return;
}
// 遞歸時調用帶參數的方法
posTraversal(node.leftNext);
posTraversal(node.rightNext);
System.out.print(node.data+" ");
}
// 查看 新增層級 的最大結點數
public int numberOfNextNodes() {
return (int) Math.pow(2,depth);
}
// 查看 樹 的深度（層級數）
public int getDepth() {
return depth;
}
}準備工作2：NumberOfNodesException.java，為add()方法創建一個自定義異常，如果傳入的數據數與當前層級最大結點數不符，則拋出該異常（如果二叉樹不滿，在數組的相應位置傳入null）。
package com.notes.data_structure6;
public class NumberOfNodesException extends Exception{
public NumberOfNodesException(String message) {
super(message);
}
}句法二叉樹的實現及其遍歷：TreeDemo.java
package com.notes.data_structure6;
public class TreeDemo {
public static void main(String[] args) throws NumberOfNodesException {
// 實例化二叉樹類，并且傳入根節點的數據
MyBinaryTree tree = new MyBinaryTree("句子");
// 加入第一層節點的數據
tree.add(new String[] {"主語","謂語"});
// 加入第二層節點的數據
tree.add(new String[] {"定語","中心語","述語","賓語"});
// 前序遍歷
tree.preTraversal(); // 句子 主語 定語 中心語 謂語 述語 賓語
System.out.println();
// 中序遍歷
tree.midTraversal(); // 定語 主語 中心語 句子 述語 謂語 賓語
System.out.println();
// 后序遍歷
tree.posTraversal(); // 定語 中心語 主語 述語 賓語 謂語 句子
}
}感謝各位的閱讀，以上就是“Java中二叉樹的原理和應用”的內容了，經過本文的學習后，相信大家對Java中二叉樹的原理和應用這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
