树和二叉树

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

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

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

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

二叉树是n >= 0个节点所构成的集合，它或为空树n = 0;或非空树,对于非空树T
- 有且仅有一个称之为根的节点
- 除根以外的其余节点分为两个互不相交的子集T_1和T_2，分别称为T的左子树和右子树,且T_1和T_2本身又都是二叉树

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

二叉树的几种形态

image.png
三节点二叉树的五种形态

image.png
为什么研究二叉树

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

二叉树的性质

满二叉树	完全二叉树

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

加线: 若p节点是双亲节点的左孩子,则将p的右孩子,右孩子的右孩子...沿分支找到的所有右孩子,都与p的双亲用线连起来

抹线: 抹掉原二叉树中双亲与右孩子之间的连线

将节点按层次排列,形成树结构

二叉树转换为树

将各棵树分别转换成二叉树

将每棵树的根节点用线相连

以第一颗树根节点为二叉树的根,再以根节点为轴心,顺时针旋转,构成二叉树型结构

森林转换为二叉树

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

还原: 将孤立的二叉树还原成树

二叉树转换为森林