树(Tree)

• 根(root)
• 子树
• 结点：树的结点包含一个数据元素及若干指向其子树的分支
• 结点的度(Degree)：结点拥有的子树数

• 度为0的结点称为叶子(Leaf)或终端结点
• 度不为0的结点称为非终端结点或分支结点
• 树的度是树内各结点的度的最大值
• 结点的子树的根称为该结点的孩子(Child)，该结点称为孩子的双亲(Parent)
• 同一个双亲的孩子之间互称兄弟(Sibling)
• 祖先，子孙，堂兄弟。。。
• 层次(Level)：结点的层次从根开始定义起，根为第一层，根的孩子为第二层。。。
• 树的深度(Depth)或高度：树中结点的最大层次
• 结点的深度或高度
• 如果将树中结点的各子树看成从左至右是有次序的(即不能互换)，则称该树为有序树，否则为无序树
• 森林(Forest)：是m棵互不相交的树的集合

二叉树(Binary Tree)

• 二叉树的子树有左右之分，其次序不能任意颠倒
• 在二叉树的第i层上至多有2^i-1个结点(i>=1)
• 深度为k的二叉树至多有2^k -1个结点(k>=1)
• 对任何一颗二叉树T，如果其终端结点数为n₀ ，度为2的结点数为n₂，则n₀=n₂+1。
• 满二叉树：深度为k且有2^k-1个结点的二叉树，每一层的结点数都是最大结点数
• 完全二叉树：深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时。
• 具有n个结点的二叉树的深度：不大于log₂n的最大整数+1

顺序存储结构

• 将编号为i的结点元素存放在一维数组下标为i-1的分量中
• 仅适用与完全二叉树

链式存储结构

• 结点由数据域和左右指针构成 – 二叉链表
• 还可在结点结构中增加一个指向其双亲结点的指针域 – 三叉链表

遍历二叉树

• 先序(根)遍历
• 中序(根)遍历
• 后序(根)遍历

线索二叉树

• 增加LTag，RTag两个标志域
• LTag为0，lchild域指示结点的左孩子，LTag为1，lchild域指示结点的前驱
• RTag为0，rchild域指示结点的右孩子，RTag为1，rchild域指示结点的后继
• 以这种结点结构构成的二叉链表作为二叉树的存储结构，叫做线索链表
• 指向结点前驱和后继的指针叫做线索
• 对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化

树的存储结构

• 双亲表示法
• 孩子表示法
• 孩子兄弟表示法

森林与二叉树的转换

• 给定一棵树，可以找到惟一的一棵二叉树与之对应，从物理结构上看，它们的二叉链表相同，只是解释不同

树和森林的遍历

赫夫曼(Huffman)树 – 最优树

• 一类带权路径长度最短的树
• 路径长度：路径上的分支数目
• 树的路径长度是从树根到每个结点的路径长度之和
• 树的带权路径长度为树中所有叶子结点的带权路径长度之和，记作WPL
• n个叶子结点构造的树中，WPL最小的二叉树为最优二叉树或赫夫曼树

赫夫曼编码