陈越《数据结构》第四讲 树(中)

前端之家收集整理的这篇文章主要介绍了陈越《数据结构》第四讲 树(中)前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

4.1 二叉搜索

4.1.1 定义与抽象数据类型的基本操作

1.

一棵二叉树,可以为;如果不为空,满足以下性质:
1. 非空 左子树 的所有 键值小于其根结点 的键值。
2. 非空 右子树 的所有 键值大于其根结点 的键值。
3. 左、右子树都是二叉搜索树 。

2.

查找:
1.1. Position Find( ElementType X,BinTree BST ) :从二叉搜索树BST中查找元素X ,返回其所在结点的地址;
1.2. Position FindMin( BinTree BST ) :从二叉搜索树BST 中查找并返回最小元素所在结点的地址;
1.3. Position FindMax( BinTree BST ) :从二叉搜索树BST 中查找并返回最大元素所在结点的地址。

注:
1.
2. 查找效率与树的高度有关!


插入与删除
1. BinTree Insert( ElementType X,BinTree BST )
2. BinTree Delete( ElementType X,BinTree BST )

1. 插入和删除有三种情况:
- 没有左儿子和右儿子;
- 只有左儿子或者右儿子;
- 既有左儿子又有右儿子(选取右子树中最小的那个)。

4.2 平衡二叉树


4.2.1 定义和特点

1. @H_399_403@@H_347_404@

平衡因子定义
(Balance Factor,简称BF): @H_784_502@BF(T)=hLhR 其中 hL hR 分别为 T 左、右子树的高度


平衡二叉树的定义
(Balanced Binary Tree)(AVL):
空树,或者任一结点左、右子树高度差的绝对值不超过1 ,即 @H_301_743@|BF(T)|1

2.


4.2.2 平衡二叉树的调整


整体思路:
RRLR@H_403_1064@LLRL

  1. RR

  2. LL

  3. LR

  4. RL


4.3

猜你在找的数据结构相关文章