學習地址：【數據結構與算法基礎-java版】? ? ? ? ? ? ? ? ??🚀數據結構--Java專欄🚀

• 筆記01【01-09】【概述、數組基本使用】【源碼、課件】
• 筆記02【10-18】【棧、隊列、單鏈表(增刪節點)、循環鏈表、雙向循環鏈表、遞歸(斐波那契、漢諾塔)】
• 筆記03【19-27】【（時間、空間復雜度）；八大排序（冒泡、快速、插入、希爾、選擇、歸并、基數、隊列基數）】
• 筆記04【28-33】【樹結構(二叉樹)概述、創建、遍歷、查找節點、刪除節點】
• 筆記05【34-39】【順序存儲二叉樹概述、二叉樹遍歷、堆排序、線索二叉樹實現及遍歷】
• 筆記06【40-48】【赫夫曼樹、概述、原理分析、代碼實現(數據壓縮、創建編碼表、解碼、壓縮文件、解壓文件)】
• 筆記07【49-54】【二叉排序樹（添加、查找、刪除節點）】
• 筆記08【55-57】【二叉平衡樹(AVL)-概述、單旋轉、雙旋轉】
• 筆記09【58-60】【計算機中數據的存儲原理、2-3樹的插入原理、B樹和B+樹】
• 筆記10【61-63】【哈希表概述、散列函數的設計、散列沖突解決方案】
• 筆記11【64-67】【圖結構概述、圖遍歷原理(BFS\DFS)、圖遍歷代碼實現】

目? ?錄

P28-4.1樹結構概述

P29-4.2二叉樹的概述

P30-4.3創建二叉樹

P31-4.4遍歷二叉樹

P32-4.5二叉樹中節點的查找

P33-4.6刪除二叉樹的子樹

1、BinaryTree.java

2、Node.java

3、TestBinaryTree.java

---

P28-4.1樹結構概述

順序存儲：開始位置、結束位置，插入數據、刪除數據=====》在數據量大的情況下，非常耗費時間！根據下標查找元素。

鏈表存儲：從第1個節點，開始往后找。。。【耗時！！！】

樹結構：查找性能、插入性能 較好！！！

?雙親結點：雌雄同體！！！子節點的上一個節點。--------->子節點

路徑：從某個節點到達某個節點，途中經過的結點。

節點的度：節點有幾個子節點（子樹）。

節點的權：給節點賦予的值（節點中存儲的數值）。

葉子節點：沒有子節點的節點。

樹的高度：最大層數。【4】

森林：多個樹。

P29-4.2二叉樹的概述

二叉樹：任何一個節點的子節點數量不超過2！?

二叉樹的子節點 分 左節點 和 右節點。

?

滿二叉樹：所有葉子節點都在最后一層，而且節點的總數為 2^n-1。【n是樹的高度！】
滿二叉樹，是 完全二叉樹！

?

完全二叉樹：所有葉子節點都在最后一層或倒數第二層，且最后一層的葉子節點在左邊連續，倒數第二層的葉子節點在右邊連續。

從上到下，從左到右 依次 數能數完 就是 完全二叉樹！

P30-4.3創建二叉樹

雙鏈表 是 前驅 和 后繼，樹 是 左右孩子結點，不一樣！

二叉樹的5種形式：

?

P31-4.4遍歷二叉樹

遍歷詳解：https://blog.csdn.net/weixin_44949135/article/details/105291651

P32-4.5二叉樹中節點的查找

P33-4.6刪除二叉樹的子樹

刪除 節點（子樹）：

無子節點（子節點一并刪除！）；

有子節點。?

1、BinaryTree.java

package demo5;public class BinaryTree {Node root;// 設置根節點public void setRoot(Node root) {this.root = root;}// 獲取根節點public Node getRoot() {return root;}public void frontShow() {if (root != null) {root.frontShow();}}public void midShow() {if (root != null) {root.midShow();}}public void afterShow() {if (root != null) {root.afterShow();}}public Node frontSearch(int i) {return root.frontSearch(i);}public void delete(int i) {if (root.value == i) {root = null;} else {root.delete(i);}}}

2、Node.java

package demo5;public class Node {// 節點的權int value;// 左兒子Node leftNode;// 右兒子Node rightNode;public Node(int value) {this.value = value;}// 設置左兒子public void setLeftNode(Node leftNode) {this.leftNode = leftNode;}// 設置右兒子public void setRightNode(Node rightNode) {this.rightNode = rightNode;}// 前序遍歷public void frontShow() {// 先遍歷當前節點的內容System.out.print(value + "、");// 左節點if (leftNode != null) {leftNode.frontShow();}// 右節點if (rightNode != null) {rightNode.frontShow();}}// 中序遍歷public void midShow() {// 左子節點if (leftNode != null) {leftNode.midShow();}// 當前節點System.out.print(value + "、");// 右子節點if (rightNode != null) {rightNode.midShow();}}// 后序遍歷public void afterShow() {// 左子節點if (leftNode != null) {leftNode.afterShow();}// 右子節點if (rightNode != null) {rightNode.afterShow();}// 當前節點System.out.print(value + "、");}// 前序查找public Node frontSearch(int i) {Node target = null;// 對比當前節點的值if (this.value == i) {return this;// 當前節點的值不是要查找的節點} else {// 查找左兒子if (leftNode != null) {// 有可能可以查到，也可以查不到，查不到的話，target還是一個nulltarget = leftNode.frontSearch(i);}// 如果不為空，說明在左兒子中已經找到if (target != null) {return target;}// 查找右兒子if (rightNode != null) {target = rightNode.frontSearch(i);}}return target;}// 刪除一個子樹public void delete(int i) {Node parent = this;// 判斷左兒子if (parent.leftNode != null && parent.leftNode.value == i) {parent.leftNode = null;return;}// 判斷右兒子if (parent.rightNode != null && parent.rightNode.value == i) {parent.rightNode = null;return;}// 遞歸檢查并刪除左兒子parent = leftNode;if (parent != null) {parent.delete(i);}// 遞歸檢查并刪除右兒子parent = rightNode;if (parent != null) {parent.delete(i);}}}

3、TestBinaryTree.java

package demo5;public class TestBinaryTree {public static void main(String[] args) {// 創建一顆樹BinaryTree binTree = new BinaryTree();// 創建一個根節點Node root = new Node(1);// 把根節點賦給樹binTree.setRoot(root);// 創建一個左節點Node rootL = new Node(2);// 把新創建的節點設置為根節點的子節點root.setLeftNode(rootL);// 創建一個右節點Node rootR = new Node(3);// 把新創建的節點設置為根節點的子節點root.setRightNode(rootR);// 為第二層的左節點創建兩個子節點rootL.setLeftNode(new Node(4));rootL.setRightNode(new Node(5));// 為第二層的右節點創建兩個子節點rootR.setLeftNode(new Node(6));rootR.setRightNode(new Node(7));// 前序遍歷樹System.out.println("========前序遍歷樹========");binTree.frontShow();System.out.println("\n");// 中序遍歷System.out.println("========中序遍歷樹========");binTree.midShow();System.out.println("\n");// 后序遍歷System.out.println("========后序遍歷樹========");binTree.afterShow();System.out.println("\n\n");// 前序查找Node result = binTree.frontSearch(3);System.out.println(result);System.out.println(result == rootR);System.out.println("\n\n===============");// 刪除一個子樹binTree.delete(4);binTree.frontShow();}}

希望對您有所幫助~

總結

以上是生活随笔為你收集整理的数据结构Java04【树结构概述、创建、遍历、查找节点、删除节点】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。