客观世界中许多事物存在层次关系
人类社会家谱 社会组织结构 图书信息管理分层次组织在管理上具有更高的效率!
数据管理的基本操作之一:查找
如何实现有效率的查找?
查找:根据某个给定关键字K,从集合R中找出关键字与K相同的记录
静态查找:集合中记录是固定的(查字典)
没有插入和删除操作,只有查找动态查找:集合中记录是动态变化的
除查找,还可能发生插入和删除方法1:顺序查找
顺序查找的一种实现(无“哨兵”)
方法2:二分查找
【例】假设有13个数据元素,按关键字由小到大顺序存放。二分查找关键字为444的数据元素过程如下:
【例】仍然以上面13个数据元素构成的有序线性表为例。二分查找关键字为43的数据元素如下:
int BinarySearch(List Tbl,ElementType K) { //在表Tbl中查找关键字为K的数据元素 int left,right,mid,NoFound=-1; left=1; right=Tbl->Length; while(left<=right) { mid=(left+right)/2; if(KElement[mid]) right=mid-1; //调整右边界 else if(K->Tbl->Element[mid]) left=mid+1; //调整左边界 else return mid; //查找成功,返回数据元素的下标 } return NotFound; }
树:n(n>=0)个结点构成的有限集合。
当n=0时,称为空树。
对于任一颗非空树(n>0),它具备以下性质:
二叉树T:一个有穷的结点集合,这个集合可以为空,若不为空,则它是由根结点和称为其左子树和右子树的两个不相交的二叉树组成。
遍历过程
访问根结点 先序遍历其左子树 先序遍历其右子树遍历过程
中序遍历其左子树 访问根结点 中序遍历其右子树遍历过程
后序遍历其左子树 后序遍历其右子树 访问根结点中序遍历非递归遍历算法
二叉树遍历的核心问题:二维结构的线性化
从结点访问其左,右儿子结点 访问左儿子后,右儿子结点怎么办?需要一个存储结构保存暂时不访问的结点
存储结构:堆栈、队列
遍历从根结点开始,首先将根节点入队,然后开始执行循环:结点出队、访问该结点、其左右儿子入队
在二叉树的遍历算法中增加检测结点的“左右子树是否都为空”
答案是:必须要有中序遍历才行
先序和中序遍历序列来确定一颗二叉树