文章目錄

• 樹
• 二叉樹
• • 滿二叉樹和完全二叉樹
  • 二叉樹的性質
  • 代碼實現求二叉樹的深度

---

樹

樹是一種非線性的數據結構，它是由n個有限結點組成一個具有層次關系的集合。

樹的相關名詞：

• 根節點：沒有前驅結點的結點。
• 父節點，子節點：有 節點C 為 節點E 的前驅節點（那么 E 就是 C 的后繼節點），稱 C 為 E 的父節點， E 為 C 的子節點。
• 兄弟節點：具有相同的父節點的結點互稱為兄弟節點，如B,C是兄弟節點
• 深度（高度）：從根節點到葉節點依次經過的節點（含根、葉節點）形成樹的一條路徑，最長路徑的長度為樹的深度。
• 度：該節點的子節點個數。樹的度則是其中節點度的最大值。
• 邊：父子節點間的連線，N 個節點有 N-1 條邊。
• 葉子節點：度為零的結點為葉子節點，如下圖中所有#

二叉樹

二叉樹：每個節點最多含有兩個子樹的樹稱為二叉樹。特點如下：

• 每個節點最多有兩棵子樹，即二叉樹不存在度大于2的節點
• 二叉樹的子樹有左右之分，其子樹的次序不能顛倒

滿二叉樹和完全二叉樹

滿二叉樹：

一個二叉樹，如果每一層的節點數都達到最大值，則這個二叉樹就是滿二叉樹。也就是說，如果一個二叉樹的層數為K，且節點總數為(2^k)-1，則就是滿二叉樹

完全二叉樹：

滿二叉樹是一種特殊的完全二叉樹，對于深度為k的，有n個節點的二叉樹，當且僅當每一個節點都與深度為K的滿二叉樹中編號1~n的結點相對應時稱為完全二叉樹

有一個很好的區分它們的方法：滿二叉樹是除葉子節點外所有節點都存在左右子樹的一棵樹，而完全二叉樹則是所有節點都是連續的，不存在有右子樹而沒有左子樹的情況

二叉樹的性質

• 一棵非空二叉樹上的 第n層 最多有 2^n-1 個節點（層數從1開始）
• 深度為n 的二叉樹的最大節點數為 2ⁿ - 1 個
• 如果葉子節點的個數為 n0 ，度為2 的結點的個數為 n2 ，則有 n0 = n2 + 1
• 具有 n 個節點的完全二叉樹的深度為 log2(n) + 1
• 如果 某結點 的編號為 i（從0開始），那么他的 左孩子 編號為 2i +1 ， 右孩子 編號為 2i +2 ，他的 父節點 為 (i - 1) / 2 。

代碼實現求二叉樹的深度

求樹的深度需要遍歷樹的所有節點，樹的遍歷方式總體分為兩類：

深度優先搜索（DFS）、廣度優先搜索（BFS）；

• 常見的 DFS ： 先序遍歷、中序遍歷、后序遍歷；
• 常見的 BFS ： 層序遍歷（即按層遍歷）。

本文將介紹基于 后序遍歷（DFS） 和 層序遍歷（BFS） 的兩種解法。

• DFS深度優先搜索：

/**- Definition for a binary tree node.- struct TreeNode {- int val;- TreeNode *left;- TreeNode *right;- TreeNode(int x) : val(x), left(NULL), right(NULL) {}- };*/ class Solution { // 后序遍歷 public:int maxDepth(TreeNode* root) {if(root==nullptr) return 0;return max(maxDepth(root->left), maxDepth(root->right)) + 1;} };

• BFS廣度優先搜索：

class Solution { // 層序遍歷 public:int maxDepth(TreeNode* root) {if(root==nullptr) return 0;queue<TreeNode*> que;que.push(root);int res = 0;while(!que.empty()){queue<TreeNode*> tmp;while(!que.empty()){TreeNode* node = que.front();que.pop();if(node->left) tmp.push(node->left);if(node->right) tmp.push(node->right);}que = tmp;res++;}return res;} };

總結

以上是生活随笔為你收集整理的二叉树相关知识及求深度的代码实现的全部內容，希望文章能夠幫你解決所遇到的問題。

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