树是一种经常用到的数据结构,用来模拟具有树状结构性质的数据集合。
树里的每一个节点有一个根值和一个包含所有字节点的列表。从图的观点来看,树也可以视为一个拥有N个节点和N-1条边的一个有向无环图
。
二叉树
是一种更为典型的树状结构,每一个节点最多有两个子数的树结构,通常子树被称作左子树
和右子树
。
对于树,应该掌握:
- 树和二叉树的概念
- 熟悉不同的遍历方法
- 运用
递归
解决二叉树相关问题
二叉搜索树(BST)
是二叉树的一种特殊形式,具有以下性质:每一个节点中的值必须不小于其左侧子树中的任何值,但不大于其右侧子树中的值。
- 对于二叉搜索树,最重要的用途是用作搜索算法,每个节点的搜索时间为O(1), 最换为O(h), h为树的高度。
- 常见的二叉搜索树有:AVL树,伸展树,红黑树,多路搜索树...