|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
若在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素，则称此类查找表为动态查找表。动态查找表的特点是表结构是动态生成的。
|
|
|
|
|
|
二叉排序树又称二叉查找树，它或者是一棵空树，或者是具有以下性质的二叉树。
|
|
|
|
.若它的左子树非空，则左子树上所有节点的值均小于根节点的值。
|
|
|
|
.若它的右子树非空，则右子树上所有节点的值均大于或等于根节点的值。
|
|
|
|
|
|
|
|
若二叉树为非空，将给定值与根节点的关键字值进行比较，若相等，则查找成功；若不等，则当根节点的关键字值大于给定值时，到根的左子树中进行查找；否则到根的右子树进行查找。
|
|
|
|
|
|
二叉排序树是通过依次输入数据元素并把它们插到二叉树的适当位置上构造起来的，具体过程如下：读入一个元素，建立一个新节点。若二叉排序树非空，则将新节点的值与根节点的值进行比较，如果小于根节点的值，则插入左子树中，否则插入右子树中；若二叉树为空，则新节点作为二叉排序树的根节点。
|
|
|
|
|
|
在二叉排序树中删除一个节点，不能把以该节点为根的子树都删除，只能删除这个节点并仍旧保持二叉排序树的特性。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
树是非线性的结构，存储树时，须把树中节点之间存在的关系反映在树的存储结构中。树有很多存储结构，这里仅介绍最常用的两种。
|
|
|
|
|
|
树的标准存储结构由节点的数据和指向子节点的指针数组组成；对于度为M的树，其指针数组中的元素个数为M。
|
|
|
|
|
|
由于树的带逆存储结构需要一个从子节点指向父节点的指针，因而该结构在标准存储结构的基础上，需要在树的节点中增加一个指向其双亲节点位置的指针。
|
|
|
|
|
|
树的遍历是树的基本操作之一，也是最重要的操作之一。树的遍历含义是指：按照某种要求依次访问树中的每个节点，每个节点均被访问一次且仅被访问一次。常用的树的遍历方法可分为前序遍历、后序遍历和中序遍历。
|
|
|
|
|
|
首先访问根节点，然后从左到右前序遍历根节点的各棵子树。树的前序遍历递归算法如下：
|
|
|
|
|
|
若利用栈来记录当前未访问完的子树的根节点指针，则前序遍历的非递归算法如下：
|
|
|
|
|
|
|
|
树的后序遍历的基本思想是：先依次遍历每棵子树，然后访问根节点，与后序遍历二叉树相同。树的后序遍历递归算法如下：
|
|
|
|
|
|
|
|
树的中序遍历的基本思想是：先左子树，遍历根节点，然后依次遍历其他各棵子树，类似二叉树的中序遍历。树的中序遍历递归算法如下：
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
