文章目錄
- 二叉樹
- 1. 樹形結構
- 1.1 概念
- 1.2 樹的表示形式
- 1.3 樹的應用
- 2. 二叉樹
- 2.1 概念
- 2.2 二叉樹的基本形態
- 2.3 兩種特殊的二叉樹
- 2.4 二叉樹的性質
- 2.5 二叉樹的存盤
- 2.6 二叉樹的遍歷
- 2.7 二叉樹的基本操作
- 第一步: 首先這里我們用窮舉法先來創建一個二叉樹來測驗這些操作.
- 第二步: 用代碼實作3種遍歷二叉樹的方法.
- 第三步: 兩種方法求結點個數
- 第四步: 兩種方法求葉子結點的個數
- 第五步: 求第 k 層結點個數
- 第六步: 查找val所在的位置
- 第七步: 獲取二叉樹的高度
- 第八步: 運行測驗結果
- 2.8 層序遍歷
- a) 層序遍歷代碼實作:
- b) 判斷一棵樹是不是完全二叉樹
- 方法一思路:
- 代碼實作:
- 方法二思路:
- 代碼實作:
- 2.9 前中后序的非遞回實作
- ①前序遍歷 (非遞回)
- ②中序遍歷 (非遞回)
- ③后序遍歷 (非遞回)
二叉樹
1. 樹形結構
1.1 概念
樹是一種非線性的資料結構，它是由n（n>=0）個有限結點組成一個具有層次關系的集合，把它叫做樹是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的，它具有以下的特點：
- 有一個特殊的節點，稱為根節點，根節點沒有前驅節點
- 除根節點外，其余節點被分成M(M > 0)個互不相交的集合T1、T2、…Tm，其中每一個集合 Ti (1 <= i<= m) 又是一棵與樹類似的子樹，每棵子樹的根節點有且只有一個前驅，可以有0個或多個后繼
- 樹是遞回定義的，
節點的度：一個節點含有的子樹的個數稱為該節點的度； 如上圖：A的為6
樹的度：一棵樹中，最大的節點的度稱為樹的度； 如上圖：樹的度為6
葉子節點或終端節點：度為0的節點稱為葉節點； 如上圖：B、C、H、I…等節點為葉節點
雙親節點或父節點：若一個節點含有子節點，則這個節點稱為其子節點的父節點； 如上圖：A是B的父節點孩
子節點或子節點：一個節點含有的子樹的根節點稱為該節點的子節點； 如上圖：B是A的孩子節點
根結點：一棵樹中，沒有雙親結點的結點；如上圖：A
節點的層次：從根開始定義起，根為第1層，根的子節點為第2層，以此類推；
樹的高度或深度：樹中節點的最大層次； 如上圖：樹的高度為4
非終端節點或分支節點：度不為0的節點； 如上圖：D、E、F、G…等節點為分支節點
兄弟節點：具有相同父節點的節點互稱為兄弟節點； 如上圖：B、C是兄弟節點
堂兄弟節點：雙親在同一層的節點互為堂兄弟；如上圖：H、I互為兄弟節點
節點的祖先：從根到該節點所經分支上的所有節點；如上圖：A是所有節點的祖先
子孫：以某節點為根的子樹中任一節點都稱為該節點的子孫，如上圖：所有節點都是A的子孫
森林：由m（m>=0）棵互不相交的樹的集合稱為森林
1.2 樹的表示形式
樹結構相對線性表就比較復雜了，要存盤表示起來就比較麻煩了，實際中樹有很多種表示方式，如：雙親表示法，孩子表示法、孩子兄弟表示法等等，我們這里就簡單的了解其中最常用的孩子兄弟表示法，
class Node {
int value;// 樹中存盤的資料
Node firstChild;// 第一個孩子參考
Node nextBrother;// 下一個兄弟參考
}
1.3 樹的應用
檔案系統管理（目錄和檔案）
2. 二叉樹
2.1 概念
一棵二叉樹是結點的一個有限集合，該集合或者為空，或者是由一個根節點加上兩棵別稱為左子樹和右子樹的二叉
樹組成，
二叉樹的特點：
1. 每個結點最多有兩棵子樹，即二叉樹不存在度大于 2 的結點，
2. 二叉樹的子樹有左右之分，其子樹的次序不能顛倒，因此二叉樹是有序樹，
2.2 二叉樹的基本形態
一般二叉樹都是由以下幾個基本形態結合而形成的，
2.3 兩種特殊的二叉樹
- 滿二叉樹: 一個二叉樹，如果每一個層的結點數都達到最大值，則這個二叉樹就是滿二叉樹，也就是說，如果一個二叉樹的層數為K，且結點總數是 ，則它就是滿二叉樹，
- 完全二叉樹: 完全二叉樹是效率很高的資料結構，完全二叉樹是由滿二叉樹而引出來的，對于深度為K的，有n個結點的二叉樹，當且僅當其每一個結點都與深度為K的滿二叉樹中編號從1至n的結點一一對應時稱之為完全二叉樹， 要注意的是滿二叉樹是一種特殊的完全二叉樹，
2.4 二叉樹的性質
- 若規定根節點的層數為1，則一棵非空二叉樹的第i層上最多有 2i-1 (i>0)個結點
- 若規定只有根節點的二叉樹的深度為1，則深度為K的二叉樹的最大結點數是 2k-1(k>=0)
- 對任何一棵二叉樹, 如果其葉結點個數為 n0, 度為2的非葉結點個數為 n2,則有n0＝n2＋1
- 具有n個結點的完全二叉樹的深度k為 log2(n+1) 上取整
- 對于具有n個結點的完全二叉樹，如果按照從上至下從左至右的順序對所有節點從0開始編號，則對于序號為i的結點有：
若i>0，雙親序號：(i-1)/2；i=0，i為根節點編號，無雙親節點
若2i+1<n，左孩子序號：2i+1，否則無左孩子
若2i+2<n，右孩子序號：2i+2，否則無右孩子
比如：假設一棵完全二叉樹中總共有1000個節點，則該二叉樹中 500 個葉子節點， 500 個非葉子節點， 1 個節點只有左孩子，0個只有右孩子，
2.5 二叉樹的存盤
二叉樹的存盤結構分為：順序存盤和類似于鏈表的鏈式存盤，
順序存盤 存盤的是完全二叉樹
二叉樹的鏈式存盤是通過一個一個的節點參考起來的，常見的表示方式有二叉和三叉表示方式，具體如下：
// 孩子表示法
class Node {
int val;// 資料域
Node left;// 左孩子的參考，常常代表左孩子為根的整棵左子樹
Node right; // 右孩子的參考，常常代表右孩子為根的整棵右子樹
}
// 孩子雙親表示法
class Node {
int val;// 資料域
Node left;// 左孩子的參考，常常代表左孩子為根的整棵左子樹
Node right; // 右孩子的參考，常常代表右孩子為根的整棵右子樹
Node parent; // 當前節點的根節點
}
2.6 二叉樹的遍歷
如果N代表根節點，L代表根節點的左子樹，R代表根節點的右子樹，則根據遍歷根節點的先后次序有以下遍歷方式：
- NLR：前序遍歷(Preorder Traversal 亦稱先序遍歷)——訪問根結點—>根的左子樹—>根的右子樹，
- LNR：中序遍歷(Inorder Traversal)——根的左子樹—>根節點—>根的右子樹，
- LRN：后序遍歷(Postorder Traversal)——根的左子樹—>根的右子樹—>根節點，
2.7 二叉樹的基本操作
第一步: 首先這里我們用窮舉法先來創建一個二叉樹來測驗這些操作.
package BinaryTree;
class TreeNode{
public char val;
public TreeNode left;
public TreeNode right;
public TreeNode(char val){
this.val = val;
}
}
public class BinaryTree {
public TreeNode createTree() {
TreeNode A = new TreeNode('A');
TreeNode B = new TreeNode('B');
TreeNode C = new TreeNode('C');
TreeNode D = new TreeNode('D');
TreeNode E = new TreeNode('E');
TreeNode F = new TreeNode('F');
TreeNode G = new TreeNode('G');
TreeNode H = new TreeNode('H');
A.left = B;
A.right = C;
B.left = D;
B.right = E;
E.right = H;
C.left = F;
C.right = G;
return A;
}
}
此時的二叉樹圖形如圖:
第二步: 用代碼實作3種遍歷二叉樹的方法.
// 前序遍歷
void preOrderTraversal(TreeNode root) {
if (root == null) {
return;
}
System.out.print(root.val + " ");
preOrderTraversal(root.left);
preOrderTraversal(root.right);
}
// 中序遍歷
void inOrderTraversal(TreeNode root){
if(root == null){
return;
}
inOrderTraversal(root.left);
System.out.print(root.val + " ");
inOrderTraversal(root.right);
}
// 后序遍歷
void postOrderTraversal(TreeNode root){
if(root == null){
return;
}
postOrderTraversal(root.left);
postOrderTraversal(root.right);
System.out.print(root.val + " ");
}
第三步: 兩種方法求結點個數
// 遍歷思路-求結點個數
static int size = 0;
void getSize1(TreeNode root){
if(root == null){
return;
}
size++;
getSize1(root.left);
getSize1(root.right);
}
// 子問題思路-求結點個數
int getSize2(TreeNode root){
if(root == null){
return 0;
}
return getSize2(root.left) + getSize2(root.right) + 1;
}
第四步: 兩種方法求葉子結點的個數
// 遍歷思路-求葉子結點個數
static int leafSize = 0;
void getLeafSize1(TreeNode root){
if(root == null){
return ;
}
if(root.left == null && root.right==null){
leafSize++;
}
getLeafSize1(root.left);
getLeafSize1(root.right);
}
// 子問題思路-求葉子結點個數
int getLeafSize2(TreeNode root){
if(root == null){
return 0;
}
if(root.left == null && root.right ==null){
return 1;
}
return getLeafSize2(root.left) + getLeafSize2(root.right);
}
第五步: 求第 k 層結點個數
int getKLevelSize(TreeNode root,int k){
if(root == null){
return 0;
}
if(k == 1){
return 1;
}
return getKLevelSize(root.left,k-1) + getKLevelSize(root.right,k-1) ;
}
第六步: 查找val所在的位置
// 查找 val 所在結點，沒有找到回傳 null
// 按照 根 -> 左子樹 -> 右子樹的順序進行查找
// 一旦找到，立即回傳，不需要繼續在其他位置查找
TreeNode find(TreeNode root, char val){
if(root == null){
return null;
}
if(root.val == val){
return root;
}
TreeNode ret = find(root.left,val);
if(ret != null){
return ret;
}
ret = find(root.right,val);
if(ret != null){
return ret;
}
return null;
}
第七步: 獲取二叉樹的高度
// 獲取二叉樹的高度
int getHeight(TreeNode root){
if(root == null){
return 0;
}
int leftHeight = getHeight(root.left);
int rightHeight = getHeight(root.right);
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
第八步: 運行測驗結果
public static void main(String[] args) {
BinaryTree binaryTree = new BinaryTree();
TreeNode root = binaryTree.createTree();
System.out.print("前序遍歷結果: ");
binaryTree.preOrderTraversal(root);
System.out.println();
System.out.print("中序遍歷結果: ");
binaryTree.inOrderTraversal(root);
System.out.println();
System.out.print("后序遍歷結果: ");
binaryTree.postOrderTraversal(root);
System.out.println();
binaryTree.getSize1(root);
System.out.println("結點數: "+BinaryTree.size);
int ret = binaryTree.getSize2(root);
System.out.println("結點數: "+ret);
binaryTree.getLeafSize1(root);
System.out.println("葉子節點數: "+BinaryTree.leafSize);
int ret1 = binaryTree.getLeafSize2(root);
System.out.println("葉子節點數: "+ret1);
int ret2 = binaryTree.getKLevelSize(root,3);
System.out.println("求k層節點數: "+ret2);
TreeNode b= binaryTree.find(root,'H');
System.out.println(b.val);
System.out.println("求二叉樹的深度: "+binaryTree.getHeight(root));
}
運行結果:
2.8 層序遍歷
設二叉樹的根節點所在層數為1，層序遍歷就是從所在二叉樹的根節點出發，首先訪問第一層的樹根節點，然后從左到右訪問第2層上的節點，接著是第三層的節點，以此類推，自上而下，自左至右逐層訪問樹的結點的程序就是層序遍歷，
a) 層序遍歷代碼實作:
// 層序遍歷
void levelOrderTraversal(TreeNode root){
if(root == null) return ;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
TreeNode top = queue.poll();
System.out.print(top.val+" ");
if(top.left != null)
queue.offer(top.left);
if(top.right != null)
queue.offer(top.right);
}
System.out.println();
}
b) 判斷一棵樹是不是完全二叉樹
方法一思路:
1. 將樹按照層序遍歷的方法,放入佇列中,不同的是將左右節點都放入佇列中,不論節點是否為空都放入
2. 回圈取出隊首元素,如果隊首為null就結束回圈.
3. 如果此時佇列不為空.
①佇列還有節點,那么就不是完全二叉樹
②佇列全是null,那么就是完全二叉樹.
4. 回圈結束那么就是true;
代碼實作:
boolean isCompleteTree(TreeNode root) {
if (root == null) return true;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode top = queue.poll();
//左子樹 和 右子樹 都放入佇列(不論是不是null)
if (top != null) {
queue.offer(top.left);
queue.offer(top.right);
} else {
//如果隊首為空就跳出回圈
break;
}
}
//如果隊不為空,說明是因為break結束的回圈.那么就需要判斷隊里的元素
while (!queue.isEmpty()) {
TreeNode cur = queue.peek();
//如果隊首為空,就出隊
if (cur == null){
queue.poll();
}else {
//遇到不為空的節點就表示不是完全二叉樹.
return false;
}
}
//隊空既為true;
return true;
}
方法二思路:
1. 觀察完全二叉樹的圖形我們可以看出來,每個節點要么有2個子節點,要么沒有節點,要么就只有一個左節點沒有右節點.
2. 遍歷判斷
①如果左子樹和右子樹都不為空,就入隊.
②如果左子樹存在 右子樹不存在,那么進行第二個判斷.
③如果左子樹不存在 右子樹存在,那么直接false
④如果左子樹右子樹都不存在,那么也進入第二個判斷.
3. 第二個判斷,判斷是否接下來的左子樹和右子樹都為空,如果不為空,就是false;一直為空就是true;
代碼實作:
boolean isCompleteTree1(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
boolean isComplete = true;
while(!queue.isEmpty()){
TreeNode top = queue.poll();
if(isComplete) {
//1.都不為空 入隊
if (top.left != null && top.right != null) {
queue.offer(top.left);
queue.offer(top.right);
} else if (top.left != null && top.right == null) {
//2.左子樹不為空,右子樹為空,進入第二個判斷
isComplete = false;
queue.offer(top.left);
} else if (top.left == null && top.right != null) {
//3.左子樹為空,右子樹不為空,不符合完全二叉樹概念false
return false;
} else {
//4.左右子樹都為空,進入第二個判斷
isComplete = false;
}
}else {
//第2判斷
//如果后面的節點還有子樹,那就不符合完全二叉樹概念 false
if(top.left != null || top.right != null){
return false;
}
}
}
//回圈遍歷結束,那就是滿足條件,回傳true;
return true;
}
2.9 前中后序的非遞回實作
①前序遍歷 (非遞回)
// 前序遍歷
void preOrderTraversal(TreeNode root) {
if (root == null) return;
TreeNode cur = root;
Stack<TreeNode> stack = new Stack<>();
while (cur != null || !stack.empty()) {
while (cur != null) {
stack.push(cur);
System.out.print(cur.val+" ");
cur = cur.left;
}
TreeNode top = stack.pop();
cur = top.right;
}
}
②中序遍歷 (非遞回)
// 中序遍歷
void inOrderTraversal(TreeNode root){
if(root == null) return ;
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while(cur != null || !stack.empty()) {
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
TreeNode top = stack.pop();
System.out.print(top.val + " ");
cur = top.right;
}
}
③后序遍歷 (非遞回)
// 后序遍歷
void postOrderTraversal(TreeNode root){
if(root == null)
return;
TreeNode cur = root;
TreeNode pre = null;//用來指向上一個被列印的元素
Stack<TreeNode> stack = new Stack<>();
while(cur != null || !stack.empty()){
while(cur != null){
stack.push(cur);
cur = cur.left;
}
cur = stack.peek();
if(cur.right == null || pre == cur.right ){
stack.pop();
System.out.print(cur.val+" ");
pre = cur;
cur = null;
}else {
cur = cur.right;
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/379473.html
標籤：java
上一篇：新專案如何技術選型以及落地實作