2019/08/16 树和二叉树

基本术语：

度：树中任意一个子结点的个数称为该结点的度，树中结点的最大度数称为该树的度。其中，度大于0的结点称为分支结点（非终端结点），度为0的结点称为叶子结点（终端结点）。

结点的层次从根结点开始定义，根结点为1层（有些课本规定根结点是0层），它的子结点为2层，以此类推。

结点的深度：结点的深度是指从根结点自顶向下逐层叠加。
结点的高度：结点的高度是指从叶结点自底向上逐层叠加。
树的高度（深度）：是指树中结点最大的层数。
有序树和无序树：若树的结点的左右子树是有次序的，则称为有序树，交换左右子树则变为不同的一棵树，否则为无序树。
路径和路径长度：树中两个结点的路径是由这两个结点之间经过的结点序列构成的，而路径长度是路径上经过的边的个数。树的分支是有向的，从双亲结点指向孩子结点，所以树中的路径是从上而下的，既同一个双亲的两个孩子之间不存在路径。

树的性质

1. 树中的结点数等于所有结点的度数加1（所有的边数）。
2. 度为 m 的树中第 i 层上至多有 个结点（i>=1）。
3. 具有 n 个结点的 m 叉树的最小高度为 向上取整。

二叉树的概念及其性质

二叉树是指每个结点上至多只有两颗子树，并且二叉树的子树具有左右的区别，次序不能随意颠倒。
性质

1. 非空二叉树上的叶子结点数等于度为2的结点数加1。
2. 非空二叉树第k层最多只有 个结点（k>=1）。
3. 高度为h的二叉树最多只有 个结点。

二叉树的遍历

根据对于根结点的访问次序，可以将二叉树的遍历分为先序（NLR）、中序（LNR）和后序（LRN）遍历。

线索二叉树

目的：为了加快查找前驱和后继的速度。
将二叉树线索化的时候，如果没有左子树，令lchild指向其前驱结点，若没有右子树，令rchild指向其后继结点。另外增加两个结点标志域作为当前指针域指的对象是左（右）子结点还是直接前驱（后继）。

二叉排序树

二叉排序树（BST），也称为二叉查找树。

1. 若左子树非空，则左子树的所有结点都小于根结点的关键字的值。
2. 若右子树非空，则右子树的所有结点都大于根结点的关键字的值。

二叉排序树的查找效率的分析
若二叉排序树为平衡二叉树，则其查找长度可以达到 。