二叉樹
二叉樹是一種非線性數(shù)據(jù)結(jié)構(gòu)，代表“祖先”與“后代”之間的派生關(guān)系，體現(xiàn)了“一分為二”的分治邏輯。與鏈表相似，二叉樹的基本單元是節(jié)點，每個節(jié)點包含值，左子節(jié)點的索引，右子節(jié)點的索引
/* 二叉樹節(jié)點結(jié)構(gòu)體 */
struct TreeNode {
int val; // 節(jié)點值
TreeNode *left; // 左子節(jié)點指針
TreeNode *right; // 右子節(jié)點指針
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
當給定一個二叉樹的節(jié)點時，我們將該節(jié)點的左子節(jié)點及其以下節(jié)點形成的樹稱為該節(jié)點的左子樹，同理可得，右子節(jié)點及其以下節(jié)點形成的樹稱為該節(jié)點的右子樹。文章來源：http://www.zghlxwxcb.cn/news/detail-789799.html
在給定的二叉樹中，除了葉子節(jié)點，其他所有節(jié)點均包含子節(jié)點和非空子樹文章來源地址http://www.zghlxwxcb.cn/news/detail-789799.html
二叉樹的常見術(shù)語
- 根節(jié)點：位于二叉樹頂層的節(jié)點，沒有父節(jié)點
- 葉子節(jié)點：沒有字節(jié)的的節(jié)點，左右指針均為null
- 邊：連接兩個節(jié)點的線段，
- 節(jié)點所在的層：從頂?shù)降走f增，根節(jié)點的層數(shù)為1
- 節(jié)點的度：節(jié)點的字節(jié)點的個數(shù)，在二叉樹中，節(jié)點的度的取值范圍：0，1，2
- 二叉樹的高度：從根節(jié)點到最遠葉子節(jié)點所經(jīng)過的邊的數(shù)量
- 節(jié)點的深度：從根節(jié)點到該節(jié)點邊的數(shù)量
- 節(jié)點的高度：從最遠的葉子節(jié)點到該節(jié)點邊的數(shù)量
二叉樹的基本操作
/* 初始化二叉樹 */
// 初始化節(jié)點
TreeNode* n1 = new TreeNode(1);
TreeNode* n2 = new TreeNode(2);
TreeNode* n3 = new TreeNode(3);
TreeNode* n4 = new TreeNode(4);
TreeNode* n5 = new TreeNode(5);
// 構(gòu)建節(jié)點之間的引用（指針）
n1->left = n2;
n1->right = n3;
n2->left = n4;
n2->right = n5;
/* 插入與刪除節(jié)點 */
TreeNode* P = new TreeNode(0);
// 在 n1 -> n2 中間插入節(jié)點 P
n1->left = P;
P->left = n2;
// 刪除節(jié)點 P
n1->left = n2;
常見二叉樹的類型
- 完美二叉樹：**所有層的節(jié)點都被填滿。**所有葉子節(jié)點的度為0，其余所有節(jié)點的度為2
- 完全二叉樹：只有最底層的節(jié)點沒有被填滿并且最底層的節(jié)點靠左填滿
- 完滿二叉樹：除了葉子節(jié)點外，其余所有節(jié)點的度為2
- 平衡二叉樹：任意節(jié)點的左子樹和右子樹的高度之差的絕對值不超過1
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)之二叉樹簡介的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
