树和二叉树

这是一篇关于树和二叉树的思维导图，主要内容有二叉树、树、哈夫曼树、线索二叉树、遍历二叉树等。

树和二叉树

• 二叉树
  • 定义
    • 二叉树是n(n≥0)个结点的有限集合，每个结点的度都不大于2。
  • 基本操作
    • LeftChild（bt， x）
      • 求以bt为根的二叉树结点x的左孩子。 若结点x无左孩子或x不在bt中， 则返回“空”。
    • RightSibling（bt， x）
      • 求以bt为根的二叉树结点x的右孩子。若结点x无右孩子或x不在bt中， 则返回“空”。
    • InsertChild（bt， p， child）
      • 以bt为根的二叉树已存在，p指向bt中某个结点，非空树child与bt不相交。将child子树插入bt，成为p所指向结点的子树。
    • DeleteChild（bt，p，i）
      • 以bt为根的二叉树已存在，p指向bt中某个结点，1≤i≤d≤2，d为p所指向结点的度。删除bt中p所指向结点的第i棵子树
    • leverororderTraversertree（bt）
      • 以bt为根的二叉树已存在，水平遍历二叉树中每个结点一次且仅一次。
    • preororderTraversertree（bt）
      • 以bt为根的二叉树已存在，按先序遍历二叉树中每个结点一次且仅一次。
  • 性质
    • 性质1： 在二叉树中，第i层结点数最多为2i-1个
    • 性质2： 深度为k的二叉树结点总数最多为：2k-1个
    • 性质3 : 对任一棵二叉树，如果叶结点数为n0，度为2的结点数为n2，则n0=n2+1。
    • 性质４`:有n个结点的完全二叉树，如果深度为K那么 K=|log2n|+1
    • 性质5：性质5 如果完全二叉树有ｎ个结点，则任意结点i (１≤i≤ｎ)，有： (１)若i＞１，则ｉ的双亲是i/2；若ｉ=１则ｉ是根无双亲； (２)若２i≤ｎ，则ｉ的左孩子是２i；若２i＞ｎ则ｉ无左孩子； (３)若２i＋１≤ｎ，则ｉ的右孩子２i＋１；若２i＋１＞ｎ，则ｉ无右孩子。
  • 满二叉树和完全二叉树
    • 满二叉树
      • 一棵二叉树如果深度为k，就有有2k-1个结点，则二叉树是满二叉树。
    • 完全二叉树
      • 与满二叉树的编号对应，但不要求每层均具有最 大结点数
    • 区别与联系
      • 满二叉树一定是完全二叉树，完全二叉树不一定 是满二叉树
• 树
  • 定义
    • 树是n(n≥0)个结点的有限集合。
  • 基本操作
    • InitTree（T）
      • 初始化树一棵树，树根为T。
    • DestoryTree（T）
      • 销毁以T为根的树，并释放所占内存空间。
    • CreateTree（T）
      • 创建一棵以T为根的树。
    • TreeEmpty（T）
      • 判断以T为根的树是否空，如果为空返TRUE，否则返FALSE。
    • Root（S）
      • 求一棵树的根，S是某树中的一个结点，返回S所在的树的根。
    • Depth(T)
      • 以T为根的树已经存在，求树T的深度并以函数值返回。
    • Parent（T，x）
      • 以T为根的树已经存在，x是T中的某个结点。若x为非根结点，则返回它的双亲，否则返回“空”。
    • FirstChild（T，x）
      • 以T为根的树已经存在，x是T中的某个结点。若x为非叶子结点，则返回它的第一个孩子结点，否则返回“空”。
    • NextSibling（T，x）
      • x是T中的某个结点。若x不是其双亲的最后一个孩子结点，则返回x后面的下一个兄弟结点，否则返回“空”。
    • InsertChild（T，p，Child）
      • 以T为根的树已经存在，p指向T中某个结点，非空树Child与T不相交。将Child插入T中，称为p所指向结点的子树。
    • DeleteChild（T，p，i）
      • 以T为根的树已经存在，Visit（）是对结点进行访问的函数。按照某种次序对树T的每个结点调用Visit（）函数访问一次且仅一次。若Visit（）失败，则操作失败。
• 哈夫曼树
  • 术语
    • 路径
      • 从树中的任一结点出发，沿着分枝能够达到另一结点，这两个结点间存在路径。
    • 路径的长度
      • 两个结点间路径上的分枝数称为。 路径的长度
    • 结点的带权路径长度
      • 从树根到某一叶结点的路径长度与该结点的权的乘积，称为该结点的带权路径长度。
  • 特点
    • 没有度为1的结点
    • 哈夫曼树的任意分支节点的左右子树交换后仍是哈夫曼树
    • n个叶子结点的哈弗阿曼书共有2n-1个结点
  • 应用
    • 变长指令编码
    • 图像的无损压缩
• 线索二叉树
  • 定义
    • 线索
      • 利用控指针分别指向前驱或后继。指向前驱和后继的指针叫线索。
    • 线索链表
      • 以这种存储结构组成的二叉链表叫做线索链表。
    • 线索化
      • 以二叉树某一种遍历顺序给空指针加线索的过程叫做线索化。
    • 线索化二叉树
      • 线索化了的二叉树称为线索二叉树。
  • 构造线索二叉树
    • 以结点p为根的子树中序线索化
    • 带头结点的二叉树中序线索化
  • 遍历线索二叉树
    • 先序线索二叉树查找
    • 中序线索二叉树查找
    • 后序线索二叉树查找
• 遍历二叉树
  • 先序遍历
    • 先访问根结点，再先序遍历左子树，最后先序遍历右子树。
    • 非递归算法步骤
      • 初始化栈，根压入栈。
      • 若栈非空出栈，出栈结点为P，访问P结点数据；若栈空结束。
      • 若P结点的右指针非空压栈；若P结点的左指针非空压栈，返回步骤二。
  • 中序遍历
    • 先中序遍历左子树，再访问根结点，最后中序遍历右子树
    • 非递归算法步骤
      • 初始化栈，P赋值为根指针。
      • 若栈或P非空执行步骤三，若栈或P空结束。
      • 若P为非空，入栈，P赋值为P结点的左指针
      • 若P为空，栈顶出栈赋值给P。访问P结点数据，且P赋值为其右指针，返回步骤二。
  • 后序遍历
    • 先后序遍历左子树，再中序遍历右子树，最后访问根结点
    • 非递归算法步骤
      • 初始化栈，（根+ mark=0）入栈。
      • 若栈非空出栈P，若栈空结束。
      • 若P的标记为0，修改标记为1，左子树入栈。
      • 若P的标记为1，修改标记为2，右子树入栈。
      • 若P的标记为2，访问P结点，返回步骤二。
  • 水平遍历
    • 二叉树的水平遍历是按二叉树的层次遍历，第一层遍历完成再遍历第二层……
    • 算法
      • 初始化一个队列，将根结点入队。
      • 队不空出队一个元素P，访问P点数据元素。队空结束。
      • 如果P->lchild非空入队。
      • 如果P->rchild非空入队。返回步骤二。
• 存储结构
  • 顺序存储
    • 用一组连续的存储单元存储二叉树的数据元素，完全二叉树可以用一维数组按完全二叉树编号顺序存储。
  • 链式存储
    • 最简单的链式结构是每个结点由基本元素、左孩子、右孩子三个域组成。