簡(jiǎn)單來(lái)說(shuō), 完全二叉樹(shù)是指按照層次進(jìn)行遍歷的時(shí)候所得到的序列與滿二叉樹(shù)相對(duì)應(yīng)
這里提供兩種思路和相應(yīng)的代碼:
1. 利用與滿二叉樹(shù)的對(duì)應(yīng)關(guān)系
任意的一個(gè)完全二叉樹(shù), 都可以補(bǔ)上一些空節(jié)點(diǎn)來(lái)形成一棵滿二叉樹(shù), 當(dāng)然了, 這些補(bǔ)上的節(jié)點(diǎn)都是葉子節(jié)點(diǎn).我們假設(shè)這些補(bǔ)上的節(jié)點(diǎn)為空節(jié)點(diǎn), 那么在對(duì)這棵補(bǔ)成滿二叉樹(shù)的樹(shù)進(jìn)行層次遍歷的時(shí)候, 那些補(bǔ)上的空節(jié)點(diǎn)都一定會(huì)出現(xiàn)在遍歷序列的結(jié)尾, 就是一系列的原節(jié)點(diǎn)后面跟著一系列補(bǔ)上的空節(jié)點(diǎn), 不會(huì)交替出現(xiàn). 利用上述性質(zhì), 可以肯定, 如果空節(jié)點(diǎn)和原節(jié)點(diǎn)交替出現(xiàn)了, 那么這棵樹(shù)一定不是完全二叉樹(shù).
// 由于如何用程序比較簡(jiǎn)單的實(shí)現(xiàn)把二叉樹(shù)補(bǔ)滿, 我暫時(shí)沒(méi)有思路...
2. 根據(jù)完全二叉樹(shù)的性質(zhì)在層次遍歷的過(guò)程中做判斷
具體流程如下:
- 對(duì)二叉樹(shù)進(jìn)行層次遍歷
- 如果當(dāng)前節(jié)點(diǎn)有右孩子, 沒(méi)有左孩子, 返回 false
- 如果當(dāng)前節(jié)點(diǎn)有左孩子, 沒(méi)有右孩子, 那么之后的節(jié)點(diǎn)都必須為葉子節(jié)點(diǎn)(即沒(méi)有孩子), 否則返回 false
- 遍歷過(guò)程中如果不返回 false, 遍歷結(jié)束后返回 true
function isCompleteBinaryTree(root)
{
let result = true
let leaf
root.levelIterate(function(node)
{
if( ! touch(node))
{
result = false
return false // 終止遍歷
}
})
return result
/*
* 層次遍歷過(guò)程中對(duì)每個(gè)節(jié)點(diǎn)執(zhí)行的操作
*
* @param node - 當(dāng)前節(jié)點(diǎn)
*/
function touch(node)
{
if(leaf)
{
return ( ! node.left) && ( ! node.right)
}
else
{
if(node.right && ! node.left)
{
return false
}
if(node.left && ! node.right)
{
leaf = true
}
// node.left && node.right
return true
}
}
}
