精华内容
下载资源
问答
  • 判断满二叉树

    2020-07-26 08:49:28
    判断二叉树是否是二叉树 思路:二叉树的叶子结点数=2的(n-1)次方,n代表树的高度(一个结点表示树的高度为1) */ #include <iostream> #include <cstdlib> #include <cmath> using namespace ...
    /*
    判断二叉树是否是满二叉树
    思路:满二叉树的叶子结点数=2的(n-1)次方,n代表树的高度(一个结点表示树的高度为1) 
    */
    #include <iostream>
    #include <cstdlib>
    #include <cmath>
    using namespace std;
    typedef char ElemType;
    typedef struct BiTNode{
    	ElemType data;
    	struct BiTNode *lchild, *rchild;
    }*BiTree;
    void CreateTree(BiTree &t){
    	ElemType e;
    	cin >> e;
    	if(e=='#')
    		t = NULL;
    	else{
    		t = (BiTree)malloc(sizeof(BiTNode));
    		t->data = e;
    		CreateTree(t->lchild);
    		CreateTree(t->rchild);
    	}
    }
    void Countleaves(BiTree T, int &count){
    	if(T){
    		if(!T->lchild && !T->rchild)	//叶子结点 
    			count++;
    		Countleaves(T->lchild, count);
    		Countleaves(T->rchild, count);
    	}
    }
    int getDepth(BiTree t){
    	int lchildDepth, rchildDepth;
    	if(!t)	return 0;	//空树的高度为0
    	else{
    		lchildDepth = getDepth(t->lchild);
    		rchildDepth = getDepth(t->rchild);
    		return (lchildDepth>rchildDepth) ? (lchildDepth+1) : (rchildDepth+1);
    	} 
    }
    bool isFullTree(BiTree t) {
    	int leaves;
    	Countleaves(t, leaves);
    //	cout << leaves << " " << getDepth(t) << endl;
    	if(t==NULL){
    		return false;
    	}else if(int(pow(2, getDepth(t)-1)) == leaves){
    		return true;
    	}else{
    		return false;
    	}
    }
    int main(){
    	BiTree t;
    	int count;
    	cout << "输入二叉树(先序、空树用#表示):";
    	CreateTree(t);
    	if(isFullTree(t)){
    		cout << "该树是满二叉树"  << endl;
    	}else{
    		cout << "该树不是满二叉树" << endl;
    	}
    	return 0;
    }
    

    程序小白,如果代码中有任何问题,欢迎指出。

    展开全文
  • 判断一棵二叉树是不是满二叉树 除最后一层无任何孩子外,每一层上的所有结点都有左右孩子的二叉树叫做满二叉树判断一棵二叉树是不是满二叉树,首先是递归的方法: 空树是满二叉树,非空的树当且仅当它的左右...

    判断一棵二叉树是不是满二叉树

    除最后一层无任何孩子外,每一层上的所有结点都有左右孩子的二叉树叫做满二叉树。

    判断一棵二叉树是不是满二叉树,首先是递归的方法:

    空树是满二叉树,非空的树当且仅当它的左右子树都是满二叉树的时候,它就是一棵满二叉树。

    每个子树应当满足:① 同时存在左子树和右子树;② 左右子树高度相同。

    /*每个节点都存在左右孩子并且左右子树深度相同时是满二叉树*/ 
    int Height(Tree& t){
    	if(t == NULL) return 0;
    	return Height(t->left) > Height(t->right) ? Height(t->left) + 1 : Height(t->left) + 1;
    } 
    
    bool isFullTree(Tree& t){
        if(t == NULL) return true;
    	return isFullTree(t->left) && isFullTree(t->right) && Height(t->left) == Height(t->right);
    }

    非递归的办法:

    利用广度优先遍历,记录每层的宽度,判断每层的宽度是否符合 2 ^(n - 1)。

    bool levelOrder(Tree& t) {
        if(t == NULL) return 0;
        queue<TreeNode*> q;
        int num = 1; //num控制每一层的结点个数,根结点只有一个节点
        q.push(t);
        while(!q.empty()){ 
            int width = q.size();
            for(int i = 0;i < width;i++){
            	TreeNode* s = q.front();
            	q.pop();
            	if(s->left) q.push(s->left);
            	if(s->right) q.push(s->right);
        	}
        	if(width < num) return false; //只要有一层出队个数小于num,那么就不是一棵满二叉树
        	else num *= 2;
    	}
        return true;
    }

    总的代码如下:

    #include<iostream>
    #include<queue>
    using namespace std;
    
    typedef struct node{
    	char val;
    	struct node* left;
    	struct node* right;
    }TreeNode,*Tree;
    
    //非递归 
    /*由根向下进行广度优先遍历,判断每层是否为满*/ 
    bool levelOrder(Tree& t) {
        if(t == NULL) return 0;
        queue<TreeNode*> q;
        int num = 1; //num控制每一层的结点个数,根结点只有一个节点
        q.push(t);
        while(!q.empty()){ 
            int width = q.size();
            for(int i = 0;i < width;i++){
            	TreeNode* s = q.front();
            	q.pop();
            	if(s->left) q.push(s->left);
            	if(s->right) q.push(s->right);
        	}
        	if(width < num) return false; //只要有一层出队个数小于num,那么就不是一棵满二叉树
        	else num *= 2;
    	}
        return true;
    }
    
    //递归 
    /*每个节点都存在左右孩子并且左右子树深度相同时是满二叉树*/ 
    int Height(Tree& t){
    	if(t == NULL) return 0;
    	return Height(t->left) > Height(t->right) ? Height(t->left) + 1 : Height(t->left) + 1;
    } 
    
    bool isFullTree(Tree& t){
        if(t == NULL) return true;
    	return isFullTree(t->left) && isFullTree(t->right) && Height(t->left) == Height(t->right);
    }
    
    void CreateTree(Tree& t){
    	char x;
    	cin>>x;
    	if(x == '#') t = NULL; 
    	else{
    		t = new TreeNode; 
    		t->val = x;  
    		CreateTree(t->left); 
    		CreateTree(t->right); 
    	}
    } 
    
    int main(){
    	Tree t;
    	CreateTree(t);
    	/*
    	   a b d # # e # # c f # # #
    	*/
    	/*
    	   a b d # # e # # c f # # g # #
    	*/
    	cout<<"isFullTree:"<<endl;
    	cout<<isFullTree(t)<<endl; 
    	cout<<"levelOrder:"<<endl;
    	cout<<levelOrder(t); 
    }

    运行结果:

     

    展开全文
  • 满二叉树判定

    2012-04-13 16:02:33
    判断一个给定的二叉树是否为满二叉树。 不考虑空树情况。 注意:空树和只有一个结点的树均是满二叉树
  • 完全二叉树定义:一棵深度为k的有n个结点的二叉树,对树中的结点按从上至下、从左到右的顺序进行编号,如果编号为i(1≤i≤n)的结点与满二叉树中编号为i的结点在二叉树中的位置相同,则这棵二叉树称为完全二叉树。...

    完全二叉树定义:一棵深度为k的有n个结点的二叉树,对树中的结点按从上至下、从左到右的顺序进行编号,如果编号为i(1≤i≤n)的结点与满二叉树中编号为i的结点在二叉树中的位置相同,则这棵二叉树称为完全二叉树。

    所以判断完全二叉树须满足两个条件:
    1所有叶子节点处的深度均为二叉树的深度
    2不存在只有右孩子而没有孩子的节点
    求深度即可,主要是递归有点绕
    递归一次,深度加一,返回一次,深度减一

    #include<iostream>
    using namespace std;
    #define  ElemType  char
     struct BiTree {
    	ElemType data;
    	 BiTree* Lchild, * Rchild;
    };
    void createBiTree(BiTree* &T)
    {
    	ElemType temp;
    	temp = getchar();
    	if (temp == '#')
    	{
    		T = NULL;
    	}
    	else
    	{
    		T = new BiTree;
    		T->data = temp;
    		createBiTree(T->Lchild);
    		createBiTree(T->Rchild);
    	}
    }
    void InOrder(BiTree* T)
    {
    	if (T)
    	{
    		InOrder(T->Lchild);
    		cout << T->data;
    		InOrder(T->Rchild);
    	}
    }
    void Deepth(BiTree* T,int& temp, int& n)
    {
    	if (T)
    	{
    		temp++;
    		Deepth(T->Lchild,temp,n);
    		Deepth(T->Rchild,temp,n);
    	}
    	else 
    	{
    		if (temp > n)
    			n = temp;
    		temp--;
    	}
    }
    void IsBest(BiTree* T, int &n, int &temp,bool &temp1)
    {
    	if (T)
    	{
    		temp++;
    		if (T->Lchild == NULL && T->Rchild!=NULL)
    			temp1 = false;
    		IsBest(T->Lchild, temp, n,temp1);
    		IsBest(T->Rchild, temp, n,temp1);
    	}
    	else
    	{
    		if (temp != n)
    			temp1 = false;
    		temp--;
    	}
    }
    int main()
    {
    	BiTree* T;
    	bool temp1=true;
    	T = NULL;
    	int temp, n;
    	temp = 0;
    	n = 0;
    	createBiTree(T);
    	InOrder(T);
    	Deepth(T, temp, n);
    	temp = 0;
    	cout << n;
    	IsBest(T, n, temp,temp1);
    	if (!temp1)
    		cout << "no";
    	else
    		cout << "yes";
    	return 0;
    }
    
    展开全文
  • 给我们一棵二叉树,我们可以一眼认出是否是完全二叉树,现在如何用代码判断完全二叉树呢? 我之前去百度了一下完全二叉树,上面说完全二叉树是一种效率极高的数据结构,究竟高在什么地方呢,说实话,我也不知道哈哈...

    给我们一棵二叉树,我们可以一眼认出是否是完全二叉树,现在如何用代码判断完全二叉树呢?


    我之前去百度了一下完全二叉树,上面说完全二叉树是一种效率极高的数据结构,究竟高在什么地方呢,说实话,我也不知道哈哈哈哈哈,上网搜了一圈也没有找到让我信服的答案,有兴趣的小伙伴可以上网查一查,可能是我现在的水平还不足以体会到完全二叉树有什么特殊的效果吧,但是作为数据结构的一种,咱们先学好再说,到以后做一些项目可能灵感会来得快点,废话不多说,今天的内容是用代码判断完全二叉树

    核心代码块:

    /*判断完全二叉树*/
    int isComplete(BiTreeNode *root)
    {
        //只有根结点,当然是完全二叉树
        if (root->leftChild == NULL && root->rightChild == NULL)
            return 1;
        Queue queue, *p1,*p2;
        p1 = &queue;
        p2 = &queue;
        initiateQueue(p1);
        queueAppend(p1,root);    //将根结点入队列
        BiTreeNode q;
        while (1)
        {
            BiTreeNode *temp = (BiTreeNode*)malloc(sizeof(BiTreeNode));
            getHead(p1, temp);
            if (temp->data == '0')   //直到队列为空,跳出循环
                break;
            queuePop(p1, &q);
            queueAppend(p1, temp->leftChild);    //将出队的左孩子结点入队
            queueAppend(p1, temp->rightChild);
        }
        while (isNotEmpty(p2))
        {
            BiTreeNode *temp = (BiTreeNode*)malloc(sizeof(BiTreeNode));
            getHead(p1, temp);
            if (temp->data != '0')       //如果队列不为空,就不是完全二叉树
                return 0;
            queuePop(p2, &q);
        }
        return 1;
    }
    

    代码思想:

    1. 完全二叉树中间不会缺少结点

    2. 中间缺少结点的二叉树就不是完全二叉树,否则即是Complete binary tree

    3. 利用队列首先将根结点入队,再将根结点出队

    4. 将出队结点的左孩子结点入队

    5. 将出队结点的右孩子结点入队

    6. 在进行一次出队,重复4,5步骤,直到出队的结点没有数据(即空结点)

    7. 如果队列不为空,一直出队,如果出队的结点不是无数据的结点,那么就不是完全二叉树;如果出队的结点全是无数据的结点,那么是完全二叉树

    8. 当然需考虑特殊情况,例如二叉树只有一个根结点等等

    以上步骤就能判断二叉树中间是否有缺少的结点


    实例代码:

    注:实例由4个文件构成:《BiTree.h》《Domin.h》《Queue.h》《main.c》,本文核心代码块放在《Domin.h》头文件内
    《BiTree.h》

    #pragma once
    /*二叉树基本操作头文件*/
    #include<stdio.h>
    #include<stdlib.h>
    typedef char DataType;   //声明数据类型
    struct  BiTreeNode
    {
        DataType data;
        BiTreeNode *leftChild;
        BiTreeNode *rightChild;
    };
    //初始化二叉树
    void  initiateBiTree(BiTreeNode **root)
    {
        (*root) = (BiTreeNode*)malloc(sizeof(BiTreeNode));
        (*root)->leftChild = NULL;
        (*root)->rightChild = NULL;
    }
    //插入左孩子结点
    BiTreeNode* leftInsert(BiTreeNode *curr, DataType data)
    {
        if (curr == NULL)
            return NULL;
        BiTreeNode *node = (BiTreeNode*)malloc(sizeof(BiTreeNode));
        node->data = data;
        node->rightChild = NULL;
        node->leftChild = curr->leftChild;
        curr->leftChild = node;
        return node;
    }
    //插入右孩子结点
    BiTreeNode* rightInsert(BiTreeNode *curr, DataType data)
    {
        if (curr == NULL)
            return NULL;
        BiTreeNode *node = (BiTreeNode*)malloc(sizeof(BiTreeNode));
        node->data = data;
        node->leftChild = NULL;
        node->rightChild = curr->rightChild;
        curr->rightChild = node;
        return node;
    }
    //前序遍历二叉树
    void preOrder(BiTreeNode *root)
    {
        if (root != NULL)
        {
            printf("%c ", root->data);
            preOrder(root->leftChild);
            preOrder(root->rightChild);
        }
    }
    //中序遍历
    void midOrder(BiTreeNode *root)
    {
        if (root != NULL)
        {
            preOrder(root->leftChild);
            printf("%c ", root->data);
            preOrder(root->rightChild);
        }
    }
    

    《Domin.h》

    #pragma once
    #include"Queue.h"
    #include"BiTree.h"
    /*二叉树的功能头文件*/
    /*判断完全二叉树*/
    int isComplete(BiTreeNode *root)
    {
        //只有根结点,当然是完全二叉树
        if (root->leftChild == NULL && root->rightChild == NULL)
            return 1;
        Queue queue, *p1,*p2;
        p1 = &queue;
        p2 = &queue;
        initiateQueue(p1);
        queueAppend(p1,root);    //将根结点入队列
        BiTreeNode q;
        while (1)
        {
            BiTreeNode *temp = (BiTreeNode*)malloc(sizeof(BiTreeNode));
            getHead(p1, temp);
            if (temp->data == '0')   //直到队列为空,跳出循环
                break;
            queuePop(p1, &q);
            queueAppend(p1, temp->leftChild);    //将出队的左孩子结点入队
            queueAppend(p1, temp->rightChild);
        }
        while (isNotEmpty(p2))
        {
            BiTreeNode *temp = (BiTreeNode*)malloc(sizeof(BiTreeNode));
            getHead(p1, temp);
            if (temp->data != '0')       //如果队列不为空,就不是完全二叉树
                return 0;
            queuePop(p2, &q);
        }
        return 1;
    }
    

    《Queue.h》

    #pragma once
    /*队列基本操作头文件*/
    #include"BiTree.h"
    typedef BiTreeNode queueDataType;
    struct QueueNode
    {
        queueDataType data;
        QueueNode *next;
    };
    struct Queue
    {
        QueueNode *head;
        QueueNode *rear;
    };
    void initiateQueue(Queue *queue)
    {
        queue->head = NULL;
        queue->rear = NULL;
    }
    /*判断非空*/
    bool isNotEmpty(Queue* queue)
    {
        if (queue->head == NULL)
            return false;
        return true;
    }
    /*入队函数*/
    void queueAppend(Queue *queue, queueDataType *data)
    {
        QueueNode *node = (QueueNode*)malloc(sizeof(QueueNode));
        if (data != NULL)
        {
            node->data.data = data->data;
            node->data.leftChild = data->leftChild;
            node->data.rightChild = data->rightChild;
        }
        else {
            node->data.data = '0';       // 用0来标记要入队的结点是空的二叉树结点
            node->data.leftChild = NULL;
            node->data.rightChild = NULL;
        }
        node->next = NULL;
        if (queue->rear == NULL)
        {
            queue->head = node;
            queue->rear = node;
        }
        else
        {
            queue->rear->next = node;
            queue->rear = node;
        }
    }
    /*出队函数*/
    void queuePop(Queue*queue, queueDataType *data)
    {
        if (!isNotEmpty(queue))
            return;
        *data = queue->head->data;
        queue->head = queue->head->next;
        if (queue->head == NULL)
            queue->rear = NULL;
    }
    /*取队头元素*/
    void  getHead(Queue *queue,queueDataType *head)
    {
        if (!isNotEmpty(queue))
            head = NULL;
        else
            *head = (queue->head->data);
    }
    /*遍历队列*/
    void print(Queue*queue)
    {
        printf("队列:");
        QueueNode *p;
        p = queue->head;
        while (p!=NULL)
        {
            printf("%c  ",p->data.data);
            p = p->next;
        }
        printf("\n");
    }
    

    《main.c》
    注:为了验证所建立的二叉树是否为指定二叉树,采用前序遍历和中序遍历 输出二叉树的结点

    #include"Queue.h"
    #include"BiTree.h"
    #include"Domin.h"
    int main()
    {
        /*测试二叉树*/
        BiTreeNode *root, *p;
        initiateBiTree(&root);
        p = leftInsert(root, 'A');
        p = leftInsert(p, 'B');
        leftInsert(p, 'D');
        rightInsert(p, 'E');
        p = rightInsert(root->leftChild, 'C');
        leftInsert(p, 'F');
        rightInsert(p, 'G');
        printf("二叉树前序遍历:");
        preOrder(root->leftChild);
        printf("\n");
        printf("二叉树中序遍历:");
        midOrder(root->leftChild);
        printf("\n");
        if (isComplete(root->leftChild))
            printf("该二叉树是完全二叉树!\n");
        else
            printf("该二叉树不是完全二叉树!\n");
        system("pause");
        return 0;
    }
    

    测试结果:


    测试一:是完全二叉树



    测试二:不是完全二叉树

    将主函数稍微变动,注释掉中间的一个结点F

    变成这样一棵二叉树



    代码编译器:Visual Studio 2017
    ok

    展开全文
  • //判断是否为满二叉树(递归法) (结点个数n=2^h-1) /* step: 1)先求该书=树的最大深度h 2)再求结点总个数n 3)若n==2^h-1,则 */ class ReturnInfo { public: int height; int no;//结点个数 ReturnInfo(int ...
  • 1满二叉树 除最后一层无任何子节点外,每一层上的所有结点都有两个子结点的二叉树。一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是说,如果一个二叉树的层数为K,且结点总数是(2...
  • // 6.49 编写算法判别给定二叉树是否为完全二叉树 Status BiTreeIsComplete(BiTree T) { // 思路:完全二叉树的层次遍历应该是没有NULL的 // 实现:把所有的结点都入队列,包括空指针 BiTNode *queue[maxSize], *...
  • 主要介绍了判断二叉树是否为完全二叉树的实例的相关资料,需要的朋友可以参考下
  • 二叉树类binarytree中增加一个功能,判断是否为完全二叉树(使用自定义的队列类完成)
  • 层次遍历判断满二叉树
  • 判断一个二叉树是否为满二叉树

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

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

    千次阅读 2018-08-25 16:28:50
    (一)判断完全二叉树 特点一: 只允许最后一层有空缺结点且空缺在右边,即叶子结点只能在层次最大的两层上出现;  特点二: 对任一结点,如果其右子树的深度为j,则其左子树的深度必为j或j+1 即度为1的点只有1...
  • 判断是否为满二叉树

    2020-09-15 16:09:28
    public class A { class Tree{ int value; Tree left; Tree right; ... public Tree(int value) { ... //判断是否为满二叉树 public static boolean isFBT(Tree tree){ //如果为空,不是二.
  • 判断一棵二叉树是否为满二叉树 1。递归 bool Is_Full(BtNode *ptr) { return ((ptr==NULL) && Is_Full(ptr->leftchild) && Is_Full(ptr->rightchild) && (Get_Depth(ptr->left...
  • 平衡二叉树要求对于二叉树的每一个节点,其左右子树的高度差不大于1。 故解题思路是先递归地求出二叉树的高度,再进行相减,若相减结果绝对值大于1,说明不是平衡二叉树,返回false,否则继续看其左右子树是否为平衡...
  • 里面是关于完全二叉树的判定方法,有两种方法,一种是用队列,另外一种是联想到堆排序算法,堆也是一种完全二叉树,也是一种简单算法,其实两者本质区别不大,只是实现方式略有区别。
  • 判断完全二叉树

    千次阅读 多人点赞 2018-11-19 17:47:33
    完全二叉树的定义: 一棵二叉树,除了最后一层之外都是完全填充的,并且最后一层的叶子结点都在左边。 https://baike.baidu.com/item/%E5%AE%8C%E5%85%A8%E4%BA%8C%E5%8F%89%E6%A0%91/7773232?fr=aladdin 百度定义 ...
  • 3、设二叉树采用二叉链表存储,试编写一个判断任意给定的二叉树是否为满二叉树的算法。 #include #include typedef struct BiTnode {  int data;  struct BiTnode* Lchild,*Rchild; }BiTnode,*BiTree;   ...
  • 判断两颗二叉树是否相似,C语言二叉树部分入门小程序,适合C语言课程的入门小练习 判断两颗二叉树是否相似,C语言二叉树部分入门小程序,适合C语言课程的入门小练习 判断两颗二叉树是否相似,C语言二叉树部分入门...
  • C++判断完全二叉树

    千次阅读 2018-05-17 22:04:09
    #include&lt;iostream&gt; #include&lt;stdlib.h&gt; #include&lt;deque&gt; //插入标准库中的头文件 using namespace std; typedef struct treenode ...//创建二叉树 v...
  • 平衡二叉树的性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是...我们可以使用递归算节点的左右子树节点取较大值,代码如下: class Solution { public: int TreeDepth(TreeN..
  • js代码-13.1 判断是否为平衡二叉树
  • 完全二叉树判断

    千次阅读 2018-11-25 19:14:44
    判断一棵树是否为完全二叉树 1)用递归算法写,左子树的层数永远和右子树的层数永远相同或者左子树层数比右子树层数一为完全二叉树,后经检验发现,某些二叉树满足要求但却不满足完全二叉树的要求,还需要考虑倒数...
  • 博主最近做了一个题目,关于正则二叉树判断,题目并不难,但是很有趣,这里博主描述一下算法思想,并附上代码 网上也有其他教程,但是不同的教程,不同的思路,我们一起进步 思路: 首先,对于二叉树,我们可以...
  • 判断是否完全二叉树python

    千次阅读 2019-06-25 19:52:15
    #File Name : 是否为完全二叉树.py class Node(object): def __init__(self,val=None): self.val = val self.left = None self.right = None def isCBT(head): if not head: retur...
  • 满二叉树的定义:除最后一层是叶子结点,其他各层

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 82,171
精华内容 32,868
关键字:

判断满二叉树代码