树与二叉树

树与二叉树的知识点总结：有n个结点的完全二叉树，如果i=1是根，则结点n的的双亲是n/2，孩子是2n，2n+1；如果i=0是根，则结点n的双亲是[n/2的天花板函数-1],孩子是2n+1,2n+2。

树

• 树的基本术语
  • 结点的度：与结点相连的分支的个数；树的度：树中所有结点的度的最大值； 叶子（终端）结点：出度为0的结点； 分支（非终端）结点：出度不为0的结点；入度为0的结点是根结点； 树的深度：树中结点的最大层次；
  • 森林是m棵互不相交的树的集合。一棵树去掉根，其子树构成森林；一个森林增加一个根成为树。
• 二叉树
  • 基本定义
    • 二叉树的每个结点最多有两个子树（出度<=2）
    • 满二叉树：深度为k且有2^k-1个结点；完全二叉树：同一层加点有顺序，叶子结点相差在两层内
  • 性质
    • ①在二叉树的第i层上最多有2^（i-1）个结点（1 2 4 8 16....）
    • ②深度为k的二叉树至多有2^k-1个结点，至少有k个结点
    • ③二叉树的叶子结点数为n0，出度为2的结点数为n2，则n0=n2+1
    • ④具有n个结点的完全二叉树的深度为
    • ⑤有n个结点的完全二叉树，如果i=1是根，则结点n的的双亲是n/2，孩子是2n，2n+1；如果i=0是根，则结点n的双亲是[n/2的天花板函数-1],孩子是2n+1,2n+2
    • ⑥对于满二叉树而言，第i层的第一个结点标号为2^(i-1),最后一个结点标号为2^i-1(根标号为1)
  • 存储结构
    • 顺序存储结构
    • 链式存储结构
      • n个结点，利用了n-1个指针，有n+1个空链域
  • 遍历二叉树
    • 先序：根结点->左子树->右子树 首项为根结点，第二项为根结点左孩子
    • 中序：左子树->根结点->右子树 根结点前面的左孩子，后面的是右孩子
    • 后序：左子树->右子树->根结点 末项为根结点，倒数第二项为根结点右孩子
    • 给定前/后序 + 中序，可以画出一棵树（前/后序用来确定根结点，中序用来确定左右孩子）
  • 线索二叉树
    • • 0表示是孩子指针，1表示是线索
    • 一个结点的前驱和后继可能是双亲或者祖先，但不可能是它的孩子
• 数和森林
  • 树的存储结构
    • 双亲表示法
    • 孩子表示法
      • • • 在CTBox中加上int parent ;//双亲位置域 ，可以得到带双亲的孩子链表
    • 孩子兄弟法
      • • • 用二叉链表表示的图形，如果ROOT有nextsibling，则表示的是森林；如果ROOT没有nextsibling，则表示的是树
  • 森林与二叉树的转换
    • 树与二叉树，森林与二叉树
      • 给定一棵树，可以找到唯一一棵二叉树与之对应（从物理结构上看，二叉链表相同，但解释不同）（对应二叉树 root的右子树必为空）
      • 若把森林中每棵树的根结点看作是第一棵树的根结点的兄弟，可以导出森林与二叉树的关系
      • 森林可以分成三部分：第一棵树的根结点；第一棵树根结点的子树森林；除第一棵树外其他树构成的森林
      • F={T1,T2,T3....}是森林，B（root,LB,RB）是二叉树 1.森林转换成二叉树：若F为空，则B为空；若F非空，则B的root为①，B的LB由②转换，B的右子树由③转换； 2.二叉树转换成森林： 若B为空，则F为空；若B非空，则F非空，F第一棵树的根结点为B的root，F第一棵树除根结点的子树森林有B的LB转换，F其余的树由B的RB转换
    • 树的遍历
      • 先根遍历树
        • 先访问树的根结点，然后依次先根遍历根的每棵子树（首项为root） 对应二叉树的前序遍历
      • 后根遍历树
        • 先依次后根遍历每棵子树，然后访问根结点（末项为root） 对应二叉树的中序遍历
      • 层次遍历树
    • 森林的遍历
      • 先序遍历森林
        • 访问第一棵树的根结点；先序遍历第一棵树中根结点的子树森林；先序遍历除去第一棵树剩余的树构成的森林【对每棵树进行先根遍历】 对应二叉树的先序遍历
      • 中序遍历森林
        • 中序遍历第一颗树的根结点的子树森林；访问第一棵树的根结点；中序遍历除去第一棵树后剩余的树构成的森林【对每棵树进行后根遍历】 对应二叉树的中序遍历
      • 后序遍历森林
        • 会岔开root与子树，一般不采用
• 哈夫曼树
  • 从树中一个结点到另一个结点之间的分支构成两个结点之间的路径 ，路径上的分支数目称做路径长度 树的路径长度是从树根到每一个结点的路径长度之和。
  • 结点的带权路径长度为从该结点到树根之间的路径长度与结点上权的乘积。 树的带权路径长度为树中所有叶子结点的带权路径长度之和。
  • 构造哈夫曼树
    • 选择权值最小的两个结点作为左右子树，构建一棵二叉树
    • • 黑圈为已给数据，红框为哈夫曼编码
• 森林的遍历
  • 先序序列：ABCDEFGHIJ 中序序列：BCDAFEHJIG
• 树的遍历
  • 先根序列：ABCDE；后根序列：BDCEA；层次遍历：ABCED
• 已知序列画树
  • 若：空树：# 叶子结点：A##
  • 则：已知前序or后序序列可以画树，中序不能唯一确定一棵树
  • 当操作数为叶子结点，运算符为分支结点，根据先缀表达式（前序），可以唯一确定一棵树