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

痛定思痛。 2022-02-28 08:18 186阅读 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 条评论，186人围观）

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

相关阅读

相关平衡二叉树

平衡二叉树（Balanced Binary Tree）是二叉查找树的一个进化体，也是第一个引入平衡概念的二叉树。1962年，G.M. Adelson-Velsky 和 E.M.

墨蓝/ 2022年05月28日 08:57/ 0 赞/ 428 阅读

相关平衡二叉树

平衡二叉树又称AVL树。它或者是颗空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。若将二叉树节点的平衡因子BF定

骑猪看日落/ 2022年05月17日 01:24/ 0 赞/ 272 阅读

相关平衡二叉树

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

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

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

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

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

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

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

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

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

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

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

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

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

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

相关平衡二叉树

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

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

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

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

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

相关二叉平衡树

二叉平衡树说起这个树，我找了整整两天的时间，刚开始考虑的不周全，然后就一直该一直该，一直加一直加。定义：它是一颗空疏或它的左右两个子树的高度差的绝对值不超过

Dear 丶/ 2021年09月22日 09:42/ 0 赞/ 477 阅读