精华内容
下载资源
问答
  • 所以判断完全二叉树须满足两个条件: 1所有叶子节点处的深度均为二叉树的深度 2不存在只有右孩子而没有孩子的节点 求深度即可,主要是递归有点绕 递归一次,深度加一,返回一次,深度减一 #include<iostream> ...

    完全二叉树定义:一棵深度为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;
    }
    
    展开全文
  • 代码+注释】判断完全二叉树

    千次阅读 2020-06-29 22:36:18
    给我们一棵二叉树,我们可以一眼认出是否是...但是作为数据结构一种,咱们先学好再说,到以后做一些项目可能灵感会来得快点,废话不多说,今天内容是用代码判断完全二叉树 核心代码块:   /*判断完全二叉树*/

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


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

    核心代码块:

    /*判断完全二叉树*/
    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,那么1 ~ (n-1) 层节点都达到最大个数,即1 ~ (n-1) 层是满二叉树,n 层节点全都连续排列在靠左边。 代码思路:(分两个阶段来判定) 第一阶段–>   每个节点都有两个子树,...

    1 二叉树的层序遍历

      二叉树的层序遍历即,按照层一排一排的读取节点的值,如下图,层序遍历得到的就应该是:“1234567”。
    在这里插入图片描述

    public static void levelOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        // 创建一个链表,然后将根节点放到链表中
        Queue<TreeNode> result = new LinkedList<>();
        result.offer(root);
        // 将头节点取出并打印,并把它非空的左右子树放入链表
        // 循环执行,每次取出头节点
        // 下一次进入取头节点就是取到上一个节点的左孩子,以此类推
        while (true) {
            TreeNode cur = result.poll();
            if (cur == null) {
                break;
            }
            System.out.print(cur.val);
            if (cur.left != null) {
                result.offer(cur.left);
            }
            if (cur.right != null) {
                result.offer(cur.right);
            }
        }
    }

    2 判断是否是完全二叉树

    完全二叉树概念:
      完全二叉树是从满二叉树而来的,满二叉树即每一个节点都有两个子节点或者没有子节点。
      完全二叉树是指若树的深度为 n,那么1 ~ (n-1) 层的节点都达到最大个数,即1 ~ (n-1) 层是满二叉树,n 层的节点全都连续排列在靠左边。

    代码思路:(分两个阶段来判定)
    第一阶段–>
      每个节点都有两个子树,如果某个节点没有子树,那么进入第二阶段;如果某个节点只有右子树没有左子树,直接返回false;如果某个节点只有左子树没有右子树,也进入第二阶段。
    第二阶段–>
      每个节点都必须没有子树,如果遇到有子树的节点则判定 false。

    public static boolean isCompleteTree(TreeNode root) {
        // 通过层序遍历的方式来实现
        if (root == null) {
            return true;
        }
        // 分为两个阶段判定
        // 这个变量为 false ,表示当前是第一阶段
        // 变量名为 true 表示进入第二阶段
        boolean isLevel2 = false;
    
        // 利用层序遍历
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(true) {
            TreeNode cur = queue.poll();
            // cur == null 说明整个树已经遍历完了
            if (cur == null) {
                break;
            }
    
            // 针对当前节点进行访问
            // 此处的访问是一系列的逻辑判断
            if (!isLevel2) {
                // 第一阶段的逻辑
                if (cur.left != null && cur.right != null) {
                    // 符合要求的节点,继续往下遍历
                    // 此时直接把左右子树入队列
                    queue.offer(cur.left);
                    queue.offer(cur.right);
                } else if (cur.left == null && cur.right != null) {
                    // 第一阶段发现只有右子树的节点
                    // 说明这个树一定不是完全二叉树
                    return false;
                } else if (cur.left != null && cur.right == null) {
                    // 遇到了这个节点不符合第一阶段的条件
                    // 进入到第二阶段进行判定
                    isLevel2 = true;
                    queue.offer(cur.left);
                } else {
                    // 这个节点没有子树
                    // 也是进入到第二阶段进行判定
                    // 因为上一个 elseif 中需要入队列,所以这两步不能合并
                    isLevel2 = true;
                }
            } else {
                // 第二阶段的逻辑
                if (cur.left != null || cur.right != null) {
                    // 发现第二阶段的某个节点的子树不为空
                    // 此时就不是完全二叉树
                    return false;
                }
            }
    
        }
        // 遍历了整个树,都没有找到反例 return false,就 return true
        return true;
    }

    在这里插入图片描述

    展开全文
  • 完全二叉树的判断

    2019-01-11 15:53:42
    文章目录完全二叉树的判断完全二叉树思路代码关于作者 完全二叉树的判断 各种二叉树的判断是经常出现的题目,这里给出的是完全二叉树的判断。 完全二叉树 第一次看到概念觉得很晦涩,但是结合图一下就知道是不是一棵...

    完全二叉树的判断

    各种二叉树的判断是经常出现的题目,这里给出的是完全二叉树的判断。

    完全二叉树

    第一次看到概念觉得很晦涩,但是结合图一下就知道是不是一棵完全二叉树。不知道的完全二叉树的同学先自行搜索相关概念。

    思路

    既然树的题目逃不过遍历,那么在四种遍历挑选一种同学们觉得哪种遍历能够解决问题,直觉告诉我就是层次遍历,不要说这是瞎扯,结合完全二叉树的概念,很明显先中后序没有办法完成,那就用层次遍历试试吧。
    这不是递归,没有办法去描述递归公式,但是怎么描述一棵树是完全二叉树呢,似乎不好描述,那么就用正反结合来论述吧,情况如下:

    1. 一个节点没有左孩子,却有右孩子
    2. 如果一个节点只有左孩子,没有右孩子,那么之后的节点应该全部为叶节点
    3. 一个叶节点之后出现的节点只能是叶节点

    代码

    /**
     * Definition for a binary tree node.
     * type TreeNode struct {
     *     Val int
     *     Left *TreeNode
     *     Right *TreeNode
     * }
     */
    func isCompleteTree(root *TreeNode) bool {
        
        if root == nil {
            return true
        }
        
        queue := list.New()
        queue.PushFront(root)
        
        // 标志之后的节点应当全部为叶节点
        flag := false
        var tem *TreeNode
        for queue.Len() != 0 {
            tem = queue.Back().Value.(*TreeNode)
            queue.Remove(queue.Back())
            
            if flag {
                if tem.Left != nil || tem.Right != nil {
                    return false
                }
                continue
            } 
    
            if tem.Left == nil && tem.Right != nil {
                return false
            }
            
            // 情况2或3满足就开启flag这个过程
            // 这里用异或更简洁,但是golang提示布尔值之间不允许异或
            if !(tem.Left != nil && tem.Right != nil) {
                flag = true
            }
            
            
            if tem.Left != nil {
                queue.PushFront(tem.Left)
            }
            if tem.Right != nil {
                queue.PushFront(tem.Right)
            }
        }
        
        return true
    }
    

    关于作者

    大四学生一枚,分析数据结构,面试题,golang,C语言等知识。QQ交流群:521625004。微信公众号:后台技术栈。
    image

    展开全文
  • 当我们出队时,遇上了NULL,我们便对队列内元素进行判断,如果队列中全部为空,那么他便是一颗完全二叉树代码实现 typedef char BTDataType; typedef struct BinaryTreeNode { struct BinaryTr
  • 判断完全二叉树

    千次阅读 2016-10-24 19:50:33
    二叉树采用二叉链表存储,设计算法判断给定二叉树是否是一棵完全二叉树。 核心代码: int IsCompleteTree(BiTree Bt) { Sq q;BiTree e; InitSq(q); InSq(q,Bt);//根节点入队列 OutSq(q,e); while(e!= NULL)/...
  • 给定一棵二叉树,已经其中没有重复值节点,请判断该二叉树是否为搜索二叉树和完全二叉树代码 import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode ...
  • 前言我是很喜欢算法的,打算写一个数据结构与算法系列的记录,很...二叉树二叉树的定义首先我们准备一颗二叉树:我们需要定义一些术语,我们所使用的数据结构由结点组成,结点包含的链接可以为空也可以指向其他结点. 在二...
  • 数据结构学习笔记分享(C/C++)偶然的机会,在bilibli上看到了郝斌老师教的《数据结构入门》,课程录制时间是...于是花了几个星期的晚上,把这门课给听完了,相关的代码也跟着老师敲了一遍,笔记也整理了一下,并自...
  • 这里面有10个数据结构:数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树;10个算法:递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法。掌握了这些...
  • 数据结构之后有可能会有上机考试,基本考点不会超出课本范围,整理一拨儿方便日后复习~~数据结构类型:逻辑结构,存储结构,对数据运算一.线性表核心知识点:线性表逻辑结构特性:数据元素之间存在线性关系,...
  • 从计算机统考大纲来看,数据结构部分及其相关知识点,数据结构占了45分,和计算机组成原理部分同一个比重,这足以体现计算机专业研究生选拔对数据结构课程重视程度。针对这样情况,小编为各位考生精心准备了一些...
  • 完全二叉树的不对称性决定了判断是不是一棵二叉树是不是完全二叉树最好要用非递归广度优先遍历。 在一般的广度优先遍历中,出队一个结点后检查是否有左右孩子,有的话相应孩子进队。 在这道题中,无论有没有左右...
  • 完全二叉树的节点个数-----------如果让你数一下一棵普通二叉树有多少个节点,这很简单,只要在二叉树的遍历框架上加一点代码就行了。但是,如果给你一棵完全二叉树,让你计算它的节点个数,你会不会?算法的时间...
  • 判断二叉树是否为完全二叉树 判断方法 使用层遍历 如果一个节点只有右孩子没有左孩子,那么不是完全二叉树 如果一个节点只有左孩子没有右孩子,或者没有孩子,后面节点必须全是叶节点 代码 #include <...
  • 重点为二者非递归,递归主要是在理解二者非递归思想时用于对比 递归重要一点就是必须先解决子问题,再基于子问题来解决当前问题。 即先进后出, 故递归转非递归时用栈来解决。 启发博文:...
  • 百度百科中对完全二叉树的定义如下: 若设二叉树的深度为 h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。(注:第 h 层可能包含 1~2h2^h2h ...
  • 这里面有10个数据结构:数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树;10个算法:递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法。掌握了这...
  • 给定一棵二叉树,已经其中没有重复值节点,请判断该二叉树是否为搜索二叉树和完全二叉树。 示例1 输入 复制 {2,1,3} 输出 复制 [true,true] 备注: n≤500000 分析: BST特点:左子值比根节点小,右子值比根节点大 ...
  • 完全二叉树的判断 实现代码 二叉搜索树 实现代码 完全二叉树 定义 在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为...
  • 判断完全二叉树:算法摘自百度百科。 代码: import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * } */ public class Solutio
  • 上图展示的树很明显是一颗非完全二叉树,博主就用这棵树来讲解一下博主对于判断完全二叉树的算法思想。 最好结合代码一起思考。 算法思想:运用队列进行操作根节点入队后迭代操作以下步骤 1.判断队首...
  • AVL树的构造和完全二叉树的判断 记录一下,以后方便复习 AVL树的构造是模板题。 完全二叉树的判断:层次遍历,如果出现一个结点不存在左或右儿子,标记一下。如果又出现一个这样的结点,那么就不是完全二叉树。 ...
  • 判断树是否是空树,若为空树则为完全二叉树 若树为非空完全二叉树,则借助队列层序遍历二叉树(空分支也入队),若出队碰到空分支,则说明之前结点都不为空,那么队列中结点都应该是空分支。若不满足上述,则...
  • 算法思想:检查二叉树是否为完全二叉树思想就是与满二叉树做对比,可知完全二叉树只有最右面是空。采用层次遍历方式在入队列过程中空指针也要进行入队若空指针后面还有非空元素则该二叉树不是完全二叉树 ...
  • 有一棵二叉树,请设计一个算法判断它是否是完全二叉树。 给定二叉树的根结点root,请返回一个bool值代表它是否为完全二叉树。树的结点个数小于等于500。 思路 二叉树层次遍历。当结点只有右子树没有左子树时不是...
  • 给定一棵二叉树,已经其中没有重复值的节点,请判断该二叉树是否为搜索二叉树和完全二叉树。 输入描述: 第一行输入两个整数 n 和 root,n 表示二叉树的总节点个数,root 表示二叉树的根节点。 以下 n 行每行三个整数...

空空如也

空空如也

1 2 3 4 5 ... 18
收藏数 358
精华内容 143
关键字:

判断完全二叉树的代码