【数据结构】树——二叉树

1.树的介绍以及树的基本概念和性质

2.二叉树介绍以及二叉树的性质

3.二叉树的构建：穷举创建，递归创建

4.二叉树的基本操作

之前我们介绍了顺序表，链表，以及栈和队列，这几种数据结构都属于线性结构，而我们接下来要讲的树属于非线性结构~

树的数据结构相当于一颗倒挂的树，由n个节点组成，最顶部的节点叫做根节点，最底下的节点称为叶子节点

1.根节点没有前驱节点的信息

2.每个节点都包含1个或者多个节点的后继（比如说根节点A分叉为两个后继节点B和C，也就是说A节点包含B和C节点的信息）

3.树是递归实现的

一棵树包含多个子树，每个子树又有自己的根节点，比如说A节点两边是左树B和右树C，左树B两边也有左树D和右树E……以此类推

---

接下来来认识一下树的一些常用概念性质(结合下图来认识)

（1）结点的度：一个结点含有子树的个数称为该结点的度；简单来说就是看结点分了多少个叉，A节点分了两个叉，那么A节点的度为6，D结点的度为1，F结点的度为3……

（2）树的度：就是这一整棵树多个子树的度中的最大度，A的度为6，F的度为3……度为6是最大的，所以该树的最大度为6

（3）叶子结点（终端结点）：叶子结点也叫终端结点，表示度为0的结点，度为0的结点就是该结点没有分叉，那么B,C,H,I,P,Q,K,L,M,N这些度为0的结点就统称为叶子结点

（4）父结点（双亲结点）：父结点也叫做双亲结点，某个结点的前驱就是该结点的父结点，比如说B的前驱是A，那么A就是B结点的父结点，B就是A结点的子结点

（5）孩子结点（子结点）：子结单就是某个结点的后继，比如A的后继有B,C,D,E,F,G 这些结点都属于A的子结点，因此！！父结点和子结点是相对而言的~

（6）根结点：一棵树中，没有双亲结点的结点；如上图：A（也就是一颗完整的树的第一个结点）

（7）结点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推,因此上图这颗树一共有4层~ A在第一层，BCDEFG在第二层，HIJKLMN在第三层，PQ在第四层

（8）树的高度或深度：树中结点的最大层次； 如上图：树的高度为4

---

树