嚴(yán)蔚敏那本教材上的說法：一個(gè)深度為k，節(jié)點(diǎn)個(gè)數(shù)為 2^k - 1 的二叉樹為滿二叉樹。這個(gè)概念非常好理解，

就是一棵樹，深度為k，而且沒有空位。

首先對(duì)滿二叉樹依照廣度優(yōu)先遍歷（從左到右）的順序進(jìn)行編號(hào)。

一顆深度為k二叉樹，有n個(gè)節(jié)點(diǎn)，然后，也對(duì)這棵樹進(jìn)行編號(hào)，假設(shè)全部的編號(hào)都和滿二叉樹相應(yīng)，那么這棵樹是全然二叉樹。

?

隨意的一個(gè)二叉樹，都能夠補(bǔ)成一個(gè)滿二叉樹。這樣中間就會(huì)有非常多空洞。在廣度優(yōu)先遍歷的時(shí)候，假設(shè)是滿二叉樹，或者全然二叉樹，這些空洞是在廣度優(yōu)先的遍歷的末尾，所以，但我們遍歷到空洞的時(shí)候，整個(gè)二叉樹就已經(jīng)遍歷完畢了。而假設(shè)，是非全然二叉樹，

我們遍歷到空洞的時(shí)候，就會(huì)發(fā)現(xiàn)，空洞后面還有沒有遍歷到的值。這樣，僅僅要依據(jù)是否遍歷到空洞，整個(gè)樹的遍歷是否結(jié)束來推斷是否是全然的二叉樹。

算法例如以下：

bool is_complete(tree *root) { queue q; tree *ptr; // 進(jìn)行廣度優(yōu)先遍歷（層次遍歷），并把NULL節(jié)點(diǎn)也放入隊(duì)列 q.push(root); while ((ptr = q.pop()) != NULL) { q.push(ptr->left); q.push(ptr->right); } // 推斷是否還有未被訪問到的節(jié)點(diǎn) while (!q.is_empty()) { ptr = q.pop(); // 有未訪問到的的非NULL節(jié)點(diǎn)，則樹存在空洞，為非全然二叉樹 if (NULL != ptr) { return false; } } return true; }

總結(jié)

以上是生活随笔為你收集整理的怎样推断一棵二叉树是全然二叉树的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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