数据结构与算法--二叉树1

https://www.jianshu.com/p/bf73c8d50dc2

1.概念

1.1结点

结点 是数据结构中的基础，是构成复杂数据结构的基本组成单位。

2.树

2.1树的定义

树（Tree)是n （n>0）个结点的有限集，n=0为空树。
在任意一颗非空树中：

1. 有且仅有一个特定的结点（root）称为根
2. n>1时，其余结点可分为m(m>0)个互不相交的有限集T1、T2…Tn，其中每个集合本身又是一棵树，并且成为根的子树

2.2结点的度

节点拥有的子数目称为结点的 度。

2.3结点关系

结点子树的根节点为该节点的 孩子结点。该结点称为孩子结点 的双亲结点。
同一个双亲结点的孩子结点之间互称兄弟结点。B和C

2.4结点层次

从根开始定义起，根为第一层，根的孩子为第一层，以此类推。

2.5树的深度

树中的结点的最大层次数称为树的深度和高度。图中树的深度为4。

3.二叉树

3.1二叉树定义

二叉树 是n(n>0)个结点的有限集合，该集合为空集（空二叉树）或由一个根结点和两颗不相交的、分别称为根结点的左子树和右子树组成。
如下图一颗普通的二叉树

3.2二叉树的特点

1. 每个节点最多有两颗子树，所以二叉树结点的度<=2
2. 左子树和右子树是有顺序的，次序不能任意颠倒
3. 即使树中某个结点只有一个子树，也是要区分他是左子树还是右子树

3.3二叉树的性质

1. 二叉树的第i层上最多有2^(i-1)个结点，i>=1
2. 二叉树中如果深度为k，那最多有2^k -1个结点，k>=1