資料結構之二叉樹基本操作詳解
文章目錄
- 資料結構之二叉樹基本操作詳解
- 一、樹概念和種類
- 樹的相關概念：
- 種類：
- 二、二叉樹
- 1.二叉樹概念
- 2.特殊二叉樹
- 3.二叉樹性質
- 3.二叉樹存盤結構
- 順序結構
- 鏈式結構
- 4.二叉樹基本操作
- 二叉樹前中后序遍歷
- 總結
一、樹概念和種類
樹的相關概念：
在介紹二叉樹之前我們先了解下什么是樹，
-
『 樹』是一種非線性的資料結構，它是由n（n>=0）個有限結點組成一個具有層次關系的集合，把它叫做樹是因.為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的，
-
有一個特殊的結點，稱為根結點，根節點沒有前驅結點，
除根節點外，其余結點被分成M(M>0)個互不相交的集合T1、T2、……、Tm，其中每一個集合Ti(1<= i <= m)又是一棵結構與樹類似的子樹，每棵子樹的根結點有且只有一個前驅，可以有0個或多個后繼，
因此，樹是遞回定義的，
-
并且要注意子樹之前不能不能有交集否則會構成一個環，就不是樹了，
其他概念： -
節點的度：一個節點含有的子樹的個數稱為該節點的度； 如上圖：A的為6
-
葉節點或終端節點：度為0的節點稱為葉節點；
如上圖：B、C、H、I…等節點為葉節點 非終端節點或分支節點：度不為0的節點； 如上圖：D、E、F、G…等節點為分支節點 -
雙親節點或父節點：若一個節點含有子節點，則這個節點稱為其子節點的父節點； 如上圖：A是B的父節點
-
孩子節點或子節點：一個節點含有的子樹的根節點稱為該節點的子節點； 如上圖：B是A的孩子節點
-
兄弟節點：具有相同父節點的節點互稱為兄弟節點； 如上圖：B、C是兄弟節點
-
樹的度：一棵樹中，最大的節點的度稱為樹的度； 如上圖：樹的度為6
-
節點的層次：從根開始定義起，根為第1層，根的子節點為第2層，以此類推； 樹的高度或深度：樹中節點的最大層次； 如上圖：樹的高度為4
-
堂兄弟節點：雙親在同一層的節點互為堂兄弟；如上圖：H、I互為兄弟節點
-
節點的祖先：從根到該節點所經分支上的所有節點；如上圖：A是所有節點的祖先
-
子孫：以某節點為根的子樹中任一節點都稱為該節點的子孫，如上圖：所有節點都是A的子孫 森林：由m（m>0）棵互不相交的樹的集合稱為森林；
種類：
那么我們接下來講解二叉樹相關知識，
二、二叉樹
1.二叉樹概念
-
『 二叉樹（binary tree） 』是指樹中節點的度不大于2的有序樹，它是一種最簡單且最重要的樹，如圖：
由此可以得到： -
二叉樹中的每一個節點的度最多是2，
-
并且二叉樹有左子樹和右子樹，屬于有序樹，
2.特殊二叉樹
-
『 滿二叉樹 』：一個二叉樹，如果每一個層的結點數都達到最大值，則這個二叉樹就是滿二叉樹，也就是說，如果一個二叉樹的層數為K，且結點總數是2的k次方-1，則它就是滿二叉樹，
-
『 完全二叉樹 』：完全二叉樹是效率很高的資料結構，完全二叉樹是由滿二叉樹而引出來的，對于深度為K的，有n個結點的二叉樹，當且僅當其每一個結點都與深度為K的滿二叉樹中編號從1至n的結點一一對 應時稱之為完全二叉樹，要注意的是滿二叉樹是一種特殊的完全二叉樹，
3.二叉樹性質
性質1：二叉樹的第i層上至多有2i-1（i≥1）個節點
性質2：深度為h的二叉樹中至多含有2h-1個節點 ，
性質3：若在任意一棵二叉樹中，有n0個葉子節點，有n2個度為2的節點，則必有n0=n2+1 ，
性質4：具有n個節點的完全二叉樹深為log2x+1（其中x表示不大于n的最大整數），
性質5：若對一棵有n個節點的完全二叉樹進行順序編號（1≤i≤n）
那么，對于編號為i（i≥1）的節點：
當i=1時，該節點為根，它無雙親節點
當i>1時，該節點的雙親節點的編號為i/2 ，
若2i≤n，則有編號為2i的左節點，否則沒有左節點 ，
若2i+1≤n，則有編號為2i+1的右節點，否則沒有右節點 ，
3.二叉樹存盤結構
- 二叉樹一般可以使用兩種結構存盤，一種順序結構，一種鏈式結構，
順序結構
- 順序結構存盤就是使用陣列來存盤，一般使用陣列只適合表示完全二叉樹，因為不是完全二叉樹會有空間的浪費，二叉樹順序存盤在物理上是一個陣列，在邏輯上是一顆二叉樹，
鏈式結構
- 二叉樹的鏈式存盤結構是指：
用鏈表來表示一棵二叉樹，即用鏈來指示元素的邏輯關系， 通常的方法是鏈表中每個結點由三個域組成，資料域和左右指標域，左右指標分別用來給出該結點左孩子和右孩子所 在的鏈結點的存盤地址 ，鏈式結構又分為二叉鏈和三叉鏈，
代碼如下（示例）：
typedef int BTDataType;
// 二叉鏈
struct BinaryTreeNode
{
struct BinTreeNode* _pLeft; // 指向當前節點左孩子
struct BinTreeNode* _pRight; // 指向當前節點右孩子
BTDataType _data; // 當前節點值域
}
// 三叉鏈
struct BinaryTreeNode
{
struct BinTreeNode* _pParent; // 指向當前節點的雙親
struct BinTreeNode* _pLeft; // 指向當前節點左孩子
struct BinTreeNode* _pRight; // 指向當前節點右孩子
BTDataType _data; // 當前節點值域
}；
4.二叉樹基本操作
二叉樹前中后序遍歷
-
所謂前序（先根）遍歷，就是嚴格按照 根 - > 左子樹 - > 右子樹的順序來遍歷整個二叉樹，
-
那么在這里我們采用遞回的方法，首先對于上圖所示，首先看根節點A，先根遍歷順序是： A - > A的左子樹- > A的右子樹
那么對于A的左子樹同樣按照先跟遍歷：*B - > B的左子樹- > B的右子樹
那么對于B的左子樹同理·········右子樹也一樣類推 -
并且遞回的終點條件是訪問的節點為空，先跟遍歷代碼如下：
void preorder(Tree* root)
{
if (root == NULL)//遞回截止條件節點為空
return;
printf("%c ", root->Data);//訪問當前的根節點
preorder(root->left);//訪問此時根節點的左子樹
preorder(root->right);//訪問此時根節點的右子樹
}
- 舉一反三，中跟后跟只需要改變訪問根節點，訪問左右子樹的順序即可
void inorder(Tree* root)//中序
{
if (root == NULL)
return;
inorder(root->left);
printf("%c ", root->Data);
inorder(root->right);
}
void Posorder(Tree* root)//后序
{
if (root == NULL)
return;
Posorder(root->left);
Posorder(root->right);
printf("%c ", root->Data);
}
總結
樹的應用也很廣泛，比如，你電腦上的檔案夾就是樹的結構，或者在查找中的效率也是非常高的！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/356119.html
標籤：其他
上一篇：【Oracle資料庫】手滑刪錯資料，一步步教你如何挽救？
下一篇：C語言指標講解