数据结构

四、二叉排序树

对二叉排序树进行中序遍历 结果必然是一个递增序列

所以通过建立二叉排序树可以对无序序列进行排序

---

一、例3.5 建立二叉排序树 并前序中序后序遍历

有了之前07中二叉树的建立、还原、遍历基础，本例只有建树部分有差别

但这个却想了挺久的。。。可能也是受之前的影响 也想一次性建树 没有想到转换为重复调用insert函数

本例完成过程先是自己试着写，第一次写了一个递归的只与前一个插入元素比较的二叉树；发现错误后尝试引入mother结点来和之前所有插入的元素做判断，但是无法判断。。如判断次数、mother节点个数之类的；第三次看了一下参考实例的函数声明，看到建树函数名为insert 参数有Node*T后就懂了。。太傻了。

思路摆正后调代码还是出现了下述简单但致命的问题：

1) 定义时初始化为空 Node*T=NULL

2) 调用insert函数和递归时都要注意重新赋值啊朋友！写个insert函数放那了树怎么会变呢？？嗯？？还有注意是赋值给 T 还是赋值给 T->lchild 之类 

还有在做插入处理时可以读入一个元素就插入一次 不用专门写数组

---

二、例3.6 二叉搜索树 判断两序列是否为同意二叉搜索树序列

自己的构思：

首先，二叉搜索树即二叉排序树。

与上题相比，该题在输入时序列长度是未知的，所以对于输入以字符串格式识别，可以利用str[i]!=0.

此外，该题与上题的主要区别在于遍历结果需要保存再做比较，不能简单输出看结果。

所以，建树的插入函数是没有变的（虽然写的时候还是出错了 基德）；主要处理是在遍历函数上，需要得到一个数组，最开始想的是直接返回一个数组，但是各种出错。。应该是指针的问题，比如char []和char *的差别之类，迷。。。

然后就卡壳了 哭

参考示例：

解决方案是设置全局变量，遍历函数也不用返回数组，遍历函数中修改的结果在main函数里也可以用。不过全局变量的处理对我来说还是挺想不到的： (但是理解了又觉得逻辑很顺畅）

这样遍历函数里的printf就变成了str[(*size)++]=T->c; 此外，str1[size1]=0是在末尾字符添加空字符，方便使用字符串函数。

注意的问题：

特别注意初始化 Node *T2=NULL时要放在循环里面，不然每次测试新的序列都会继续在之前的T2基础上继续插入元素，导致结果错误。

---

三、对二叉排序树的删除

删除结点的类型分为三种情况：

1. 删除结点无叶子结点：根root指针置空 or 父结点连接该结点的指针置空

2. 删除结点只有左子树/右子树：父结点连接该结点的指针指向该结点的左/右子树根节点，再将该结点的左/右孩子指针置空

3. 删除的结点既有左子树又有右子树：将该结点的右子树中的左下结点（即中序遍历第一个遍历到的结点)赋值给该结点，再删除那个左下结点（连接指针置空）  ------（保证二叉排序树的结构）