java数据结构和算法------第八章

二叉树

为什么要用到树呢？因为树结合了有序数组和链表。在树中查找数据项的速度和在有序数组中一样快。并且插入数据项和删除数据项的速度和链表中一样快。

一棵树只有一个根，从根到其他任何节点的路径有且仅有一条。

二叉树是树中特殊的一种，但是它每个节点最多只有两个子节点。

二叉搜索树

一个节点的左子节点的关键字值小于该节点，而右子节点的值大于该节点。

树的效率

时间复杂度是O（lgN ）更精确地说是O（lg2N）

树的遍历

前序   中序     后序

中序遍历