查找方法：
静态查找：
1、顺序查找 ： O(N)
2、二分查找(Binary Search)：O(logN)
前提：有序连续存放在数组中
二分查找判定树(以11个元素为例)：
1、判定树上每个节点需要的查找次数，刚好是该节点所在的层数
2、查找成功的情况，查找次数不会超过判定树的深度
3、n个节点的判定树的深度为(log以2为底的n)+1
4、平均成功查找次数：(44+43+22+11)/11 = 3
树(Tree)：
根(Root)、子树(SubTree)
1、子树不想交
2、除了根结点，每个结点有且只有一个父节点
3、一棵N个结点的树，有N+1条边
树的基本术语：
1、结点的度(Degree)：结点的子树个数
2、树的度：树的所有结点中最大的度数
3、叶结点(Leaf)：度为0的节点
4、父结点(Parent)：有子树的结点，是其子树的根节点的父结点
5、子结点(child)：若A是B的父结点，则B是A的子结点
6、兄弟结点(Sibling)：具有同一个父结点的各结点彼此为兄弟结点
7、路径和路径长度
8、祖先结点(Ancestor)：沿树根到某一结点，路径上的所有结点都是这个结点的祖先结点
9、子孙结点(Descendant)：某一结点的子树中的所有结点，是这个结点的子孙结点
10、结点的层次(level)：规定根节点为1层，其他任一结点的层数是其父结点层数+1
11、树的深度(depth)：树中所有结点的最大层次，是这棵树的深度
用链表表示树：儿子-兄弟表示法 翻转即二叉树
例：二元运算表达式树
先序遍历：前缀表达式
中序遍历：中缀表达式（受运算符优先级的影响）
后序遍历：后缀表达式
例：两种遍历序列确定二叉树（其中一种必须为中序）
网友评论