`
yyang900427
  • 浏览: 11554 次
  • 性别: 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)、查找二叉树的深度、计算节点数量,或者检查树是否对称。这些功能可以通过递归或迭代的方式实现。 在实际应用中,字符类型...

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

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

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

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

    平衡二叉树的构造

    插入操作需要考虑如何更新平衡因子并判断是否需要进行旋转。删除操作则更为复杂,可能涉及节点替换、单旋、双旋等步骤。测试程序通常会包含一系列的插入和删除操作,以验证AVL树的正确性和性能。 总的来说,理解并...

    平衡二叉树C程序源码

    6. **平衡因子检查**:在插入或删除后检查节点的平衡因子,以确定是否需要进行旋转。 7. **旋转操作**:实现AVL树的左旋和右旋,或者红黑树的四种旋转操作(左旋、右旋、左旋-右旋、右旋-左旋)。 为了正确地实现...

    课设 - 平衡二叉树的演示 .docx

    平衡因子用于判断树是否平衡,如果插入新节点导致某个节点的平衡因子超过1或低于-1,需要进行相应的旋转操作来恢复平衡。 2. **插入**:在平衡二叉树中插入节点,首先要进行正常的二叉树插入操作,然后检查新插入...

Global site tag (gtag.js) - Google Analytics