六、树和二叉树(概念与性质)
树的基本概念：
- 结点：树中的一个独立单元。
- 结点的度：结点拥有的子树数量。
- 树的度：树中各结点度的最大值。
- 叶子：度为0的结点称为叶子结点或终端结点。
- 非终端结点：度不为0的结点称为非终端节点或分支结点。除根结点外，非终端结点也称为内部节点。
- 双亲和孩子：结点的字树的根称为该结点的孩子，相应的该结点称为孩子的双亲。 兄弟：同一个双亲的孩子之间互称兄弟。
- 祖先：从根到该节点所经分支上的所有结点。 子孙：以某结点为根的字树中的任一结点都称为该结点的子孙。
- 层次：结点的层次从根开始定义起，根为第一层，根的孩子为第二层。树中任一结点的层次等于其双亲结点的层次加1。
- 堂兄弟：双亲在同一层的结点互为堂兄弟。 树的深度：树中结点的最大层次称为树的深度或高度。
- 有序树和无序树：如果将树中结点的各子树看成从左至右是有次序的。，则称该树为有序树，否则称为无序树。
- 森林： m(m>=0)棵互不相交的树的集合。
二叉树的定义：
二叉树是n（n>=0）个结点所构成的集合，或为空树，或为非空树，对于非空树T：
(1)有且仅有一个称之为根的结点；
(2)除根结点以外的其余结点分为两个互不相交的子集T1和T2，分别称为T的左子树和右子树，且T1和T2本身又都是二叉树。
二叉树与树的区别：
①二叉树每个结点至多只有两颗子树（二叉树中不存在度大于2的结点）
②二叉树的子树有左右之分，其次序不能颠倒。
二叉树的五种形态
二叉树的性质：
性质1 在二叉树的第 i 层上至多有 2^(i-1)个 结点(i>=1)。
性质2 深度为k的二叉树至多有2^k-1个结点(k≥1)。
性质3 在任意-棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则no=n2+1。
满二叉树：深度为k且含有(2^k)-1个结点的二叉树
完全二叉树：深度为k，有n个结点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树。
性质4：具有n个结点的完全二叉树的深度为└log2^n┘+1。
性质5：如果对一颗有n个结点的完全二叉树（其深度为└log2n┘+1）的结点按层序编号（从第一层到第└log2n┘+1层，每层从左至右），则对任一结点i（1<=i<=n）有：
(1)如果i=1，则结点i是二叉树的根，无双亲；如果i>1,则其双亲PARENT(i)是结点└i/2┘。
(2)如果2i>n，则结点i无左孩子(结点i为叶子结点)；否则其左孩子LCHILD(i)是结点2i。
(3)如果2i+1>n，则结点i无右孩子；否则其有孩子RCHILD(i)是结点2i+1。
快手公司福利 699人发布
查看14道真题和解析