精华内容
下载资源
问答
  • 判断是否是平衡二叉树定义:平衡二叉树任何一个节点的左右子树的高度差值小于等于1分析:我们需要判断左右子树的高度,这里可以利用后序遍历来实现,后序遍历可以先遍历左子树,获取到左子树的高度leftHeight;...

    上篇文章分享了二叉树的遍历方法,本文我们利用这几种遍历方法来解决二叉树中的几个问题。

    判断是否是平衡二叉树

    定义:平衡二叉树任何一个节点的左右子树的高度差值小于等于1

    分析:我们需要判断左右子树的高度,这里可以利用后序遍历来实现,后序遍历可以先遍历左子树,获取到左子树的高度leftHeight;再获取到右子树的高度rightHeight,然后做差值。

    代码:

    16db069c9c033d1afde1f1d2962a439a.png
    2bda292d0c5964426b6bdd5079cf509a.png

    判断是否是搜索二叉树

    定义:搜索二叉树就是左边的节点小于当前节点,右边节点大于当前节点

    分析:只需要中序遍历,并且前面的节点是小于后面的节点就可以了

    代码:这里用递归版的中序遍历改的

    87609beaa8d1ed5e44bbda115ce71c1b.png

    判断是否是完全二叉树

    定义:若设二叉树的深度为k,除第k层外,其他各层(1~(k-1)层)的节点数都达到最大值,且第k层所有的节点都连续集中在最左边,这样的树就是完全二叉树。

    分析:只需要层次遍历,如果当前节点有右孩子,但是没有左孩子,直接返回false;

    如果当前节点不是左右孩子都全,则后续节点肯定为叶子节点

    代码

    b865719412b016ea3d1f3167fd44874b.png

    希望对大家有所帮助,有帮助记得点赞哦!可以关注下,后面持续分享编程类的文章,谢谢!

    展开全文
  • 判断二叉树是否是完全二叉树,主要判断有2点 1、如果当前节点没有左孩子,则当前节点不应该有右孩子。 2、如果当前节点没有左孩子或者右孩子,则当前节点的兄弟节点(这里一般是指该节点父节点的右孩子)不应该有子...

    判断二叉树是否是完全二叉树,主要判断有2点
    1、如果当前节点没有左孩子,则当前节点不应该有右孩子。
    2、如果当前节点没有左孩子或者右孩子,则当前节点的兄弟节点(这里一般是指该节点父节点的右孩子)不应该有子节点。

    package com.aekc.algorithm;
    
    import java.util.LinkedList;
    
    /**
     * @author Twilight
     */
    public class CompleteBinaryTree {
    
        class Node {
            public int value;
            public Node leftNode;
            public Node rightNode;
    
            public Node(int value) {
                this.value = value;
            }
        }
    
        public Node buildTree() {
            LinkedList<Node> queue = new LinkedList<>();
            Node head = new Node(treeValue[0] - '0');
            queue.offer(head);
            for(int i = 1; i < treeValue.length; i = i + 2) {
                Node node = queue.poll();
                if(node == null) {
                    break;
                }
                if(treeValue[i] != '#') {
                    node.leftNode = new Node(treeValue[i] - '0');
                    queue.offer(node.leftNode);
                } else {
                    node.leftNode = null;
                }
                if(i + 1 < treeValue.length && treeValue[i + 1] != '#') {
                    node.rightNode = new Node(treeValue[i + 1] - '0');
                    queue.offer(node.rightNode);
                } else {
                    node.rightNode = null;
                }
            }
            return head;
        }
    
        public boolean isCompleteBinaryTree(Node root) {
            if(root == null) {
                return false;
            }
            LinkedList<Node> queue = new LinkedList<>();
            queue.offer(root);
            boolean flag = true;
            while(!queue.isEmpty()) {
                Node node = queue.poll();
                // 如果flag为false,说明当前节点的兄弟节点(当前节点的父亲节点的左孩子)没有左孩子或者右孩子,或者没有子节点。
                if(!flag) {
                    // 如果有孩子
                    if(node.leftNode != null || node.rightNode != null) {
                        return false;
                    }
                }
                if(node.leftNode != null) {
                    queue.offer(node.leftNode);
                } else {
                    // 如果当前节点没有左孩子,则该节点不应该有右孩子,这里设置标识
                    flag = false;
                }
                if(node.rightNode != null) {
                    queue.offer(node.rightNode);
                    // 如果flag为false,则代表该节点没有左孩子
                    if(!flag) {
                       return false;
                    }
                } else {
                    // 如果该节点没有右孩子,则他的兄弟节点不能有子节点,这里设置标识
                    flag = false;
                }
            }
            return true;
        }
    
        /**
         *       1
         *   2      3
         * 4   #  6   7
         */
        private char[] treeValue = {'1', '2', '3', '4', '#', '6', '7'};
    
        public static void main(String[] args) {
            CompleteBinaryTree tree = new CompleteBinaryTree();
            Node node = tree.buildTree();
            System.out.println(tree.isCompleteBinaryTree(node));
        }
    }
    
    
    展开全文
  • * 基于秩实现的完全二叉树节点 */ package dsa; public class ComplBinTreeNode_Rank extends BinTreeNode implements BinTreePosition { private Vector T;//所属的树 private int rank;//在所属树中的秩 ...
  • 给出一个完全二叉树的层序遍历,判断该二叉树是不是一个堆,若是一个堆,则判断是最大堆还是最小堆,并输出后序遍历 题解: 依次检查所有节点(除了根节点)和它的父节点的关系,判断是否破坏最大堆或者最小堆的性质...

    在这里插入图片描述
    在这里插入图片描述

    题目大意:

    给出一个完全二叉树的层序遍历,判断该二叉树是不是一个堆,若是一个堆,则判断是最大堆还是最小堆,并输出后序遍历

    题解:

    依次检查所有节点(除了根节点)和它的父节点的关系,判断是否破坏最大堆或者最小堆的性质,如果有不满足的情况将maxl或minnl置为0,以此排除最大堆或者最小堆。后序遍历直接套板子即可。

    代码如下:

    #include<iostream>
    #include<vector>
    #include<stdio.h>
    #include<math.h>
    #define MAX 10005
    using namespace std;
    
    int m,n,a[1005];
    
    void postorder(int root){
        if(root>n) return;
        postorder(2*root);
        postorder(2*root+1);
        printf("%d%s",a[root],root==1?"\n":" ");//输出的小技巧,最后输出空格还是换行
    }
    
    int main(){
        scanf("%d%d",&m,&n);
        while(m--){
            int minl=1,maxl=1;
            for(int i=1;i<=n;i++){
                scanf("%d",&a[i]);
            }
            for(int i=2;i<=n;i++){
                if(a[i]>a[i/2]) maxl=0;
                if(a[i]<a[i/2]) minl=0;
            }
            if(maxl==1){
                printf("Max Heap\n");
            }else if(minl==1){
                printf("Min Heap\n");
            }else{
                printf("Not Heap\n");
            }
            postorder(1);
        }
        return 0;
    }
    
    展开全文
  • 用数组方式存储完全二叉树(使用场景举例:最大堆) 如何存储 ...因为是完全二叉树,所以需要判断是不是叶子节点,那为什么这么判断呢?因为完全二叉树节点数量就相当于等比数列增长嘛,比值是2 ...

    用数组方式存储完全二叉树(使用场景举例:最大堆)

    如何存储

    数组0号元素放元素的个数,1放根节点,后面放其他元素,一共n个元素。

    怎样找到父节点

    n/2嘛,就找到了父节点

    怎样找到左孩子和右孩子节点

    左孩子:n × 2
    右孩子:n × 2 + 1

    怎样确定叶子节点

    i > n/2 ?
    大于就是叶子节点
    因为是完全二叉树,所以需要判断是不是叶子节点,那为什么这么判断呢?因为完全二叉树的节点数量就相当于等比数列增长嘛,比值是2

    展开全文
  • 可以根据完全二叉树的性质来判断,在线性存储结构下,左孩子下标 = 2 * 父节点, 右孩子下标 = 2 * 父节点下标+ 1; 我们在输入节点过程中,如果一个节点是别人的孩子节点,那么他一定是根节点,这样在输入完成后,...
  • 理论如果给定输入列表A[1..n],其中n=len(A),则堆排序算法需要先构建一个最大堆,即最大元素总是位于根节点处,且所有子节点不大于其父节点。由于最大元素位于根节点A[1]处,因此我们可以通过如下步骤对A进行排序...
  • 二叉树的基本操作Node* GetParent(Node* x) //得到父节点 { if ( _pRoot == NULL) return _pRoot; return _GetParent(_pRoot, x); } Node* Find(const T& value) //查找结点 { ret
  • 然后我们可以从根节点开始遍历,如果是完全二叉树,那么最后一个节点的编号一定等于节点数,可以看图中蓝色部分,我们只需要用一个maxn记录dfs过程中最大值,最后判断一下与n的关系即可 代码 #include<iostream&...
  • 给出一棵二叉树,判断其是否为完全二叉树。 Input Format 第一行,N&lt;1000000,表示二叉树节点数。 默认序号为0的节点为树根。接下来共N-1行,依次表示序号为1,...,N-1的节点的父亲节点序号。 如果一个...
  • 树的常用概念根节点(Root)、叶子节点(Leaf)、父节点(Parent)、子节点(Child)、兄弟节点(Siblings),还有节点的高度、深度以及层数,树的高度。Root: Top node in a treeChild: Nodes that are next to each other ...
  • 完全二叉树的顺序存储方法将的树(顺序存储ABICFJMDEG)保存到数组a中;并实现从键盘输入一个字母,查找该字母是否在树中,如果在,请输出它的父亲结点、左孩子结点和右孩子结点,没有有关结点的,请输出相关信息。 ...
  • 而二叉树又有很多特殊的结构,如斜二叉树、满二叉树、完全二叉树、线索二叉树(排序二叉树)、平衡二叉树等。这里我们先不做深究,先来实现二叉树这种数据结构。二叉树中的节点本身可以存储数据,而且有一个父节点,两...
  • 二叉树

    2019-04-17 16:43:00
    3、找指定二叉树,给定两个节点最近的父节点 4、判断是不是BST树 5、AVL平衡树 6、红黑树: 7、完全二叉树 8、求根节点到叶子节点的最短路径的节点个数 9、DFS和BFS 10、根到叶节点数字之和 11、二叉树序列...
  • 解法:用递归来实现,从A树的根节点开始,判断其所有的节点是不是依次和树B相同,如不同,递归调用函数,继续判断树A当前节点的左子树的所有节点或右子树的所有节点是否和树B所有节点相同,直到遍历到树A的叶子...
  • 顺序二叉树通常只考虑完全二叉树 第 n个元素的左子节点为 2 × n + 1 第 n个元素的右子节点为 2 × n + 2 第 n个元素的父节点为(n-1) ÷2 其中n 表示二叉树中的第几个元素(从0开始编号) 2.2、 顺序二叉树...
  • 二叉树(Binary Tree)回顾在前面的文章中,我们对于二叉树的一些基本概念进行了回顾,同时对比了线性结构与树形结构,总结了一些常见的二叉树的性质,像二叉树,真二叉树,完全二叉树,以及满二叉树等等,但是,我们...
  • 二叉树的实现(C语言)头文件二叉树节点结构的定义及操作函数的声明各种二叉树操作函数的实现二叉树...父节点求二叉树叶子节点个数求二叉树第k层节点个数克隆二叉树判断二叉树是否是完全二叉树比较两个二叉树是否相等...
  • 从A树的根节点开始,判断其所有的节点是不是依次和树B相同,如不同,递归调用函数,继续判断树A当前节点的左子树的所有节点或右子树的所有节点是否和树B所有节点相同,直到遍历到树A的叶子节点,如果不是完全相同...
  • 文章目录二叉树二叉树的定义二叉树的实现二叉树的操作遍历先根遍历(Pre ...节点判断两棵二叉树是否相等判断两棵二叉树是否镜像判断是否为完全二叉树翻转二叉树(镜像二叉树)判断是否是二叉查找树判断是否是平衡二叉树...
  • 创建二叉树已知中序遍历结果和后序遍历结果,创建二叉树输出第K层的元素节点在二叉树中查找元素求已知结点的父节点判断二叉树是否是满二叉树判断二叉树是否为完全二叉树二叉树的顺序存储递归实现中序遍历非递归实现...
  • 如果不是完全二叉树,按照完全二叉树一一对应起来,需要设置一位Empty来判断是否有数据 i的左子树2i i的右子树2i+1 结点为i的结点,父节点为i/2向下取整 链式存储 struct ElemType{ int value; }; typedef ...
  • 二叉树的基本用法总结

    千次阅读 2016-09-11 11:08:35
    下面列举了二叉树的一些常用方法,水平...兄弟的查找,父节点的查找; 计算树的深度、叶子数、节点数; 树的拷贝; 判断两个树是否相等; 判断是否是满树、完全树; #include #include #include #include #include usi
  • 主要操作是以下: 创建二叉树 克隆二叉树 ...判断一棵树是否是完全二叉树 创建二叉树树的定义是递归创建的,所以创建树也可以递归地创建一棵树,首先需要一个序列,按什么顺序来创建,我采用了前序的遍历方
  • 思路:由于是完全二叉树,所以若节点的左子结点存在的话,其右子节点必定存在,所以左子结点的next指针可以直接指向其右子节点,对于其右子节点的处理方法是,判断父节点的next是否为空,若不为空,则指向其next...
  • 思路:用递归来实现,从A树的根节点开始,判断其所有的节点是不是依次和树B相同,如不同,递归调用函数,继续判断树A当前节点的左子树的所有节点或右子树的所有节点是否和树B所有节点相同,直到遍历到树A的叶子...
  • 给出一个完全二叉树的层序遍历序列,判断其是大顶堆、小顶堆还是不是堆。 【思路】 因为通常我们静态存储二叉树在数组中也是以层序存的。所以可以直接读入序列存在数组中。 输出路径:先序遍历(不过注意要先访问右...
  • 二叉排序树与平衡二叉树的实现

    热门讨论 2010-12-26 15:25:31
    建立二插排序树,首先用一个一维数组记录下读入的数据,然后再用边查找边插入的方式将数据一一对应放在完全二叉树相应的位置,为空的树结点用“0” 补齐。 1.2.2 建立二叉排序树 二叉排序树是一种动态树表。其特点...
  • 怎么判断是不是堆序列

    万次阅读 2017-08-30 02:32:20
    先画出完全二叉树结构,判断是否满足 最大堆:左右孩子都比父节点小 最小堆:左右孩子都比父节点大 例如:下面的序列中,()是堆 正确答案: A  1,2,8,4,3,9,10,5 1,5,10,6,7,8,9,2 9,8,7,6,4,8,2,1 9...

空空如也

空空如也

1 2 3 4 5 6
收藏数 111
精华内容 44
关键字:

完全二叉树判断父节点