判断一棵二叉树是不是完全二叉树的算法,求指教

如题所述

看它最下面一层,缺少的节点是不是从最右侧开始缺少。如果是的话那么它就是完全二叉树。
温馨提示:答案为网友推荐,仅供参考
第1个回答  2014-12-21
看它的节点个数是不是2的n次方,n是二叉树的高度追问

这个明显不行,从个数上看不出来结构的

追答

只要满足等式,就是完全二叉树,你知道完全二叉树是怎么定义吗?

追问

完全二叉树叶子节点必须是从右边缺着,照你这么说左边缺着也叫完全二叉树……

追答

搞错了,我以为是满二叉树

第2个回答  2014-12-20
去看看呗追问

第3个回答  2014-12-21
你好追答

遍历一次这个二叉树。在遍历过程中记录两个值,一个是当前已经遍历的变量数(如 Counter),一个是最大的变量号(如 LastNum)。变量编号按以下规则分配:
⑴ 根结点编号为 1 ;
⑵ 对于某个编号为 n 的结点,其左子结点(若存在)的编号为 2n,其右子结点(若存在)的编号为 2n + 1。
遍历完成后,得到两个号码,对其比较,若 Counter 与 LastNum 相等,则说明是完全二叉树,若 LastNum 较大,则不是。

记得采纳哦

追问

对啊,有理!那我还有问题,怎么给节点编码?用层次遍历的方法给每个节点编码,这个编码应不应该是节点类的属性之一呢?那岂不是要改一下节点类新添一个编号属性?我的理解对不对?

追答

采纳,哥们儿

追问

刚看到,不好意思

本回答被提问者采纳
相似回答