树形结构是一种非线性结构。
树形结构是结点之间有分支，并具有层次关系的结构。它非常类似于自然界中的树。
树结构在客观世界中是大量存在的，例如家谱、行政组织机构都可用树形象地表示。
树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程。
树的实例——家族树
在现实生活中，有入如下血统关系的家族可用树形图表示：
- 张源有三个孩子张明、张丽和张亮；
- 张明有两个孩子张林和张维；
- 张亮有三个孩子张平、张华和张群；
- 张平有两个孩子张晶和张磊。
attachment:tree.jpg
树的定义：
树是由n (n≥0)个结点构成的有限集合；n=0的树称为空树；当n≠0时，树中的结点应该满足以下两个条件：
- 有且仅有一个特定的结点称之为根，它没有前驱结点；
其余结点分成m(m≥0)个互不相交的有限集合latex($$T_1, T_2,\cdots,T_m$$)，其中每一个集合又都是一棵树，称latex($$T_1, T_2,\cdots,T_m$$)为根结点的子树。
树的图示：
attachment:tree2.jpg
术语：
- 子结点：树中某个结点的子树之根称为该结点的孩子(Child)或子结点
- 父结点：该结点称为孩子的双亲(Parents)或父亲或父结点。
- 兄弟结点：同一个双亲的孩子称为兄弟(Sibling)结点。
- 结点的度：树中的一个结点拥有的子树数称为该结点的度(Degree)。
- 树的度：一棵树的度是指该树中结点的最大度数。：
- 叶结点：度为零的结点称为叶子(Leaf)或终端结点。
- 分支节点：度不为零的结点称分支结点或非终端结点。
路径：若树中存在一个结点序列k1，k2，…，kj，使得ki是ki+1的双亲(1≤i<j)，则称该结点序列是从kl到kj的一条路径(Path)或道路。
- 路径的长度：路径的长度指路径所经过的边(即连接两个结点的线段)的数目，等于j-1。
- 祖先和子孙：若树中结点k到ks存在一条路径，则称k是ks的祖先(Ancestor)，ks是k的子孙(Descendant)。一个结点的祖先是从根结点到该结点路径上所经过的所有结点，而一个结点的子孙则是以该结点为根的子树中的所有结点。（结点k的祖先和子孙不包含结点k本身。）
- 结点的层次：根结点的层次为1（也有将根的层次定义为0的），其余结点的层次为父结点的层次加1。即从根结点到该结点的路径长度加1。
- 树的高度：树中结点的最大层数称为树的高度(Height)或深度(Depth)。
- 堂兄弟：双亲在同一层的结点互为堂兄弟。
有序树和无序树：若将树中每个结点的各子树看成是从左到右有次序的(即不能互换)，则称该树为有序树(OrderedTree)；否则称为无序树(UnoderedTree)。（若不特别指明，一般讨论的树都是有序树。）
- 森林：森林(Forest)是m(m≥0)棵互不相交的树的集合。
- 同构：
树形结构的特点：
- 树中任一结点都可以有零个或多个直接后继(即孩子)结点，但至多只能有一个直接前趋(即双亲)结点。
- 树中只有根结点无前趋，它是开始结点；叶结点无后继，它们是终端结点。
- 祖先与子孙的关系是对父子关系的延拓，它定义了树中结点之间的纵向次序。
- 有序树中，同一组兄弟结点从左到右有长幼之分。对这一关系加以延拓，规定若k1和k2是兄弟，且k1在k2的左边，则k1的任一子孙都在k2的任一子孙的左边，那么就定义了树中结点之间的横向次序。
- 将一棵树的根结点去掉，它的子树的集合即为一个森林。而在森林中的每棵树之上加一个共同的根，森林就成为了一棵树。
- 从树的根结点到树中其余结点均存在一条惟一的路径。
树的基本操作：
- init_tree初始化
- destroy_tree销毁树
- create_tree创建树
- tree_empty判断空树
- root返回树根
- parent返回父结点
- first_child第一个字结点
- next_sibling下一个兄弟结点
- insert_child插入子结点
- delete_child删除子结点
- tranverse_tree遍历
二叉树的定义：
满足下列条件的树称为二叉树：
- 每个结点的度都不大于2
- 每个结点的孩子结点次序不能任意交换
术语：
- 左孩子
- 右孩子
二叉树五种基本形态：