目錄
一.樹的概念
二.樹中重要的概念
三.二叉樹的概念
滿二叉樹
完全二叉樹
四.二叉樹的性質
五.二叉樹的存儲
六.二叉樹的遍歷
前序遍歷
中序遍歷?
后序遍歷?
一.樹的概念
樹是一種非線性數(shù)據(jù)結構，它由節(jié)點和邊組成。樹的每個節(jié)點可以有零個或多個子節(jié)點，其中一個節(jié)點被指定為根節(jié)點。樹的節(jié)點之間通過邊連接。另外，樹形結構中，子樹之間不能有交集，否則就不是樹形結構。
樹的結構具有層級關系，根節(jié)點位于最頂層，而葉節(jié)點位于最底層。樹的形狀可以類比于現(xiàn)實生活中的樹，根節(jié)點相當于樹的根部，而分支和葉子節(jié)點則相當于樹的枝干和葉子。
在計算機科學中，樹被廣泛用于各種應用，例如文件系統(tǒng)、數(shù)據(jù)庫索引、編譯器中的抽象語法樹等。樹的常見特點是具有唯一的根節(jié)點、沒有循環(huán)的邊、可以有任意數(shù)量的子節(jié)點等。
樹的常見操作包括插入新節(jié)點、刪除節(jié)點、查找節(jié)點、遍歷節(jié)點等。常見的樹結構包括二叉樹、紅黑樹、AVL樹等。樹的設計和使用在算法和數(shù)據(jù)結構領域中非常重要，它可以提供高效的數(shù)據(jù)存儲和檢索方式。?
二.樹中重要的概念
筆者就以下圖作為例子進行說明：
- 結點的度：一個結點含有子樹的個數(shù)稱為該結點的度； 如上圖：A的度為6
- 樹的度：一棵樹中，所有結點度的最大值稱為樹的度； 如上圖：樹的度為6
- 葉子結點或終端結點：度為0的結點稱為葉結點； 如上圖：B、C、H、I...等節(jié)點為葉結點
- 雙親結點或父結點：若一個結點含有子結點，則這個結點稱為其子結點的父結點； 如上圖：A是B的父結點
- 孩子結點或子結點：一個結點含有的子樹的根結點稱為該結點的子結點； 如上圖：B是A的孩子結點
- 根結點：一棵樹中，沒有雙親結點的結點；如上圖：A
- 結點的層次：從根開始定義起，根為第1層，根的子結點為第2層，以此類推
- 樹的高度或深度：樹中結點的最大層次； 如上圖：樹的高度為4
- 非終端結點或分支結點：度不為0的結點； 如上圖：D、E、F、G...等節(jié)點為分支結點
- 兄弟結點：具有相同父結點的結點互稱為兄弟結點； 如上圖：B、C是兄弟結點
- 堂兄弟結點：雙親在同一層的結點互為堂兄弟；如上圖：H、I互為兄弟結點
- 結點的祖先：從根到該結點所經(jīng)分支上的所有結點；如上圖：A是所有結點的祖先
- 子孫：以某結點為根的子樹中任一結點都稱為該結點的子孫。如上圖：所有結點都是A的子孫
- 森林：由m（m>=0）棵互不相交的樹組成的集合稱為森林?
三.二叉樹的概念
二叉樹是一種常見的樹狀數(shù)據(jù)結構，在二叉樹中，每個節(jié)點最多有兩個子節(jié)點，分別稱為左子節(jié)點和右子節(jié)點。二叉樹的特點是每個節(jié)點最多只有兩個子節(jié)點，且子節(jié)點的位置是有序的，即左子節(jié)點在右子節(jié)點之前。
二叉樹可以為空，如果一個二叉樹不為空，則它一定由根節(jié)點、左子樹和右子樹組成。每個節(jié)點都有一個值，可以是任意類型的數(shù)據(jù)。
二叉樹也可以只有一個節(jié)點，如下圖所示，根節(jié)點不為空，但是左子樹和右子樹為空，這樣的二叉樹也是允許存在的
總的來說，對于任意一顆二叉樹，它都是由以下幾部分復合而成的：
二叉樹可以用來表示許多實際問題，例如計算機科學中的排序和搜索算法。在二叉樹中，有一些特殊的類型，如滿二叉樹、完全二叉樹和平衡二叉樹等。二叉樹還可以通過遍歷算法來訪問其中的節(jié)點，最常見的遍歷算法有前序遍歷、中序遍歷和后序遍歷。
二叉樹中還有以下倆個常見的特殊的二叉樹
滿二叉樹
一棵二叉樹，如果每層的結點數(shù)都達到最大值，則這棵二叉樹就是滿二叉樹。也就是說，如果一棵二叉樹的層數(shù)為 k ，且結點總數(shù)是 ，則它就是滿二叉樹。
完全二叉樹
完全二叉樹是由滿二叉樹而引出來的，對于深度為 k 的，有 n 個結點的二叉樹，當且僅當其每一個結點都與深度為?k 的滿二叉樹中編號從0至n-1的結點一一對應時稱之為完全二叉樹。 要注意的是滿二叉樹是一種特殊的完全二叉樹
四.二叉樹的性質
- 若規(guī)定根結點的層數(shù)為1，則一棵非空二叉樹的第?i 層上最多有個節(jié)點
- 若規(guī)定只有根結點的二叉樹的深度為 1?，則深度為K的二叉樹的最大結點數(shù)是
- 對任何一棵二叉樹, 如果其葉結點個數(shù)為 n0?, 度為2的非葉結點個數(shù)為 n2?,則有 n0＝n2＋1?
- ?具有?n?個結點的完全二叉樹的深度?k?為
- 對于具有?n?個結點的完全二叉樹，如果按照從上至下從左至右的順序對所有節(jié)點從0開始編號，則對于序號為?i 的結點有：若i>0，雙親序號：(i-1)/2；i=0，i為根結點編號，無雙親結點；若2i+1<n，左孩子序號：2i+1，否則無左孩子；若2i+2<n，右孩子序號：2i+2，否則無右孩
五.二叉樹的存儲
對于任意一個節(jié)點，我們最多只能知道它的左右孩子節(jié)點和根節(jié)點，以及自己保存的數(shù)據(jù)，由此我們引申出許多種表示二叉樹的方法，常見的有孩子表示法，孩子雙親表示法，兄弟節(jié)點表示法...
// 孩子表示法
class Node {
int val; // 數(shù)據(jù)域
Node left; // 左孩子的引用，常常代表左孩子為根的整棵左子樹
Node right; // 右孩子的引用，常常代表右孩子為根的整棵右子樹
}
// 孩子雙親表示法
class Node {
int val; // 數(shù)據(jù)域
Node left; // 左孩子的引用，常常代表左孩子為根的整棵左子樹
Node right; // 右孩子的引用，常常代表右孩子為根的整棵右子樹
Node parent; // 當前節(jié)點的根節(jié)點
}筆者以下圖舉例：
?
我們使用孩子表示法，然后依次按照圖示組成一顆二叉樹（后文的遍歷都是基于此樹）
public class MyBinaryTree {
public class TreeNode {
public char val;//記錄當前節(jié)點的值
public TreeNode leftNode;//記錄當前節(jié)點的左孩子節(jié)點
public TreeNode rightNode;//記錄當前節(jié)點的右孩子節(jié)點
public TreeNode(char val) {//初始化節(jié)點的值
this.val = val;
}
}
//生成每一個節(jié)點,然后連起來
public TreeNode CreatTree() {
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.leftNode = B;
A.rightNode = C;
B.leftNode = D;
C.leftNode = E;
C.rightNode = F;
//最后返回根節(jié)點
return A;
}
}六.二叉樹的遍歷
二叉樹的遍歷是指按照一定的規(guī)則，將二叉樹中的所有節(jié)點訪問一次，并且每個節(jié)點只訪問一次。常見的二叉樹遍歷方式有前序遍歷、中序遍歷和后序遍歷。
前序遍歷
前序遍歷（preorder traversal）：先訪問根節(jié)點，然后遍歷左子樹，最后遍歷右子樹。具體步驟如下：
- 訪問根節(jié)點
- 前序遍歷左子樹
- 前序遍歷右子樹?
代碼實現(xiàn)如下：
//前序遍歷
public void preOrder(TreeNode root) {
if (root == null) {
return;//空樹不需要遍歷
}
System.out.print(root.val + " ");//訪問根節(jié)點
preOrder(root.leftNode);//前序遍歷左子樹
preOrder(root.rightNode);//前序遍歷右子樹
}對于上述的代碼，程序運行起來的具體邏輯是如下圖這樣的，反復的遞歸和回退進行實現(xiàn)
?
中序遍歷?
中序遍歷（inorder traversal）：先遍歷左子樹，然后訪問根節(jié)點，最后遍歷右子樹。具體步驟如下：
- 中序遍歷左子樹
- 訪問根節(jié)點
- 中序遍歷右子樹
代碼實現(xiàn)如下：
//中序遍歷
public void inOrder(TreeNode root) {
if (root == null) {
return;//空樹不需要遍歷
}
inOrder(root.leftNode);//中序遍歷左子樹
System.out.print(root.val + " ");//訪問根節(jié)點
inOrder(root.rightNode);//中序遍歷右子樹
}后序遍歷?
后序遍歷（postorder traversal）：先遍歷左子樹，然后遍歷右子樹，最后訪問根節(jié)點。具體步驟如下：
- 后序遍歷左子樹
- 后序遍歷右子樹
- 訪問根節(jié)點
代碼實現(xiàn)如下：
//后序遍歷
public void postOrder(TreeNode root) {
if (root == null) {
return;//空樹不需要遍歷
}
postOrder(root.leftNode);//后序遍歷左子樹
postOrder(root.rightNode);//后序遍歷右子樹
System.out.print(root.val + " ");//訪問根節(jié)點
}我們可以寫個測試來看看遍歷的結果：
public class Test {
public static void main(String[] args) {
MyBinaryTree myBinaryTree = new MyBinaryTree();
MyBinaryTree.TreeNode rootNode = myBinaryTree.CreatTree();
System.out.println();
System.out.println("前序遍歷：");
myBinaryTree.preOrder(rootNode);
System.out.println();
System.out.println("中序遍歷:");
myBinaryTree.inOrder(rootNode);
System.out.println();
System.out.println("后序遍歷:");
myBinaryTree.postOrder(rootNode);
}
}
輸出：
也就是說：
其實不管是前序，中序，后序遍歷，他們整體的搜索過程都是一樣的，不同的地方在于對當前根節(jié)點的處理時間不一樣：前序遍歷是先處理根節(jié)點；中序遍歷是先遍歷當前節(jié)點的左子樹再處理當前根節(jié)點；而后序遍歷則是最后再處理根節(jié)點，就像下圖一樣
以上是三種最基本的二叉樹遍歷方式。除了這三種，還有一些其他的二叉樹遍歷方式，比如層序遍歷、螺旋遍歷等。不同的遍歷方式適用于不同的場景和問題，可以根據(jù)具體的需求選擇合適的遍歷方式。文章來源：http://www.zghlxwxcb.cn/news/detail-763618.html
?
?本次的分享就到此為止了，希望我的分享能給您帶來幫助，也歡迎大家三連支持，你們的點贊就是博主更新最大的動力！
如有不同意見，歡迎評論區(qū)積極討論交流，讓我們一起學習進步！
有相關問題也可以私信博主，評論區(qū)和私信都會認真查看的，我們下次再見文章來源地址http://www.zghlxwxcb.cn/news/detail-763618.html
到了這里，關于數(shù)據(jù)結構：圖文詳解 樹與二叉樹（樹與二叉樹的概念和性質，存儲，遍歷）的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
