软考软件设计师专题讲义九：数据结构相关算法

　　二叉树

　　二叉树永远都是数据结构中考查的重点，包括二叉树的基本概念、性质以及各种不同的遍历方法。而且，它的相关算法也是树和森林的算法的基础。因此对这部分知识要十分的重视。

　　另外，有时候还会涉及到二叉查找树的一些概念和算法。

　　查找树便于链式存储，还能实现快速查找。作为一种特殊的二叉树，它或者为空，或者满足以下3个条件：

　　I. 若该树根结点的左子树非空，其左子树所有结点的键值都小于该树根结点的键值

　　II. 若该树根结点的右子树非空，其右子树所有结点的键值都大于该树根结点的键值

　　III. 该树根的左子树和右子树均为查找树

　　根据以上定义可以知道，如果进行中序遍历，即可得到一个从小到大的结点序列。

　　排序

　　排序对于数据结构来说是一个特别重要的重点和难点，这也是体现一个高级程序员基本素质的地方。我们除了要掌握各种排序算法的基本思想，还必须要掌握其具体实现(用C语言或者Pascal语言均可)，这反过来对我们更深刻领会其算法的本质也很有裨益。另外，对于它们之间的各种差异比较，如稳定性、时间复杂度、空间复杂度也要有所了解。这可以见前面知识要点部分的相关内容。

　　HASH表的处理过程和解决冲突的方法!!!

　　　　　　　计算机软考软件设计师练习试题及答案解析汇总