满二叉树和完全二叉树到底有什么区别，他们定义不是差不多？

满二叉树是指除最后一层外，每一层上的所有结点有两个子结点，则k层上有2k-1个结点深度为m的满二叉树有2m-1个结点。
完全二叉树是指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。

倒霉熊lujin · 2018-4-30 01:12:45

差别就在最后一层上，
满二叉树定义，除最后一层外，每一层上的所有节点有两个子节点，也就是说倒数第二层的每个节点都有两个子节点，那么最后一层的节点数一定是倒数第二层的2倍，所以最后一层一个节点都不能缺。
而完全二叉树，在最后一层的节点是可以缺少的，其节点数可能是倒数第二层节点数的2倍（满二叉树一定是完全二叉树），也可能是1个，2个，只不过，这些缺的节点只能是最右边的。

哪些美好 · 2018-4-30 01:12:46

楼下的答案能解释为什么叶子结点会出现在倒数第二层的吗？？按你说的最后一层只能缺少右边的的结点那么倒数第二层一定不肯能是叶子节点啊

满二叉树和完全二叉树到底有什么区别，他们定义不是差不多？

2 个回复