滿二叉樹

定義：高度為h，并且由2{h} –1個(gè)結(jié)點(diǎn)的二叉樹，被稱為滿二叉樹。

---

完全二叉樹

定義：一棵二叉樹中，只有最下面兩層結(jié)點(diǎn)的度可以小于2，并且最下一層的葉結(jié)點(diǎn)集中在靠左的若干位置上。這樣的二叉樹稱為完全二叉樹。
特點(diǎn)：葉子結(jié)點(diǎn)只能出現(xiàn)在最下層和次下層，且最下層的葉子結(jié)點(diǎn)集中在樹的左部。顯然，一棵滿二叉樹必定是一棵完全二叉樹，而完全二叉樹未必是滿二叉樹。

---

二叉搜索樹

定義：在二叉搜索樹中，任取一個(gè)節(jié)點(diǎn)A，A的值不小于它左子樹上的任何值、它右子樹上的每個(gè)值都大于A。

插入節(jié)點(diǎn)、刪除樹

/*二叉搜索樹數(shù)據(jù)類型*/ struct TreeNode {int data;TreeNode* left;TreeNode* right; }; /*向二叉搜索樹中添加一個(gè)節(jié)點(diǎn)*/ TreeNode* InsertTree(TreeNode* root, int value){//遞歸調(diào)用，所以要記得返回類型TreeNode* newNode;if(root == nullptr){newNode = new TreeNode;newNode->data = value;newNode->left = nullptr;newNode->right = nullptr;return newNode;}if(value < root->data)root->left = InsertTree(root->left, value);if(value > root->data)root->right = InsertTree(root->right, value);return root; } /*刪除二叉樹*/ void DeleteTree(TreeNode* root){if(root->left != nullptr)DeleteTree(root->left);if(root->right != nullptr)DeleteTree(root->right);delete root;return; }

廣度優(yōu)先遍歷（BFS）

算法流程：
1. 根節(jié)點(diǎn)入隊(duì)
2. 循環(huán)判斷當(dāng)前隊(duì)列非空，訪問隊(duì)首，出隊(duì)
3. 如果左子樹非空，左子樹根節(jié)點(diǎn)入隊(duì)
4. 如果右子樹非空，右子樹根節(jié)點(diǎn)入隊(duì)
代碼：

vector<int> BFS(TreeNode* root){std::vector<<int> sequence;queue<TreeNode*> q;q.push(root);while(!q.empty()){TreeNode* tmp = q.front();sequence.push_back(tmp->data);q.pop();if(tmp->left != nullptr)q.push(tmp->left);if(tmp->right != nullptr)q.push(tmp->right);}return sequence; }

深度優(yōu)先遍歷（DFS）

深度優(yōu)先遍歷。有四種遍歷方式：先根，后根，左子樹優(yōu)先，右子樹優(yōu)先

（1）先根順序遍歷：a. 訪問根節(jié)點(diǎn) b. 遍歷左子樹 c. 遍歷右子樹
（2）后根順序遍歷：a. 遍歷左子樹 b. 遍歷右子樹 c. 訪問根節(jié)點(diǎn)
（3）左子樹優(yōu)先遍歷：a. 遍歷左子樹 b. 訪問根節(jié)點(diǎn) c.遍歷右子樹
（4）右子樹優(yōu)先遍歷：a.遍歷右子樹 b.訪問根節(jié)點(diǎn) c.遍歷左子樹

/*先根遍歷代碼*/ /*其余遍歷方式相似，調(diào)換訪問順序即可*/ void FLRTraverse(TreeNode *root){printf("%d", root->val); //訪問根節(jié)點(diǎn)if(root->left != NULL)FLRTraverse(root->left); //遍歷左子樹if(root->right != NULL)FLRTraverse(root->right); //遍歷右子樹 }

總結(jié)

以上是生活随笔為你收集整理的二叉搜索树（BFS）总结的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。