树和二叉树基本概念

• 树是由一个汇合以及在该汇合上定义的一种关系形成的
• 汇合中的元素称为树的 结点 ，所定义的关系称为 父子关系
• 父子关系在树的结点之间建设了一个层次结构
• 树的结点蕴含 一个数据元素 和指向其子树的若干分支
• 根结点 具备非凡位置，简称为 根

树（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$ 个结点的二叉树
• 满二叉树 中每层都达到最大数，即 每层结点都是满的

齐全二叉树

• 在一棵 满二叉树中 ，从最上层最右侧起， 去掉相邻的若干叶子节点，失去的即为齐全二叉树
• 满二叉树肯定是齐全二叉树，而齐全二叉树不肯定是满二叉树

二叉树的性质

1. 在二叉树的第 i 层上，最多有 $2^(n-1)$ 个结点（根是第 1 层）
2. 高度为 h 的二叉数至少有$2^h$- 1 个结点
3. 对于任意一棵二叉树，叶子节点数 = 度为 2 的结点数 + 1
4. 有 n 个结点的齐全二叉树的高度为 $log_2^n$+1，其中$log_2^n$ 是向下取整
5. 含有 n >= 1 个结点的二叉树高度至少为 n -1；高度至多为 $log_2^n$+1，其中$log_2^n$ 是向下取整

6. 如果对一棵含有 n 个结点的齐全二叉树的结点进行编号，则对任意结点 i

   1. 如果 i =1，则结点 i 是二叉树的根；如果 i >1，则其双亲结点为 i / 2 向下取整
   2. 如果 2i>n, 则结点 i 无左孩子；否则其左孩子为 2i
   3. 如果 2i+1>n，则结点 i 无右孩子；否则其右孩子为 2i+1

二叉树的存储构造

二叉树的存储构造有两种：顺序存储构造 和链式存储构造

顺序存储构造

• 对于 满二叉树 和齐全二叉树 来说，能够将其存储在一组间断的存储单元中
• 用一维数组来实现顺序存储构造 时，将二叉树第 i 个结点寄存到数组中第 i 个重量中
• 依据二叉树的性质，能够失去结点 i 的父结点、左右孩子结点别离寄存在 i /2、2i、2i+ 1 重量中
• 这种存储形式对于 满二叉树 和齐全二叉树 是十分适合并且高效不便 的，因为满二叉树和齐全二叉树采纳顺序存储构造即 不节约空间，也能依据公式很快确定结点之间的关系
• 然而对于个别的二叉树而言，必须用“虚结点 ”将一棵二叉树 补成一棵齐全二叉树 来存储，否则 无奈确定结点之间的前驱后继关系 ，然而这样就会造成 空间的节约

链式存储构造

• 设计不同的节点构造可形成不同的链式存储构造
• 在二叉树中，每个结点都有两个孩子，则能够设计成每个结点至多蕴含 3 个域：数据域、左孩子域、右孩子域
• 利用此构造失去的二叉树存储构造称为 二叉链表 。数据域存放数据元素， 左孩子域寄存指向左孩子结点的指针，右孩子域寄存指向右孩子的指针
• 为了不便找到父结点，能够在上述结点构造中 增加一个指针域 ， 指向结点的父结点 ，采纳此构造失去的存储构造称为 三叉链表