树、二叉树、森林

树和二叉树

树

• 树是一种新的逻辑结构

集合: 数据元素间除了"同属于一个集合"外,无其他关系
线性结构: "一对一的关系",如线性表,栈、队列、串
树形结构: "一对多的关系",如: 树
图形结构: "多对多"的关系,如: 图

• 常见的树形结构

目录
家庭关系
文件目录
...

• 树的定义

  • 树是n个节点的有限集
  • 节点个数为零的树成为空树
  • 任意一个非空树中n>0
  • 有且仅有一个特定的称为根的节点
  • 非根的节点可以分为互不相交的有限集,每个集合本身又是一棵树,这些树称为根的子树
  • 度: 节点最多分叉数量

• 节点的层次: 根到该节点的层数

 树的度:
      根的度:
      关系树的度:

    树的深度:
      从根节点垂直向下数

• 树的家谱图

  双亲	上层的节点(直接前驱)
  孩子	下层节点的子树的根(直接后驱)

  祖先	从根到该节点所经分支的所有节点
  子孙	该节点下层子树中的任一节点

  兄弟	同一双亲的同层节点
  堂兄弟	双亲位于同一层的节点(但并非同一双亲)

• 森林
  

  森林: 删除根节点后不相交的树的集合
  有序树: 节点各子树从左至右有序,不能互换(左为第一)
  无序树: 节点各子树可互换位置

二叉树(Binary Tree)：

• 二叉树是n >= 0个节点所构成的集合，它或为空树n = 0;或非空树,对于非空树T

  • 有且仅有一个称之为根的节点
  • 除根以外的其余节点分为两个互不相交的子集T_1和T_2，分别称为T的左子树和右子树,且T_1和T_2本身又都是二叉树

• 二叉树的特点及与树的异同

  二叉树	树
  具有递归性	具有递归性
  至多只有两颗子树(节点的度不超过 2)	没有限制子树个数的上限
  子树有左右之分,其次序不能任意颠倒(有序树)	子树可能有有序,也可能无序

• 二叉树的几种形态

  

• 三节点二叉树的五种形态

  

• 为什么研究二叉树

  普通树(多叉树)不转化为二叉树,运算很难实现
  为何要重点研究每个节点最多只有两个二"叉"的树
  可以证明,所有树都能转化为唯一对应的二叉树，不失一般性。
  

二叉树的性质

• 性质一

  在二叉树的第 i 层上至多有2^(i-1)个节点

• 性质二

  深度为k的二叉树至多有(2^k)-1个节点
  深度为 1: 1=(2^1)-1个节点
  ...

• 性质三

  对于任何一个二叉树,若 2 度的节点数有n_2个,则叶子数n_0必定为n_2+1,即 n_0 = n_2 + 1

完全二叉树与满二叉树

满二叉树	完全二叉树
深度为k且含有(2^k)-1个节点的二叉树	深度为k,有n个节点的二叉树,当且仅当其每个节点都与深度为k的满二叉树中(自上而下从左往右)编号从1至n的节点一 一对应

• 满二叉树的特点

  1. 每一层上的节点树都是最大节点数
     
  2. 每一层 i 的节点树都具有最大值 2^(i-1)

树和二叉树的转换及其应用

树转换为二叉树

• 转换的实现步骤

  1. 加线: 在兄弟之间加一条连线
  2. 抹线: 在每个节点,除了其左孩子外,去除其余孩子之间的关系
  3. 以树的根节点为轴心,将整树顺时针旋转45°

  

  

二叉树转换为树

1. 加线: 若p节点是双亲节点的左孩子,则将p的右孩子,右孩子的右孩子...沿分支找到的所有右孩子,都与p的双亲用线连起来
2. 抹线: 抹掉原二叉树中双亲与右孩子之间的连线
3. 将节点按层次排列,形成树结构

森林

森林转换为二叉树(二叉树与多颗树之间的关系)

1. 将各棵树分别转换成二叉树
2. 将每棵树的根节点用线相连
3. 以第一颗树根节点为二叉树的根,再以根节点为轴心,顺时针旋转,构成二叉树型结构

二叉树转换为森林

1. 抹线: 将二叉树中根节点与其右孩子连线,沿右分支搜索到的所有右孩子间连线全部抹掉,使之变成孤立的二叉树
2. 还原: 将孤立的二叉树还原成树