二叉树的应用：二叉排序树BST和平衡二叉树AVL的构造 课设作业 完整代码

# 一、实验名称： 二叉树的应用：二叉排序树BST和平衡二叉树AVL的构造 # 二、实验学时：4 # 三、实验内容和目的： 树型结构是一类重要的非线性数据结构。其中以树和二叉树最为常用，直观看来，树是以分支关系定义的层次结构。树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树来形象表示。树在计算机领域中也得到广泛应用，如在编译程序中，可用树来表示源程序的语法结构。又如在数据库系统中，树型结构也是信息的重要组织形式之一。 实验内容包含有二： 二叉排序树(Binary Sort Tree)又称二叉查找(搜索)树(Binary Search Tree)。其定义为：二叉排序树或者是空树，或者是满足如下性质的二叉树：1.若它的左子树非空，则左子树上所有结点的值均小于根结点的值；2.若它的右子树非空，则右子树上所有结点的值均大于根结点的值；3.左、右子树本身又各是一棵二叉排序树。 平衡二叉树（Balanced Binary Tree）又被称为AVL树。具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。构造与调整方法。 实验目的： - 二叉排序树的实现 - 用二叉链表作存储结构，生成一棵二叉排序树T。 - 对二叉排序树T作中序遍历，输出结果。 - 输入元素x,查找二叉排序树T,若存在含x的结点,则返回结点指针。 - 平衡二叉树的实现 - 用二叉链表作为存储结构，输入数列L，生成一棵平衡二叉树T。 - 对平衡二叉树T作中序遍历，输出结果。 # 四、实验原理 二叉排序树的实现 叉树节点插入 在二叉排序树中插入新结点，要保证插入后的二叉树仍符合二叉排序树的定义。插入过程：若二叉排序树为空，则待插入结点*s作为根结点插入到空树中；当非空时，将待插结点关键字s->data和树根关键字root->data进行比较，若s->data =root->data,则无须插入，若s->data<root->data,则插入到根的左子树中，若s->data> root->data,则插入到根的右子树中。而子树中的插入过程和在树中的插入过程相同，如此进行下去，直到把结点*s作为一个新的树叶插入到二叉排序树中，或者直到发现树已有相同关键字的结点为止。 - 生成了一棵二叉排序树 - 每次插入的新结点都是二叉排序树上新的叶子结点。 - 由不同顺序的关键字序列，会得到不同二叉排序树。 - 对于一个任意的关键字序列构造一棵二叉排序树，其实质上对关键字进行排序。 - 叉排序树结点的删除 在二叉排序树中删除节点，要保证删除后的二叉树仍然符合二叉排序树的定义，即二叉排序树中的每一个节点的左子树的值都要比该节点小，右子树的值都要比该节点大。要删除二叉排序树中的某一个节点首先需要查找该节点在二叉排序树中是否存在，将待删除节点的值p->data与二叉排序树的根节点的值root->data进行比较，若p->data=root->data,则证明查找到待删除节点，进行下一步删除操作；若p->data<root->data，则将待删除节点与根节点的左孩子的值进行比较；p->data<root->data，则将待删除节点与根节点的右孩子的值进行比较；直到查找到待删除节点为止，或者二叉排序树不存在该节点，终止删除操作。删除过程要分三种情况： 待删除节点为二叉排序树的叶子节点，删除该节点不会影响二叉排序树的特性，只需将其父节点相应的指针域改为空指针即可； 待删除节点为只含有一棵子树的节点，删除该节点只需令其父节点相应的指针域指向该节点对应的子树即可； 待删除节点为含有左右子树的节点，删除该节点需要使用其中序遍历的前驱代替之，代替之后将其前驱删除。换言之，即使用待删除节点右子树中的最小值代替该节点的值，并将最小值所处的节点删除。 - 平衡二叉树的实现 - 叉树节点插入 - 找到相应插入位置，同时记录离插入位置最近的可能失衡节点A(A的平衡因子不等于0)。 - 插入新节点S。 - 确定节点B(B是失衡节点A的其中一个孩子，就是在B这支插入节点导致的不平衡，但是B的平衡因子为-1 或 1) - 修改从B到S路径上所有节点的平衡因子。(这些节点原值必须为0，如果不是，A值将下移)。 - 根据A、B的平衡因子，判断是否失衡及失衡类型，并作旋转处理。 - 每插入一个结点就进行调整使之平衡。调整策略，根据二叉排序树失去平衡的不同原因共有四种调整方法。 - 第一种情况：LL型平衡旋转 - 由于在A的左子树的左子树上插入结点使A的平衡因子由1增到2而使树失去平衡。调整方法是将子树A进行一次顺时针旋转。 - 第二种情况：RR型平衡旋转 - 其实这和第一种LL型是镜像对称的，由于在A的右子树的右子树上插入结点使得A的平衡因子由1增为2；解决方法也类似，只要进行一次逆时针旋转。 - 第三种情况：LR型平衡旋转 这种情况稍复杂些。是在A的左子树的右子树C上插入了结点引起失衡。但具体是在插入在 C的左子树还是右子树却并不影响解决方法，只要进行两次旋转（先逆时针，后顺时针）即可恢复平衡。 - 第四种情况：RL平衡旋转 - 也是LR型的镜像对称，是A的右子树的左子树上插入的结点所致，也需进行两次旋转(先顺时针，后逆时针)恢复平衡。 - 生成了一棵平衡二叉树 - 每次插入的新结点都是平衡二叉树上新的叶子结点。 - 由于插入节点可能会破坏平衡二叉树的性质，因此在插入节点后需要进行调整以维护二叉树的平衡性。 - 由不同顺序的关键字序列，可能会得到不同二叉排序树。平衡二叉树既持了二叉排序树排序的性质，又降低了原来操作的复杂度。 - 平衡二叉树的删除 在二叉排序树中删除节点，要保证删除后的二叉树仍然符合平衡二叉树的定义。对于排序性的维护，可以延用上述二叉排序树的做法。对于平衡性的维护，可以借用平衡二叉树生成的逆向思维。 若删除节点导致以该节点位置为根的平衡二叉树的平衡因子大于等于2，可以看做往该平衡二叉树的左子树插入节点导致的不平衡，这里有两种情况： 若删除节点的值大于等于根的左孩子即的值data>=root->lchild->data，说明删除是在根的左孩子的及其右子树进行的，可以看成向根的左孩子的左子树增加节点导致的不平衡，进行LL旋转。 若删除节点的值小于根的左孩子即data<root->lchild->data，则说明删除是在根的左孩子的左子树进行的，可以看成向根的左孩子的右子树增加节点导致的不平衡，进行LR旋转。 若删除节点导致以该节点位置为根的平衡二叉树的平衡因子小于等于-2，可以看做往该平衡二叉树的右子树插入节点导致的不平衡，这里有两种情况： 若删除节点的值小于等于根的右孩子的值即data<=root->rchild->data，说明删除是在根的右孩子的及其左子树进行的，可以看成向根的右孩子的右子树增加节点导致的不平衡，进行RR旋转。 若删除节点的值大于根的右孩子即data>root ->rchild->data，则说明删除是在根的右孩子的右子树进行的，可以看成向根的右孩子的左子树增加节点导致的不平衡，进行RL旋转。 # 五、实验器材（设备、元器件） - 处理器：Intel Core i5-8300H CPU @ 2.30GHz 2.30GHz - 已安装的内存(RAM)：8GB - 系统�