二叉排序树的删除图解_二叉排序树的删除_二叉排序树的删除代码(3)

全部代码 .................................................................................................................................. 20 二叉链表结构C.................................................................................................................... 20 二叉链表结构C++ ............................................................................................................... 24 顺序存储结构C.................................................................................................................... 27

1 需求分析

1.1 问题的提出 研究关于如何创建二叉排序树并对树进行遍历，查找和删除等操作，同时关注用顺序和二叉链表作存储结构带来的区别。

1.2任务与分析

用顺序和二叉链表作存储结构实现二叉排序树：

（1）以回车('\n')为输入结束标志,输入数列L，生成一棵二叉排序树T；

（2）对二叉排序树T作中序遍历，输出结果；

（3）输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作

2)；否则输出信息“无x”。二叉排序树的删除

2 总体设计

2.1二叉排序树的建立

建二叉树的结点至少应当包含三个域，分别存放结点的数据data，左子女结点指针leftChild和右子女结点指针rightChild。整个二叉树的链表要有一个表头指针，它指向二叉树的根结点，其作用是当作树的访问点

从空的二叉排序树开始，经过一系列的查找插入操作以后，生成了一棵二叉排序树。

根据二叉排序树的定义，建立一棵二叉排序树的过程是按照待排序序列元素的先后次序，不断动态生成二叉树的结点，逐个插入到二叉树中。若p为根结点指针，b为当前待插入元素，其过程可以描述为：

若为空树（p=nil），动态生成一个结点，其数据域为当前待插入元素b，左、右指针域为“空”，p指向该结点。

若非空树，比较b与根结点数据data（p）

如果b<data(p), 将b插入左子树中；

如果b≥data(p)，将b插入右子树中；

左、右子树的插入方式与二叉排序树的插入方式相同。

不断调用上述的插入过程，直到所有待排序序列均排入后，就形成一棵二叉排序树。

由此可见，建立二叉排序树就是多次调用二叉排序树的插入算法。

-1-

2.2中序遍历二叉树算法的框架是：

若二叉树为空，则空操作；否则

中序遍历左子树（L）；

访问根结点（V）；

中序遍历右子树（R）。

中序遍历二叉树也采用递归函数的方式，先访问左子树,然后访问根结点,最后访问右子树.直至所有的结点都被访问完毕。 2.3二叉排序树中元素的查找

在二叉排序树上进行查找，是一个从根结点开始，沿某一个分支逐层向下进行比较判等的过程。它可以是一个递归的过程。假设我们想要在二叉排序树中查找关键码为x的元素，查找过程从根结点开始。如果根指针为NULL，则查找不成功；否则用给定值x与根结点的关键码进行比较；如果给定值等于根结点的关键码，则查找成功，返回查找成功的信息，并报告查找到的结点地址。如果给定值小于根结点的关键码，则继续递归查找根结点的左子树；否则，递归搜索根结点的右子树。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-26533-3.html