树是一种非线性的数据结构，用它能很好地描述有分支和层次特性的数据集合。树型结构在现实世界中广泛存在，如社会组织机构的组织关系图就可以用树型结构来表示。树在计算机领域中也有广泛应> 用，如在编译系统中，用树表示源程序的语法结构。在数据库系统中，树型结构是数据库层次模型的基> 础，也是各种索引和目录的主要组织形式。在许多算法中，常用树型结构描述问题的求解过程、所有解的状态和求解的对策等。在这些年的国内、国际信息学奥赛、大学生程序设计比赛等竞赛中，树型结构成为参赛者必备的知识之一，尤其是建立在树型结构基础之上的搜索算法。
  在树型结构中，二叉树是最常用的结构，它的分支个数确定、又可以为空、并有良好的递归特性，特别适宜于程序设计，因此也常常将一般树转换成二叉树进行处理。

👆图1.1 认识节点

概念

1. 节点(node)：图1.1中的每个圆圈(树的元素)都代表一个节点
2. 根节点(root)：图1.1中的1号节点，一个没有父亲节点的节点
   
   👆图1.2 子树(子集)
3. 除根结点外，其余 $m$ 个结点能分成 $m(m>=0)$ 个互不相交的有限集合 $T_0,T_1,T_2,……T_{m-1}$ 。其中的每个子集又都是一棵树，这些集合称为这棵树的子树。
4. 节点的度：一个节点儿子节点的个数
5. 在用图形表示的树型结构中，对两个用线段（称为树枝）连接的相关联的结点，称上端结点为下端结点的父结点，称下端结点为上端结点的子结点。称同一个父结点的多个子结点为兄弟结点。
6. 层次(level)：根节点层数为1，其余节点的层数皆为父亲节点层数加一。
7. 深度(depth)：一棵树中所有的结点的层次的最大值。

👆图2.1 二叉树

二叉树的遍历

树的遍历方式主要分为三种：

1. 前序遍历：先遍历根节点，在遍历左子树，最后遍历右子树，对于任意一个子树，仍按照先序进行遍历。图2.1中的二叉树的先序遍历：1 2 5 8 9 6 4 7 10 11

2. 后序遍历：先遍历左子树，在遍历右子树，最后遍历根节点，对于任意一个子树，仍按照后序进行遍历。图2.1中的二叉树的后序遍历：8 9 5 6 2 10 11 7 4 1

3. 中序遍历：先遍历左子树，在遍历根节点，最后遍历右子树，对于任意一个子树，仍按照中序进行遍历。图2.1中的二叉树的先序遍历：8 5 9 2 6 1 4 10 7 11

练习

注：无视三号即可按照二叉树的方法遍历
答案（CTRL+a查看答案、7是左子树）：$\color{white}{先序12564789；中序52618794；后序56289741}$

二叉树知二定一：必须有中序

整体思路：先用前（后）序遍历找出根节点，将根节点写入草稿纸中，然后根据根节点在中序中找到左子树和右子树。