如何判断二叉树是满二叉树？

如何判断二叉树是满二叉树~

满二叉树的判断方法：
除最后一层无任何子节点外，每一层上的所有结点都有两个子结点（最后一层上的无子结点的结点为叶子结点）。也可以这样理解，除叶子结点外的所有结点均有两个子结点。节点数达到最大值。所有叶子结点必须在同一层上。




结点（如果一颗树深度为h，最大层数为k）：
1、它的叶子数是： 2^(h-1)；
2、第k层的结点数是： 2^(k-1)；
3、总结点数是： 2^k-1 (2的k次方减一)；
4、总节点数一定是奇数。

二叉树的的遍历或者叫周游算法教材上都应该有。跟那个基本一样。就是多一句判断一个结点是否左右均有子结点，或者均无子结点。
void judge（BinNode* rt）
{
if（rt==NULL||k==0）return； //判断空树或者非满
if（（rt->leftchild()==NULL）！=（rt->rightchild()==NULL）//左右子结点是否都为空，或均不为空
k=0；//全局变量，初值为1，为零就说明不是满二叉树
judge（rt->leftchild()）；
judge（rt->rightchild()）；//递归遍历判断
}
很久没弄不知道细节有误没有，意思应该没错

满二叉树的判断方法：

除最后一层无任何子节点外，每一层上的所有结点都有两个子结点（最后一层上的无子结点的结点为叶子结点）。也可以这样理解，除叶子结点外的所有结点均有两个子结点。节点数达到最大值。所有叶子结点必须在同一层上。

结点（如果一颗树深度为h，最大层数为k）：

1、它的叶子数是： 2^(h-1)；

2、第k层的结点数是： 2^(k-1)；

3、总结点数是： 2^k-1 (2的k次方减一)；

4、总节点数一定是奇数。

完全二叉树的定义：深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称为完全二叉树。
特点：叶子结点只可能在层次最大的两层上出现；对任一结点，若其右分支下子孙的最大层次为l，则其左分支下子孙的最大层次必为l 或l+1

满二叉树：一棵深度为k，且有2的(k)次方－1个节点的二叉树
特点：每一层上的结点数都是最大结点数

最简单的就是： 求出二叉树的深度。。。和节点的总个数。。。然后满足公式就行了。。。
层次书和 节点总个数 满足 1+2+4+8+ 2的层次次方= 节点总个数。。就行了呗。。

完全二叉树的定义：深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称为完全二叉树。
特点：叶子结点只可能在层次最大的两层上出现；对任一结点，若其右分支下子孙的最大层次为l，则其左分支下子孙的最大层次必为l 或l+1

满二叉树：一棵深度为k，且有2的(k)次方－1个节点的二叉树
特点：每一层上的结点数都是最大结点数

最简单的就是： 求出二叉树的深度。。。和节点的总个数。。。然后满足公式就行了。。。
层次书和 节点总个数 满足 1+2+4+8+ 2的层次次方= 节点总个数。。就行了呗。。

全二叉树(Complete Binary Tree)： 若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的节点都连续集中在最左边，这就是完全二叉树。

判断很简单，广度优先搜索整个二叉树，一旦找一个不含有子节点或者只含有一个左子节点之后，那么后续的所有节点都必须是叶子节点。否则，该树就不是完全二叉树。

---

萨迦县19582383401： 判断一棵二叉树是否为完全二叉树算法 - ？
贸性雅博： 假设为完全二叉树 找到第一个非叶子结点,判断其是否是只有左孩子或左右孩子都有.此后判断其前面的结点是否都有左右孩子.

萨迦县19582383401： 急急~判断一棵二叉树是满二叉树的算法!？
贸性雅博： 我的思路是利用满二叉树的性质来判断.满二叉树一定符合 节点数 = 2的n次方 -1 (n为深度) 所以可以先遍历二叉树,并记录深度和节点数,最后做出判断 #include<stdio.h> void inorder(bintree *t,int currentDeep) { if(*t!=NULL) { if(...

萨迦县19582383401： 大佬看一下,这种算不算满二叉树 - ？
贸性雅博： 这个不算满二叉树,但是它是一个完全二叉树,满二叉树要在右下角再加两个节点,简单的说就是要把右下角补满,而完全二叉树只需要从左到右顺序一致就行,所以这个是完全二叉树而不是满二叉树.

萨迦县19582383401： ,判断一棵树是否为完全二叉树,并将其图形化c++ - ？
贸性雅博： 判断一棵树是否为完全二叉树,有以下几种情况:(1),倒数第二层不是满二叉树;(2),最后一层从左往右不是连续的有节点;(3),最后一层从左到右一次又节点.使用队列的方法来进行判断一棵树是否为完全二叉树.

萨迦县19582383401： 如何判断二叉树是否是完全二叉树 递归 - ？
贸性雅博： bool isComplete(TreeNode * root, bool &isFull, int &deep) { isFull = true; if (root == NULL) //空树为完全(且满)二叉树 return true; isFull = false; if (root->left == NULL && root->right != NULL)//右子树存在,左子树不存在则不是完全二叉树 return ...

萨迦县19582383401： 满二叉树和完全二叉树到底有什么区别,他们定义不是差不多?满二叉树是指除最后一层外,每一层上的所有结点有两个子结点,则k层上有2k - 1个结点深度... - ？
贸性雅博：[答案] 差别就在最后一层上,满二叉树定义,除最后一层外,每一层上的所有节点有两个子节点,也就是说倒数第二层的每个节点都有两个子节点,那么最后一层的节点数一定是倒数第二层的2倍,所以最后一层一个节点都不能缺.而完全二叉...

萨迦县19582383401： 判断完全二叉树 - ？
贸性雅博： #include int main() { int t[1024] = {0}; int p[1024] = {0}; int m,r; scanf(＂%d%d＂, &m, &r); t[0]=p[0]=m; t[1]=r; p[r]=1; while(--p[0]) { scanf(＂%d%d＂, &m,&r); if(p[m]==0 && p[r]!=0) // m is not in tree yet, m is r's right node { int np=p[r]*2+1; t[np] = m; p[m...

萨迦县19582383401： 判断二叉树是否为满二叉树 (C++描述) - ？
贸性雅博： 倒是对的,但你不觉得太麻烦了吗?一道初三题不用这么做,如果是满二叉树结点数一定是2的n次方-1,直接判断就行了!

萨迦县19582383401： 如何计算满二叉树或者是完全二叉树的叶数 - ？
贸性雅博： 满二叉树定义:一棵深度为k,且有2的(k)次方-1个节点的二叉树 如果已知深度k,那么叶数为2的(k-1)次方个叶子 如果已知总节点数n (n = 2的(k)次方- 1),那么叶数为(n + 1) / 2 比如一个深度为3的满二叉树,一共有7个节点(第1层1个,第2层2个,第3层4个),叶子数为4 (4 = 2的(3 - 1)次方, 4 = (7 + 1) / 2 完全二叉树的定义:深度为k,有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时,称为完全二叉树 完全二叉树的叶子数为(n + 1) / 2取下整 例如5个节点的完全二叉树,第二层2个节点,其中右节点为叶子;第三层2个节点都是叶子

萨迦县19582383401： 完全二叉树和满二叉树的区别 - ？
贸性雅博： 完全二叉树的定义:深度为k,有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时,称为完全二叉树.特点:叶子结点只可能在层次最大的两层上出现;对任一结点,若其右分支下子孙的最大层次为l,则其左分支下子孙的最大层次必为l 或l+1 满二叉树:一棵深度为k,且有2的(k)次方-1个节点的二叉树 特点:每一层上的结点数都是最大结点数