树和二叉树基本概念
- 树是由一个汇合以及在该汇合上定义的一种关系形成的
- 汇合中的元素称为树的 结点 ，所定义的关系称为 父子关系
- 父子关系在树的结点之间建设了一个层次结构
- 树的结点蕴含 一个数据元素 和指向其子树的若干分支
- 根结点 具备非凡位置，简称为 根
树（tree）是 n（n>=0）个结点的无限集
- 或者是一个 空树（n=0），空树中不蕴含任何结点
- 或者是一棵 非空树（n>0），此时有且仅有一个称为根的特定的结点
结点的度与树的度
- 结点领有的 子树的数目 称为 结点的度（Degree）
- 度为 0 的结点称为 叶子（leaf）结点 或终端结点
- 度不为 0 的结点称为 非终端结点 或分支结点。除根之外的分支结点也称为 外部结点
- 树内 各结点的度的最大值 称为 树的度
结点的档次和树的深度
- 结点的 档次 （level）从根开始定义， 根结点档次为 1 ，其子树档次为 2
- 树中的最大档次数称为数的 深度（Depth）或 高度
父亲、儿子、兄弟
- 父亲（parent）：一个结点的间接前驱结点
- 儿子（child）：一个结点的间接后继结点
- 兄弟（sibling）：同一个父亲结点的其余结点
先人、子孙、堂兄弟
- 先人 ：从根到该结点的门路上的 所有结点
- 子孙 ： 以某结点为根 的树中的 任一结点 都是该结点的子孙
- 堂兄弟 ： 父亲结点在同一档次 的结点
有序树、m 叉树、森林
- 有序树：树中结点的各子树从左至右看成有程序的（若不特指阐明，个别探讨的都是有序树）
- 无序树：不思考子树的程序
- m 叉树 ：树中所有 结点的最大度为 m 的有序树
- 森林 ：m（m>=0）棵互不相交的 树的汇合
二叉树
- 每个结点的 度均不超过 2 的有序树，称为 二叉树（binary tree）
- 二叉树或者是一棵 空树 ，或者是由一个根结点和两个互不相交的 左子树 和右子树 组成的非空树
满二叉树
- 高度为 k 并且有
$2^k+1$个结点的二叉树 - 满二叉树 中每层都达到最大数，即 每层结点都是满的
齐全二叉树
- 在一棵 满二叉树中 ，从最上层最右侧起， 去掉相邻的若干叶子节点，失去的即为齐全二叉树
- 满二叉树肯定是齐全二叉树，而齐全二叉树不肯定是满二叉树
二叉树的性质
- 在二叉树的第 i 层上，最多有
$2^(n-1)$个结点（根是第 1 层） - 高度为 h 的二叉数至少有
$2^h$- 1 个结点 - 对于任意一棵二叉树，叶子节点数 = 度为 2 的结点数 + 1
- 有 n 个结点的齐全二叉树的高度为
$log_2^n$+1，其中$log_2^n$是向下取整 - 含有 n >= 1 个结点的二叉树高度至少为 n -1；高度至多为
$log_2^n$+1，其中$log_2^n$是向下取整 -
如果对一棵含有 n 个结点的齐全二叉树的结点进行编号，则对任意结点 i
- 如果 i =1，则结点 i 是二叉树的根；如果 i >1，则其双亲结点为 i / 2 向下取整
- 如果 2i>n, 则结点 i 无左孩子；否则其左孩子为 2i
- 如果 2i+1>n，则结点 i 无右孩子；否则其右孩子为 2i+1
二叉树的存储构造
二叉树的存储构造有两种：顺序存储构造 和链式存储构造
顺序存储构造
- 对于 满二叉树 和齐全二叉树 来说，能够将其存储在一组间断的存储单元中
- 用一维数组来实现顺序存储构造 时，将二叉树第 i 个结点寄存到数组中第 i 个重量中
- 依据二叉树的性质，能够失去结点 i 的父结点、左右孩子结点别离寄存在 i /2、2i、2i+ 1 重量中
- 这种存储形式对于 满二叉树 和齐全二叉树 是十分适合并且高效不便 的，因为满二叉树和齐全二叉树采纳顺序存储构造即 不节约空间，也能依据公式很快确定结点之间的关系
- 然而对于个别的二叉树而言，必须用“虚结点 ”将一棵二叉树 补成一棵齐全二叉树 来存储，否则 无奈确定结点之间的前驱后继关系 ，然而这样就会造成 空间的节约
链式存储构造
- 设计不同的节点构造可形成不同的链式存储构造
- 在二叉树中，每个结点都有两个孩子，则能够设计成每个结点至多蕴含 3 个域：数据域、左孩子域、右孩子域
- 利用此构造失去的二叉树存储构造称为 二叉链表 。数据域存放数据元素， 左孩子域寄存指向左孩子结点的指针，右孩子域寄存指向右孩子的指针
- 为了不便找到父结点，能够在上述结点构造中 增加一个指针域 ， 指向结点的父结点 ，采纳此构造失去的存储构造称为 三叉链表