查看: 115|回复: 0
收起左侧

二叉树平衡因子#C++(数据结构)

[复制链接]
发表于 2020-4-24 08:49:41 | 显示全部楼层 |阅读模式 简体中文繁體中文

一、二叉树的基本概念


                               
登录/注册后可看大图

二叉树:二叉树是每个节点最多有两个子树的树结构。

根节点:一棵树最上面的节点称为根节点。

父节点子节点:如果一个节点下面连接多个节点,那么该节点称为父节点,它下面的节点称为子 节点。

叶子节点:没有任何子节点的节点称为叶子节点。

兄弟节点:具有相同父节点的节点互称为兄弟节点。

节点度:节点拥有的子树数。上图中,13的度为2,46的度为1,28的度为0。

树的深度:从根节点开始(其深度为0)自顶向下逐层累加的。上图中,13的深度是1,30的深度是2,28的深度是3。

树的高度:从叶子节点开始(其高度为0)自底向上逐层累加的。54的高度是2,根节点23的高度是3。

对于树中相同深度的每个节点来说,它们的高度不一定相同,这取决于每个节点下面的叶子节点的深度。上图中,13和54的深度都是1,但是13的高度是1,54的高度是2。


                               
登录/注册后可看大图

a)平衡二叉树

此节点往下 左子树深度 - 右子树深度=平衡因子

1:5的结点平衡因子就是 3 - 2 = 1;以5为跟节点,5的深度是0,2 1 4 3都是以5为跟节点的左子树 6 7 都是以5为跟节点的右子树


                               
登录/注册后可看大图

深度对应:5深度为:0 2深度为:1 1和4深度为:2 3深度为:3 6深度为:1 7深度为:2

左子树深度3 右子树深度2

2:2的结点平衡因子就是 1 - 2 = -1;

屏蔽2以上的节点 此时以2为跟节点:左子树


                               
登录/注册后可看大图

2深度为:0 1深度为:1  4深度为:1 3深度为:2

左子树深度1 右子树深度2

3:4的结点平衡因子就是 1 - 0 = 1;

4为跟节点 屏蔽其他


                               
登录/注册后可看大图

4深度为:0 3深度为:1 左子树深度1 右子树深度0

4:6的结点平衡因子就是 0 - 1 = -1;

叶子结点都是为 0;

(b)不平衡二叉树

此节点往下 左子树深度- 右子树深度=平衡因子

3 的结点平衡因子就是 2 - 4 = -2;

1 的结点平衡因子就是 0 - 1 = -1;

4 的结点平衡因子就是 0 - 3 = -3;

5 的结点平衡因子就是 0 - 2 = -2;

6 的结点平衡因子就是 0 - 1 = -1;

叶子结点都是为 0;



11)M8$ZMJM}JUH{BURD@@7A.png
您需要登录后才可以回帖 登录 | 注册会员

本版积分规则