关于二叉搜索树及三种树遍历的特点

关于二叉搜索树及三种树遍历的特点

二叉搜索树：或者是一棵空树，或者具有如下性质：对树中任一节点X，它的左子树中的所有关键字节点的值都不大于（小于或等于）X的关键字值，而它的右子树中的所有关键字节点的值都大于X的关键字值。

中序遍历二叉搜索树可得到一个关键字的有序序列，由小到大排序。

在二叉搜索树中的插入、删除、搜索的复杂度等于树高，即(log(n))。

在二叉搜索树中找最小节点和最大节点也很方面，如要找最小节点，只需从根节点开始，一直找左子树，当某个节点没有左子树时，该节点就是最小节点，即终止节点就是最小节点。同理，如果要找最大节点，那么从根节点开始一直找右子树即可，当某个节点没有右子树时，该节点就是最大节点。

二叉树后序遍历的特点：最后一个节点肯定是根节点。

二叉树先序遍历的特定：第一个节点肯定是根节点。

根据这些知识我们可以解决下列问题：如果一棵二叉搜索树中存储了字符’A’, ‘B’,’C’,’D’, ‘E’, ‘F’, ‘G’, ‘H’,判断下列哪个结果是后序树遍历的结果（选C）：

A: ADBCEGFH, B: BCAGEHFD, C: BCAEFDHG, D: BDACEFHG

二叉树的常见问题及其解决程序

【递归】二叉树的先序建立及遍历

在JAVA中实现的二叉树结构

【非递归】二叉树的建立及遍历

二叉树递归实现与二重指针