`
yyang900427
  • 浏览: 11811 次
  • 性别: Icon_minigender_1
  • 来自: 北京
最近访客 更多访客>>
社区版块
存档分类
最新评论

判断二叉树是否平衡

阅读更多

/** 
 * 题目:输入一棵二叉树的根结点,判断该树是不是平衡二叉树。如果某二叉树
 * 中任意结点的左右子树的深度相差不超过1,那么它就是一棵平衡二叉树
 */

int is_balanced(struct node * root_node, int * depth)
{
    if(root_node == NULL)
    {
        *depth = 0;
        return 1;
    }

    int left, right;

    if(is_balanced(root_node->left_node, &left) && \
        is_balanced(root_node->right_node, &right))
    {
        int diff = left - right;

        if(diff <= 1 && diff >= -1)
        {
            *depth = (left > right ? left : right) + 1;
            return 1;
        }
    }

    return 0;
}


分享到:
评论

相关推荐

    JAVA判断二叉树是否是二叉平衡树

    接下来,我们可以创建一个`BinaryTree`类,包含一个`isBalanced()`方法来判断二叉树是否平衡: ```java public class BinaryTree { public boolean isBalanced(TreeNode root) { if (root == null) { return ...

    判断二叉树是否是平衡二叉树

    判断一颗二叉树是不是平衡二叉树,数据结构算法

    平衡二叉树1

    然后,我们定义主要的函数`isBalanced`,用于判断二叉树是否平衡。这个函数同样使用递归策略。首先,如果根节点为空,我们可以认为这是一个平衡的二叉树,返回`true`。接着,我们计算左子树和右子树的高度差,并使用...

    C,构造二叉树,判断平衡二叉树

    根据给定二叉树的先序遍历和中序遍历结果,构造出该二叉树;给出该二叉树的后序遍历结果;判定该二叉树是否为平衡二叉树;

    题目整理(二叉树).pdf

    - 判断二叉树是否平衡。 - 计算二叉树中双分支节点数。 - 实现二叉树的左右孩子互换。 - 递归删除二叉树中的节点。 - 删除二叉树中值为x的所有节点。 - 求先序遍历中第k个节点的值。 - 求代权路径长度和。 -...

    平衡二叉树判断1

    然后,我们定义了一个Solution类,用于判断二叉树是否是平衡二叉树: ```c class Solution { public: int getdfs(TreeNode* root) { if (root == nullptr) return 0; int leftdepth = getdfs(root-&gt;left); int ...

    二叉树 基本操作(面试)

    2. 判断二叉树是否平衡:计算每个节点的左右子树高度,判断是否存在不平衡的情况。 3. 最大/最小路径和:找到从根节点到叶子节点的路径,使得路径上的节点值之和最大或最小。 4. 二叉树的复制:创建一个新的二叉树...

    写一算法,判断一棵二叉树是否是一棵二叉排序树。

    通过以上分析,我们可以看出无论是递归还是非递归的方法,都能够有效地解决判断二叉树是否为二叉排序树的问题。递归方法虽然简洁易懂,但可能会导致较大的递归深度;而非递归方法虽然稍微复杂一些,但能够有效地控制...

    java 实现平衡二叉树

    文档中是我自己实现的用java语言实现(1)判断给定的二叉树是否平衡;(2)二叉树插入新数据后,如果失衡自我旋转调整的方法。

    数据结构1800题树及二叉树章节答案

    5. **树的高度和平衡**:平衡因子的概念,用于判断二叉树是否平衡,以及计算高度的方法。 6. **二叉搜索树**:关于二叉搜索树的性质及其遍历特性。 7. **树的其他表示法**:双亲链表、孩子链表和孩子兄弟表示法的优...

    平衡二叉树的检索(算法与数据结构课程设计).doc

    核心算法是`void judge(trees *p)`,该函数首先计算节点的平衡因子,然后判断二叉树是否平衡。若不平衡,则根据不平衡类型(R_类或L_类)进行旋转调整,包括RR(左单旋)、RL(先右后左双旋)、LL(右单旋)和LR(先...

    C++类机制实现二叉树数据结构

    在C++编程中,二叉树是一种非常重要的数据结构,它...例如,我们可以很容易地添加新的功能,如判断二叉树是否平衡、计算二叉树的高度等。通过深入理解二叉树和C++的类机制,开发者可以更高效地处理复杂的数据结构问题。

    树与二叉树代码模板.zip

    例如,平衡因子用于判断二叉树是否平衡,对于AVL树,平衡因子的绝对值不能超过1。同时,树的平衡对于保持高效性能至关重要,因为不平衡的树可能导致查找效率降低到接近于线性时间。 在实际问题中,树和二叉树的应用...

    采用字符类型为元素类型和二叉链表为存储结构,实现抽象数据类型二叉树。

    此外,我们还可以实现一些其他功能,比如判断二叉树是否平衡(左右子树的高度差不超过1)、查找二叉树的深度、计算节点数量,或者检查树是否对称。这些功能可以通过递归或迭代的方式实现。 在实际应用中,字符类型...

    C++ 实现判断是否为平衡二叉树(最小二叉树)算法及应用实例

    内容概要:本文档介绍了一个用C++编写的判断是否为平衡二叉树(也称为最小二叉树)的完整代码示例。主要内容涵盖二叉树相关操作,包括定义节点结构、计算树的高度、检查树是否平衡以及插入新元素等功能模块,并给出...

    二叉树的基本操作介绍.docx

    - **判断二叉树是否平衡**:检查二叉树是否满足平衡条件,即任意两个叶节点的最大深度差不超过1。 综上所述,二叉树的基本操作是理解和使用二叉树的基础,掌握这些基本操作可以帮助我们在实际编程中更有效地利用...

    统计二叉树叶子节点个数:递归方法与多语言实现

    统计叶子节点的数量是一个基础而重要的操作,它能够为其他操作提供关键信息,比如判断二叉树是否平衡、计算树的高度等。 递归是解决二叉树相关问题的一种常见方法,其核心思想是将问题分解为更小的子问题,直到达到...

    2015广工数据结构实验--平衡二叉树(包含源码和实验报告

    1. **树节点定义**:首先,需要定义一个树节点结构,包括节点值、左子节点和右子节点指针,以及可能的平衡因子(用于判断树的平衡状态)。 2. **插入操作**:在平衡二叉树中插入节点时,需要考虑插入后可能导致的树...

    Java面试黄金宝典:链表、树、图与大数据处理的关键算法解析

    内容概要:本文档详细介绍了 Java 中多种关键算法及其应用场景,涵盖单链表中间节点查找、从海量数据中找不重复数、判断二叉树是否平衡、大文件商品编号验证、敏感词检测、图算法、平衡树旋转以及动态规划思想等内容...

Global site tag (gtag.js) - Google Analytics