【陈越 数据结构】第三讲 树(上)

树：层次结构

1.为什么要采用树结构？

插入、删除、查找的效率能提高。

1.1 查找：

（1）顺序查找

哨兵的作用：

可以少写一个判断的语句，不用每次都判断下标了。

令哨兵=查找值K，最后返回下标，如果下标为0，则没找到。

顺序查找时间复杂度：N(O)

（2）二分查找

前提和定义：有序数组

算法：

每次都除2除2除2，因此
时间复杂度：O(logN)

对于1…11个元素来说，其二分查找顺序永远如上图所示，称作：判定树。
ASL：平均成功查找次数。

1.2 动态查找问题：查找树

树是保证节点联通的最小的一种方式。

如何表示一颗树？

用数组是不可行的，用链表可以：

每个节点的链表结构是一样的，两个指针，这样的话在程序实现的时候比较方便。

把这个树旋转45度，则可以得到二叉树。
树结构中：二叉树是最最重要的内容。

1.3 二叉树

二叉树：可以约等于度为2的数，每个节点都只能有2个子树，但是又不完全能这么说，因为二叉树有左右树之分。


斜二叉树就是一个链表。
下图右边就不是一个完全二叉树（很重要，后面经常用）：

证明：
从边的角度考虑，一个2叉树的边为节点数-1，n0为没有子节点的节点个数，n0贡献0条边，n1贡献1条边，n2贡献2条边，那么如下等式成立。

数组的存储方式：

链表的存储方式：

二叉树的遍历：