聲明：本篇博客的圖來源于：?https://blog.csdn.net/qq_35433716/article/details/89710720

?一、相關名詞說明

度：結點擁有的子樹數；（樹的度是樹內各節點的度的最大值）

葉節點或終端結點：度為0的結點

非終端結點或分支節點：度不為0的結點；

二、二叉樹的定義

二叉樹是n個結點的有限集合，該集合或者為空集（稱為空二叉樹），或者由一個根結點和兩棵互不相交的、分別稱為根節點的左子樹和右子樹組成。

三、二叉樹的特點

1、每個結點最多由兩顆子樹；

2、左子樹和右子樹是有順序的；

3、二叉樹的五種形態：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? 圖3-1

四、特殊二叉樹

1、斜樹

左斜樹：所有的結點都只有左子樹的二叉樹，如圖3-1的（3）；

右斜樹：所有的結點都只有右子樹的二叉樹，如圖3-2的（4）；

2、滿二叉樹

定義：在一棵二叉樹中，所有的分支結點都存在左子樹和右子樹，并且所有葉子都在同一層中，如圖4-1所示。

圖4-1 滿二叉樹

3、完全二叉樹

定義：對一根具有n個結點的二叉樹按層序編號，如果序號為i(1<=i<=n)的結點與同樣深度的滿二叉樹中編號為i的結點在二叉樹中的位置完全相同，則這顆二叉樹稱為完全二叉樹,如圖4-2所示。

特點：（1）葉子結點只能出現在最下兩層；（2）最下層的葉子一定集中在左部連續位置；（3）倒數二層，若有葉子結點，一定在右部連續位置；（4）如果結點度為1，則該結點只有左孩子；（5）同樣結點樹的二叉樹，完全二叉樹的深度最小。

圖4-2 完全二叉樹

五、二叉樹性質

六、二叉樹存儲結構

1、順序存儲結構：只適用于完全二叉樹

2、二叉鏈表：包括data：數據域，lchild：左孩子指針域，rchild:右孩子指針域

template<typename T> class treeNode {T data;treename *lchild, *rchild; };

七、遍歷二叉樹

定義：二叉樹的遍歷是指從根結點出發，按照某種次序依次訪問二叉樹中所有結點，使得每個結點被訪問一次且僅被訪問一次。

遍歷方法：

1、前序遍歷

若二叉樹非空，則執行以下操作

（1）訪問根結點；

（2）先序遍歷左子樹；

（3）先序遍歷右子樹。

2、中序遍歷

若二叉樹非空，則執行以下操作

（1）中序遍歷左子樹；

（2）訪問根結點；

（3）中序遍歷右子樹。

3、后序遍歷

若二叉樹非空，則執行以下操作

（1）后序遍歷左子樹；

（2）后序遍歷右子樹；

（3）訪問根節點。

4、層序遍歷

若二叉樹非空，則從樹的根結點開始，從上而下逐層遍歷，在同一層中，按從左到右的順序對結點逐個訪問。

八、二叉樹C++實現

以下代碼參考自：https://blog.csdn.net/Ajay666/article/details/76736333

#include <iostream> #include <string> using namespace std;class treeNode { public:char data;treeNode *lchild, *rchild; };class tree { public:private:treeNode *root;int height; //樹高void pre_order(treeNode *t);void in_order(treeNode *t);void post_order(treeNode *t);treeNode *create(string &s, int &pos);void get_height(treeNode *t, int h); public:tree(){ root = NULL; height = 0; }void createtree(string &s);void preorder();void inorder();void postorder();int getheight(); }; //遞歸創建二叉樹，如果是#則表示空結點 treeNode* tree::create(string &s, int &pos) {++pos;treeNode *t;if ((unsigned)pos >= s.size()){return NULL;}else{if (s[pos] == '#'){t = NULL;}else{t = netreeNode; //分配內存空間t->data = s[pos];t->lchild = create(s, pos);t->rchild = create(s, pos);}return t;} } //按照前序遍歷創建二叉樹 void tree::createtree(string &s) {int pos = -1;root=create(s, pos); } //前序遍歷二叉樹 void tree::preorder() {pre_order(root);cout << endl; }void tree::pre_order(treeNode *t) {if (t != NULL){cout << t->data << " ";pre_order(t->lchild);pre_order(t->rchild);} }//中序遍歷二叉樹 void tree::inorder() {in_order(root);cout << endl; }void tree::in_order(treeNode *t) {if (t != NULL){in_order(t->lchild);cout << t->data << " ";in_order(t->rchild);} }//后序遍歷二叉樹 void tree::postorder() {post_order(root);cout << endl; }void tree::post_order(treeNode *t) {if (t != NULL){post_order(t->lchild);post_order(t->rchild);cout << t->data << " ";} }//求樹的高度 void tree::get_height(treeNode *t, int h) {if (t != NULL){h++;if (h > height){height = h;}get_height(t->lchild, h);get_height(t->rchild, h);} }int tree::getheight() {get_height(root, 0);cout <<"樹的高度："<< height << endl;return height; } int main() {string s1= "ABD##E#F##C##";tree t1;t1.createtree(s1); //創建樹t1.preorder(); //前序遍歷樹t1.inorder(); //中序遍歷樹t1.postorder(); //后序遍歷樹t1.getheight(); //樹高度system("pause");return 0; }

?

?

總結

以上是生活随笔為你收集整理的大话数据结构学习笔记（8）二叉树的全部內容，希望文章能夠幫你解決所遇到的問題。

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