一、樹這一章節主要總結有以下幾個知識點，以及一些需要注意的點：

1、樹的結構體，一般有數據域，左右孩子域，順序結構（一般適用于完全二叉樹，避免過多空間浪費）

typedef struct
{
?? ?TElemType data;
?? ?int lch;
?? ?int rch;
}BiTNode; //定義順序存儲結構

typedef sttuct BiTNode
{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree; //定義鏈式存儲結構（二叉鏈表形式）

2、通過輸入的信息來建立樹，并找出根結點

順序結構里：所給題目，沒有孩子就會用‘-’表示，時
1、輸入左右孩子時不能直接
cin>>t[i].lch;
cin>>t[i].rch; //這樣是錯的，因為lch是int類型，而‘-’是char 類型
而是要先
char x,y;
cin>>x>>y
if(x!='-')
?? {
?????? t[i].lch = x-'0'; //將char型的數字改為int型的數值
check[t[i].lch] = true;
}
2、記得將x/y等于'-'的t[i].lch/rch元素賦值為-1，方便后面的表示

3、二叉樹的遍歷：先中后，三種順序，運用遞歸的方法；層序，利用隊列的知識

#include <queue> queue <int> queue1; //隊列創建

//查了一些隊列的相關操作
1、彈出隊列：queue1.pop();
2、訪問隊尾元素：queue1.back();
3、判斷隊列空：queue1.empty()；
（當隊列空時，返回true）
4、查看隊列中的元素個數：queue1.size()
5、返回隊首元素：queue1.front()

利用隊列實現層序遍歷簡單說明：

???????? 就是在先根結點入隊，然后出隊，然后其左右孩子入隊，再依次出隊，其中每個結點每次出隊時就將其左右孩子入隊。當隊列為空時，整棵樹層序遍歷完畢。

下圖為簡單演示

（圖片摘自博客 https://blog.csdn.net/qq_29542611/article/details/79372678）

層序遍歷代碼如下：

void level(node t[], int x) //層次遍歷 { int p; //等會pop出的元素 queue <int> q; q.push(x); //x是根結點的索引（所在下標） //入隊while(!q.empty()) {p = q.front(); //p賦值為隊首元素 q.pop(); //出隊if(p!=-1) //該結點非空 {q.push(t[p].lch);q.push(t[p].rch);} } }

但是剛才重新看代碼的時候發現 if(p!=-1){ q.push(t[p].lch); q.push(t[p].rch); } 這一步我好像不太理解，這一步是想要判斷其左右孩子是否為空，不是應該如下代碼所示嗎：

if (t[p].lch != -1)q.push(t[p].lch);if (t[p].rch!= -1)q.push(t[p].rch);

?

二、下一章將學習圖，做出幾個小要求：

1、做好提前預習，把書本的內容認真看一遍

2、老師當天講完編程的內容就當天復習并及時按編程思想自己重新寫一次代碼

轉載于:https://www.cnblogs.com/MRBC/p/10810344.html

總結

以上是生活随笔為你收集整理的第五章 树和二叉树的全部內容，希望文章能夠幫你解決所遇到的問題。

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