树与二叉树

数据的逻辑结构
线性结构的元素时一对一的，树可以说是一对多的。

树型结构(非线性结构）

1. 结点之间有分支
2. 具有层次关系

树的定义

树的定义类似递归的定义

树的其他表达方式：

树的基本术语：

根节点：非空树中无前驱结点的结点
结点：树中的每一个元素
结点的度：结点拥有的子树的数量。
树的度：树内各结点的度的最大值。
叶子（终端结点）：度=0的结点，
分支结点：度不等于0的结点，非终端结点
内部结点：根节点以外的分支结点称为内部节点
树的深度：树中结点的最大层次，有时候也称树的高度。

森林:

树结构与线性结构的比较：

二叉树

二叉树定义

注：二叉树不是树的特殊情况，他们是两个概念，二叉树结点的子树要区分左子树和右子树，即使只有一颗子树也要进行区分，说明他是子树还是右子树。

具有三个节点的二叉树有5中不同的形态，而树只有两种形态。

二叉树的五种基本形态

二叉树的抽象数据定义

二叉树的性质和储存结构

性质1：在二叉树的第i层至多有 个结点。至少有一个结点。

性质2：深度为k的二叉树至多有 个结点。

性质3：

满二叉树

一颗深度为k且有 个结点的二叉树称为满二叉树。
特点：

完全二叉树

和满二叉树的序号一一对应的上。

**注：在满二叉树中，从最后一个结点开始，连续去掉任意个结点，即是一个完全二叉树。

性质4：具有n个结点的完全二叉树的深度为 （向下取整）。

性质5：

二叉树的储存结构

顺序存储结构

二叉树的顺序存储缺点：
最坏情况：

二叉树的链式存储结构

三叉链表

遍历二叉树

遍历定义：顺着某一条搜索路径访问二叉树的结点，使得每一个结点均被访问一次，而且仅被访问一次（又称周游）。

由先序和中序可以确定一颗二叉树
由后序和中序可以却确定一颗二叉树

递归

二叉树的层次遍历算法