一棵n個結點的滿二叉樹有幾個度為1的結點,有幾個分支結點個幾個葉子結點。
- 2022-10-25
滿二叉樹要麼度為0要麼度為2,所以又0個度為1的結點。
最後一層葉子結點數 (n+1) / 2,分支結點是 n - (n+1) / 2 = (n-1)/2。
如果一棵二叉樹的結點要麼是葉子結點,要麼它有兩個子結點,這樣的樹就是滿二叉樹。(一棵滿二叉樹的每一個結點要麼是葉子結點,要麼它有兩個子結點,但是反過來不成立,因為完全二叉樹也滿足這個要求,但不是滿二叉樹)。
擴充套件資料:
從根結點開始,假設根結點為第1層,根結點的子節點為第2層,依此類推,如果某一個結點位於第L層,則其子節點位於第L+1層。由m(m≥0)棵互不相交的樹構成一片森林。如果把一棵非空的樹的根結點刪除,則該樹就變成了一片森林,森林中的樹由原來根結點的各棵子樹構成。
滿二叉樹要麼度為0要麼度為2,所以又0個度為1 的結點
最後一層葉子結點數 (n+1) / 2,分支結點是 n - (n+1) / 2 = (n-1)/2
一棵深度為5的滿二叉樹有 2的(n-1)次方減1 個分支結點和 2的(n-1)次方 個葉子結點
即 15 16