精华内容
下载资源
问答
  • 满二叉树的特点:除了最后一层没有任何子节点,非最后一层的节点,都必须有左右节点 按照这个思想,我们可以开始去设计递归思路了 要学会善于发现! 我们通过观察满二叉树的结构可以发现,树的左右结构完全对称。...

    满二叉树的特点:除了最后一层没有任何子节点,非最后一层的节点,都必须有左右节点

    按照这个思想,我们可以开始去设计递归思路了

    要学会善于发现!

    • 我们通过观察满二叉树的结构可以发现,树的左右结构完全对称。
    • 左右对称的两个节点都必须有左右子节点,并且他们的左右子节点的下一层全不为空或者都为空

    根据上述的两个思路,我们就可以写代码了

     public boolean isFullBST(TreeNode root) {
            return isFullBST(root,root);
        }
    //  q 为左侧结构节点, p为右侧结构节点  p和q在结构上对称存在 
     public boolean isFullBST(TreeNode q,TreeNode p) {
            if(q==null&&p==null){return true;}  //判断结构是否为左右对称
            if(q==null||p==null){return false;} //判断结构是否为左右对称
    //堆成的两个节点p和q都有子孩子时
            if(q.left!=null&&q.right!=null&&p.left!=null&&p.right!=null){  
    //     p和q的下一层节点全满或都为空,返回true
                if(q.left.left==null&&q.left.right==null&&q.right.left==null&&q.right.right==null
                   &&p.left.left==null&&p.left.right==null&&p.right.left==null&&p.right.right==null){
                    return true;
                }
            }
            if(q.left==null||q.right==null||p.left==null||p.right==null){  //q和p节点中不全为空
                return false;
            }
            return isFullBST(q.left,p.right)&&isFullBST(q.right,p.left);  //递归
        }

    测试结果如下

     

     

    展开全文
  • 判断二叉树是否为满二叉树

    千次阅读 2019-10-30 20:37:05
    根据满二叉树的高度与节点个数之间的关系,很容易判断一棵树是否为FBT,只需要求树其树高和节点个数即可。 代码实现: struct node { int val; node *left, *right; }; int height(node *root) { if (!root) re....

    满二叉树的定义:一个高度为h,并且含有2^h - 1个节点的二叉树称为满二叉树,下文称呼满二叉树为FBT。

    根据满二叉树的高度与节点个数之间的关系,很容易判断一棵树是否为FBT,只需要求树其树高和节点个数即可。

    代码实现:

    struct node {
    	int val;
    	node *left, *right;
    };
    
    int height(node *root) {
    	if (!root) return 0;
    	int left  = height(root->left);
    	int right = height(root->right);
    	return max(left, right) + 1; 
    }
    
    
    void count(node *root, int &sum) {
    	if (root) {
    		sum += 1;
    		count(root->left);
    		count(root->right);
    	}
    }
    
    bool isFBT(node *root) {
    	if (!root) return 1;
    	int sum = 0;
    	int h = height(root);
    	count(root, sum);
    	return sum == pow(2, h) - 1;
    }
    
    展开全文
  • 本文介绍了判断一颗二叉树是不是平衡、完全、满二叉树,并给出C++代码

    目录

    1 判断二叉树是不是平衡二叉树

    2 判断二叉树是不是完全二叉树

    3 判断二叉树是不是满二叉树


    在这之前,我们假设二叉树节点的结构如下:

    typedef struct binaryTreeNode
    {
    	int mData;
    	binaryTreeNode * mLeft;
    	binaryTreeNode * mRight;
    };

    1 判断二叉树是不是平衡二叉树

    首先来科普一下什么是平衡二叉树,学过数据结构的应该都知道,这毕竟不是什么新鲜的问题。

    首先大家对二叉查找树(二叉排序树)有所了解。 首先平衡二叉树是一棵二叉查找树,另外,以平衡二叉树中所有节点为根的树的左右子树高度之差的绝对值不超过1。

    所以在判断二叉树是不是平衡二叉树之前,我们先应该去判断这颗树满足不满足平衡二叉树的基本条件,即这颗树是不是二叉查找树,对于二叉查找树,我们知道由于它满足左小右大的规则,所以二叉查找树的中序遍历序列是从小到大有序的。我们可以根据这个特点去判断一个二叉树是不是二叉查找树

    见下面代码:

    int predit = INF;//假设INF为已定义的常量,它小于树中的任何值,用predit记录当前访问节点的前驱的值
    bool JustBST(binaryTreeNode* root)
    {
    	if (root == NULL)//空树也是二叉查找树
    		return true;
    	bool b1 = JustBST(root->mLeft);//递归的判断左子树是否是二叉排序树
    	if (b1 == false || predit > root->mData)//左子树不是二叉排序树或者predit的值大于当前根节点的值,则该树不是二叉排序树
    		return false;
    	predit = root->mData;//将要访问右子树的时候,predit记录下当前根节点的值
    	bool b2 = JustBST(root->mRigjt);//递归去判断右子树是否为二叉排序树
    	return b2;
    }

    判断完了二叉树是不是二叉排序树之后,我们再来判断这棵树满足不满足二叉平衡树的性质。

    可以递归的去判断左子树是否是平衡的,右子树是否是平衡的,然后再通过比较高度差,判断自身是否是平衡的。见如下代

    bool isBalanced(binaryTreeNode* root)
     {
            if(root==NULL)
                return true;
            //判断左右子树是否平衡,并且判断高度差
            if(isBalanced(root->mLeft)&&isBalanced(root->mRight)&&abs(height(root->mLeft)-height(root->mRight))<=1)
                return true;
            return false;
        }
        //得到深度
        int height(binaryTreeNode*root)
        {
            if(root==NULL) return 0;
            int l =  height(root->mLeft)+1;
            int r = height(root->mRight)+1;
            return l>r?l:r;
        }

    2 判断二叉树是不是完全二叉树

    首先我们知道,如果一个二叉树的深度为k,且1~k-1层的节点数都达到了最大个数,且第k层的节点都集中在左边,那么这样的二叉树就是一个完全二叉树,如下图所示,是一个完全二叉树:

    可以看出一颗完全二叉树只可能最后一层的节点不是满的。因此我们可以采用层次遍历的方法来进行判断,在遍历的时候我们只去判断当前节点为不为空,不管子节点为不为空都入队。

    如上图所示,当遍历完10这个元素的时候,对列里面全是为NULL的元素,这个时侯我们遍历到一个空元素,这时候不再入队,只需判断队中元素有没有不为空的元素,如果有,那么这个树就不是完全二叉树。

    bool IsComTree(binaryTreeNode* t)
    {
    	if (t == NULL)
    		return true;
    	//对列
    	queue<binaryTreeNode*> que;
    	que.push(t);
    	while (t=que.front())
    	{
    		//无论子节点为不为空,都入队
    		que.push(t->mLeft);
    		que.push(t->mRight);
    		que.pop();
    	}
    	while (!que.empty())
    	{
    		if (que.front())
    			return false;
    		que.pop();
    	}
    	return true;
    }

    3 判断二叉树是不是满二叉树

    在一棵二叉树中,如果所有的分支节点都有左右孩子,并且叶子节点都集中在最后一层,那么这二样的二叉树称为满二叉树,如下图所示:

    由于满二叉树的特性,我们可以得满二叉树的一些特性:

    1. 一个层数为k的满二叉树的节点总数为2的k次方j减1,一定是奇数个。
    2. 第i层节点数为2的i减1次方。

    因此在判断一颗二叉树是不是满二叉树的时候,可以用上述的两个性质来判断。

    int Count(binaryTreeNode* t)
    {
    	if (t == NULL)
    		return 0;
    	return 1 + Count(t->mLeft) + Count(t->mRight);
    }
    
    int TreeDeep(binaryTreeNode* t)
    {
    	if (t == NULL)return 0;
    	int left = TreeDeep(t->mLeft) + 1, right = TreeDeep(t->mRight) + 1;
    	return left > right ? left : right;
    }
    bool IsFullTree(binaryTreeNode* t)
    {
    	if (t == NULL)
    		return true;
    	//节点数
    	int num = Count(t);
    	//层数
    	int deep = TreeDeep(t);
    	if (num == pow(2, deep) - 1)
    		return true;
    	return false;
    }

     

    展开全文
  • 判断一个二叉树是否为满二叉树

    千次阅读 2015-04-09 19:50:35
    数据结构作业……本来想随便抄一份,结果网上的代码好麻烦的样子orz一个...代码如下/**判断一个二叉树是否为满二叉树 */ #include #include <cstdlib>struct BiTree { int data; BiTree * lchild; BiTree * rc

    数据结构作业……本来想随便抄一份,结果网上的代码好麻烦的样子orz

    一个满二叉树节总结点数等于2^最大深度-1
    满二叉树

    最大深度可通过层次遍历求出。
    代码如下

    /**< 判断一个二叉树是否为满二叉树 */
    #include <cstdio>
    #include <cstdlib>
    
    struct BiTree
    {
        int data;
        BiTree * lchild;
        BiTree * rchild;
    };
    
    void build(BiTree * &tr)
    {
        int data;
        scanf("%d", &data);
        if (data == -1)
        {
            tr = NULL;
        }
        else
        {
            tr = (BiTree *)malloc(sizeof(BiTree));
            tr->data = data;
            build(tr->lchild);
            build(tr->rchild);
        }
    }
    
    void print(BiTree *tr)
    {
        if (tr != NULL)
        {
            printf("%d ", tr->data);
            print(tr->lchild);
            print(tr->rchild);
        }
    }
    
    bool isFull(BiTree * tr)
    {
        //1 << 最大深度 = 节点个数 +1
        struct Node
        {
            BiTree *tree;
            int cnt;           //深度
        };
        Node que[100];         //通过数组实现简单队列
        if (tr == NULL)
            return true;
        int rear = 0, front = 0;
        que[rear].tree = tr;
        que[rear].cnt = 0;
        int deep = 0;
        int tot = 0;
        while (rear >= front)
        {
            if (que[front].tree != NULL)
            {
                tot++;
                que[++rear].tree = que[front].tree->lchild;  //入队
                que[rear].cnt = que[front].cnt + 1;
                que[++rear].tree = que[front].tree->rchild;  //入队
                que[rear].cnt = que[front].cnt + 1;
                if (deep < que[rear].cnt)
                    deep = que[rear].cnt;
            }
            front++;  //出队
        }
        printf("\ndeep=%d, tot=%d\n", deep, tot);
        return 1 << deep == tot + 1;
    }
    
    int main()
    {   //1 2 -1 -1 3 -1 -1
        //1 2 4 -1 -1 -1 3 5 -1 -1 6 -1 -1
        //1 2 3 -1 -1 4 5 -1 -1 6 -1 -1 7 -1 -1
        BiTree *tr;
        printf("请以先序遍历输入结点数据,输入-1表示该结点为空\n");
        build(tr);
        printf("建好的树先序输出如下\n");
        print(tr);
        printf("\n该二叉树%s满二叉树", isFull(tr) ? "是" : "不是");
    
        return 0;
    }
    展开全文
  • 基本思路:(1)某节点没有做孩子...具体实现:先层次遍历二叉树到一个队列。然后从队列头部开始(i=1),进行判断(按照基本思路)。 代码如下: int is_Comp_Tree(BTNode *b) { int i=1; BTNode *Qu[Max...
  • 【经典算法实现 28】广度优优先 - 创建满二叉树 完整代码实现一、广度优先算法思路二、循环队列实现2.1 循环队列测试代码运行结果三、广度优优先算法 - 创建满二叉树3.1 算法实现3.2 完整代码 (带详细注释)3.3 ...
  • 判断的方式和判断满二叉树的方式很相似。 完整代码如下: #include<iostream> #include<algorithm> using namespace std; typedef struct node{ char val; struct node* left; struct node* ...
  • 一棵二叉树,除最后一层外,是一棵满二叉树,最后一层可以不满,但是必须从左往右连续的有。 完全二叉树的不对称性决定了判断是不是一棵二叉树是不是完全二叉树最好要用非递归广度优先遍历。 在一般的广度优先遍历...
  • 给定一棵二叉树,已经其中没有重复值的节点,请判断二叉树是否为搜索二叉树和完全二叉树。 示例1 输入 复制 {2,1,3} 输出 复制 [true,true] 备注: n≤500000 分析: BST特点:左子值比根节点小,右子值比根节点大 ...
  • 算法思想:检查二叉树是否为完全二叉树思想就是与满二叉树做对比,可知完全二叉树只有最右面是空的。采用层次遍历的方式在入队列的过程中空指针也要进行入队若空指针后面还有非空元素则该二叉树不是完全二叉树 ...
  • 在完全二叉树中,除了最底层节点可能没填外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层,则该层包含 1~2^h个节点。 完全二叉树判断 采用按层遍历...
  • 给出一个二叉树判断是否是完全二叉树。 分析:我们都知道完全二叉树是指最后一层左边是的,右边可能慢也不能不满,然后其余层都是的,根据这个特性,利用层遍历, 如果我们当前遍历到了NULL结点即叶结点,...
  • 左神算法基础class4—题目6判断一棵二叉树是否是平衡二叉树1.题目:判断一棵二叉树是否是平衡二叉树2.分析(1)平衡二叉树的概念(2)二叉树题解套路3.核心代码(1)树的建立(2)...满二叉树一定是平衡二叉树,平衡...
  • 判断一个二叉树是否是完全二叉树

    千次阅读 2013-02-24 08:22:34
    判断一个二叉树是否是完全二叉树 思路:在层序遍历的过程中,找到第一个非节点(non-full node)。节点(full-node)指的是同时拥有左右孩子的节点。在找到第一个非节点之后,剩下的节点不应该有孩子节点;如果有...
  • 对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 算法思想 判断树是否是空树,若为空树则为完全二叉树 若树为非空完全二叉树,则...
  • 废话不说,直接上代码: #include&amp;lt;iostream&amp;gt; #include&amp;lt;cmath&amp;gt; #define MAXSIZE 1024 struct tree{ char data; tree *lchild; tree *rchild; }; using ...
  • 如果二叉树中除去最后一层节点为满二叉树,且最后一层的结点依次从左到右分布,则此二叉树被称为完全二叉树。 直接上思路。层序遍历一下,遇到第一个叶子 那么后面出现的节点都应该是叶子节点。当然 还要判断上图...
  • 完全二叉树判断

    2017-05-07 18:20:20
    完全二叉树:如果一棵具有N个结点的二叉树的结构与满二叉树的前N个节点的结构相同,称为完全二叉树。 所以就分了以下几种情况: 该节点有左右子树,继续判断 该节点只有左子树,判断他的下一个节点还有没有子树...
  • 昨天的文章讲述了二叉树的先序、中序和后序的遍历方法(递归和非递归),但是这种遍历方法有什么意义么?今天来讲讲这些算法可以用来做什么,只要稍加更改,我们就可以得到...完全二叉树:只有最后一层不需要铺,其...
  • 树 二叉树 /* 二叉树的构造 */ /* 二叉树的遍历 */ /* 二叉树的基础操作 */ /* 二叉树的相关判断 */ ...// 判断二叉树是否是满二叉树 // 判断二叉树是不是二叉排序树 // 判断二叉树是不是平衡二叉树 ...
  • 完全二叉树的判断完全二叉树的n-1层是一颗满二叉树,最后一层的节点依次从左到右。所以只要n-1层第一次出现只有一个左孩子没有有孩子的情况或者没有左孩子的情况就做一个标记,往后的遍历的过程中如果还出现了有节点...
  • 昨天的文章讲述了二叉树的先序、中序和后序的遍历方法(递归和非递归),但是这种遍历方法有什么意义么...完全二叉树:只有最后一层不需要铺,其余各层均是的状态! 平衡二叉树:每个节点的左子树和右子树的高度...
  • 完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。(来自百度) ...
  • 首先看什么是完全二叉树 ...这里给出的思想是把所有二叉树的节点入队列,然后遇到NULL停止,看栈中剩余的是否还有空节点,若有的话则为满二叉树,没有的话则不是,可以对照代码理解思想,这里不难理解
  • 完全二叉树:一棵具有N个节点的二叉树的结构与满二叉树的前N个节点的结构相同 如何判断一个树是完全二叉树 可以使用层序遍历,只需2个步骤 第一步:如果遍历到一个节点只有右子树没有左子树,则不是完全...
  • 二叉树分类`完全二叉树`:`满二叉树`:1.1 常用的操作树:2. 二叉树的遍历2.1 前序遍历2.2 中序遍历2.3 后序遍历2.4 层序遍历3. 根据`前序和中序遍历` 或 `后序和中序遍历`还原二叉树4. 二叉树的深度:5. 判断是否...
  • 完全二叉树其实就是最后一层没有满的满二叉树。 上图: a为完全二叉树,b为满二叉树。 由于完全二叉树的定义,所以我们只要遍历每层的每个节点判断除了倒数一二层的节点外是否还有缺少左右节点的子节点,若有则不是...
  • 鉴别完全二叉树

    2020-05-05 10:44:46
    一颗 k 层 n 个节点的完全二叉树,和 k 层的满二叉树按层序遍历的前 n 个节点形状一致。所以,一颗完全二叉树中的任何节点如果有右儿子,那么一定有左儿子。且层序遍历时,一旦出现空节点,后续节点必定全为空。可以...

空空如也

空空如也

1 2 3 4
收藏数 76
精华内容 30
关键字:

判断满二叉树代码