1.什么是树
树(Tree): n(n≥0)个结点构成的有限集合。 当n=0时，称为空树;
二分查找算法
int BinarySearch(StaticTable *Tbl , ElementType K) {
int left ,right ,mid notFound = -1;
left = 1;
right = Tble->length;
while (left <= right) {
mid = (left +right)/2;
if (K< Tbl->Element[mid]) right = mid -1;
else if (K > Tble->Element[mid]) left = mid +1;
else return mid;
}
return NotFound;
}
二分查找的时间复杂度是O(logN)
2.对于任一棵非空树(n> 0)，它具备以下性质:
- 树中有一个称为“根(Root)”的特殊结点，用 r 表示;
- 其余结点可分为m(m>0)个互不相交的有限集T1，T2，... ，Tm，其 中每个集合本身又是一棵树，称为原来树的“子树(SubTree)
- 树的特点
- 子树是不相交的;
- 除了根结点外，每个结点有且仅有一个父结点;
- 一棵N个结点的树有N-1条边。
- 树的术语
- 结点的度(Degree): 结点的子树个数
- 树的度: 树的所有结点中最大的度数
- 叶结点(Leaf):度为0的结点
- 父结点(Parent):有子树的结点是其子树的根结点的父结点
- 子结点(Child):若A结点是B结点的父结点，则称B结点是A结点的子结点;子结点也称孩子结点。
- 兄弟结点(Sibling):具有同一父结点的各结点彼此是兄弟结点
- 路径和路径长度:从结点n1到nk的路径为一 个结点序列n1 , n2 ,... , nk , ni是 ni+1的父结 点。路径所包含边的个数为路径的长度。
- 祖先结点(Ancestor):沿树根到某一结点路 径上的所有结点都是这个结点的祖先结点。
- 子孙结点(Descendant):某一结点的子树 中的所有结点是这个结点的子孙。
- 结点的层次(Level):规定根结点在1层， 其它任一结点的层数是其父结点的层数加1。 12. 树的深度(Depth):树中所有结点中的最 大层次是这棵树的深度。
5.树的表示
一般树可以使用儿子兄弟表示法。
旋转45度，可以给这种树命名为二叉树。
