树知识点总结/树的运算

树是有限数据元素的集合

根节点无前驱节点，其他节点单前驱，多后驱

度Degree：子树的个数

分支(Branch)节点：度不为零的节点

叶子节点：度为零的节点

左孩子，右孩子，双亲，兄弟

路径，路径长度

祖先，子孙：有一条路径从M到N，则M为祖先，N为子孙

层数，深度和高度：

森林：零棵或有限棵不相交的树的集合

二叉树性质

个节点 2. 深度为k的二叉树最多有 $2^{_{k}}-1$

个节点 3. 叶子节点数为 $n^{_{0 }}$

，度为2的节点数为 $n_{2}$

，则有： $n_{0}=n_{2} + 1$ 4. 设n为二叉树节点总数，有* $n_{} = n_{0} + n_{1} + n_{2}$ * 5. 具有n个节点的完全二叉树的深度为 $\log_2n + 1$ **

以二叉链表作为二叉树的存储结构，n个节点空链域的个数为n+1个

节点的权，带权路径长度

树转换为二叉树后有n个非终端节点，n+1个右指针域为空

森林的先序和后序遍历对应所转换的二叉树的先序和中序遍历。