平衡二叉树判定方法（c++）实现

痛定思痛。 2022-02-28 08:18 205阅读 0赞

# [平衡二叉树判定方法（c++）实现][c] #

\-- 欢迎指正--

平衡二叉树特点：

任意一个结点的平衡因子（左子树高度 - 右子树高度）的绝对值不会超过1。

下面的方法，若是平衡二叉树，则还会返回树的高度

结点结构：

struct node 
    {
        int data;
        int height;
        node *lc;
        node *rc;
        node()
            : data(0)
            , height(0)
            , lc(0)
            , rc(0)
        {
    
        }
    };

函数源码：

// 判断是否为平衡二叉树,若是，则返回树的高度
        // false - 不是平衡二叉树，true-是平衡二叉树
        bool is_avl_tree(node *pnode, int &deepth)
        {
            if ( NULL == pnode)
            {
                deepth = 0;
                return true;
            }
    
            int left_h = 0;
            int right_h = 0;
    
            if (is_avl_tree(pnode->lc, left_h) && is_avl_tree(pnode->rc, right_h))
            {
                int diff = abs(left_h - right_h);
                if (1 < diff)
                    return false;
                deepth = 1 + ( (left_h > right_h) ? left_h : right_h);
    
                return true;
            }
    
            return false;
        }

posted @ 2019-03-22 23:05 [mohist][] 阅读( ...) 评论( ...) [编辑][Link 1] 收藏

[c]: https://www.cnblogs.com/pandamohist/p/10581982.html
[mohist]: https://www.cnblogs.com/pandamohist/
[Link 1]: https://i.cnblogs.com/EditPosts.aspx?postid=10581982

发表评论取消回复

表情：

评论列表（有 0 条评论，205人围观）

还没有评论，来说两句吧...

相关阅读

相关树（二）平衡二叉树

[树（一）二叉查找树][Link 1] [树（三）红黑树与平衡二叉树的区别][Link 2] 1 为什么有平衡二叉树二叉查找树（二叉搜索树）

迷南。/ 2023年06月22日 04:22/ 0 赞/ 20 阅读

相关树：平衡二叉树

1，二叉排序树问题对于一个有序数组`{1, 2, 3, 4, 5}`，其生成的二叉排序树如下；由图可见，最终形成一个类似单链表形式的二叉树，对插入速度没有影响，但

╰+哭是因爲堅強的太久メ/ 2023年02月28日 01:25/ 0 赞/ 21 阅读

相关平衡二叉树

写在前面 > 剑指offer：平衡二叉树题目要求 > 输入一棵二叉树，判断该二叉树是否是平衡二叉树。平衡二叉树要求任意一个节点的左右字数之间的高度差不超过1。

浅浅的花香味﹌/ 2022年05月17日 01:54/ 0 赞/ 322 阅读

相关平衡二叉树

时间限制：1秒空间限制：32768K 热度指数：160212 [ 算法知识视频讲解][Link 1] 题目描述输入一棵二叉树，判断该二叉树是否是平衡二叉树。

向右看齐/ 2022年03月08日 01:44/ 0 赞/ 348 阅读

相关平衡二叉树判定方法（c++）实现

[平衡二叉树判定方法（c++）实现][c] \-- 欢迎指正-- 平衡二叉树特点：　　任意一个结点的平衡因子（左子树高度 - 右子树高度）的绝对值不会超过1。　

痛定思痛。/ 2022年02月28日 08:18/ 0 赞/ 206 阅读

相关二叉搜索树判定方法（c++实现）

[二叉搜索树判定方法（c++实现）][c] \--- 欢迎指正--- 自己想到的方法是：使用中序遍历数组或者链表，然后比较数组或者链表中的数据是否有序。 CC150

一时失言乱红尘/ 2022年02月28日 08:16/ 0 赞/ 229 阅读

相关平衡二叉树（c++实现）续

[平衡二叉树（c++实现）续][c] \--- 欢迎指正--- 题外话：上一篇关于平衡二叉树文章中，我都没说自己是怎么理解的。别人终归就是别人的。但别人真的是写的棒棒的

Myth丶恋晨/ 2022年02月28日 08:14/ 0 赞/ 179 阅读

相关平衡二叉树（c++）实现

[平衡二叉树（c++）实现][c] \------ 欢迎指正------- 1、参考资料：　　书籍：《算法导论》　　博文：[http://www.cnblogs

淩亂°似流年/ 2022年02月28日 08:14/ 0 赞/ 246 阅读

相关平衡二叉树

平衡二叉树介绍是由前苏联的两位数学家G.M.Adelse-Velskil和E.M.Landis提出，因此一般也称作AVL树，AVL树本质还是一棵二叉查找树，只是在其基础

青旅半醒/ 2022年02月24日 07:54/ 0 赞/ 383 阅读

相关平衡二叉树 (平衡查找树)

平衡二叉树(AVL 树) 看一个案例(说明二叉排序树可能的问题) ![1460404-20190609204205330-1398837969.png][] 上

小咪咪/ 2021年10月29日 07:24/ 0 赞/ 498 阅读