八、树和二叉树

一、树的定义

树的定义
树是一种非线性的数据结构
树是由 n (n≥0) 个结点组成的有限集合
 如果 n = 0，称为空树 ；
 如果 n > 0，则 ：
  有一个特定的称之为根 (root) 的结点，它只有直接后继，但没有直接前驱
  除根以外的其它结点划分为 m (m≥0) 个互不相交的有限集合T0, T1, …,Tm-1， 每个集合又是一棵树， 并且称之为根的子树(subTree)

树家族中的概念
树的结点包含一个数据及若干指向子树的分支
结点拥有的子树数称为结点的度
 度为0的结点称为叶结点
 度不为0的结点称为分支结点
树的度定义为所有结点中的度的最大值

结点的直接后继称为该结点的孩子
 相应的，该结点称为孩子的双亲
结点的孩子的孩子的…… 称为该结点的子孙
 相应的，该结点称为子孙的祖先
同一个双亲的孩子之间互称兄弟

结点的层次
 根为第1层
 根的孩子为第2层
 ……
树中结点的最大层次称为树的深度或高度

如果树中结点的各子树从左向右是有次序的，子树间不能互换位置 ，则称该树为有序树 ，否则为无序树。

森林是由 n ( n≥0) 棵互不相交的树组成的集合

树的一些常用操作

创新互联公司专注于资溪网站建设服务及定制，我们拥有丰富的企业做网站经验。 热诚为您提供资溪营销型网站建设，资溪网站制作、资溪网页设计、资溪网站官网定制、微信平台小程序开发服务，打造资溪网络公司原创品牌,更为您提供资溪网站排名全网营销落地服务。

创建树
销毁树
清空树
插入结点
删除结点
获取结点
获取根结点
获取树的结点数
获取树的高度
获取树的度

二、树的存储结构

树的存储结构
无法直接用数组表示树的逻辑结构
但可以设计结构体数组对结点间的关系进行表述

利用链表组织树中的各个结点
链表中的前后关系不代表结点间的逻辑关系
结点的逻辑关系由 child 数据域描述
child 数据域保存其他结点的存储地址

三、二叉树的定义

另一种树结构模型
孩子兄弟表示法模型
每个结点都有一个指向其第一个孩子的指针
每个结点都有一个指向其第一个右兄弟的指针

每个结点包含一个数据指针和两个结点指针
数据指针 ： 指向保存于树中的数据
孩子结点指针 ： 指向第一个孩子
兄弟结点指针 ： 指向第一个右兄弟

孩子兄弟表示法的特点
能够表示任意的树形结构
每个结点中有且仅有三个指针域
 数据指针，孩子结点指针，兄弟结点指针
每个结点的结构简单
 只有孩子结点指针和兄弟结点指针构成了“树杈"
二叉树的定义
二叉树是由n ( n ≥0) 个结点组成的有限集合， 该集合或者为空， 或者是由一个根结点加上两棵分别称为左子树和 右子树的 、 互不相交的二叉树组成。

特殊的二叉树

满二叉树(Full Binary Tree)
如果 二叉树中所有分支结点的度数都为2， 且叶子结点都在同一层次上 ， 则称这类二叉树为满二叉树 。

完全二叉树 (Complete Binary Tree)
如果一棵具有n个结点的高度为k的二叉树， 它的每一个结点都与高度为k 的满二叉树中编号为1—n 的结点一一对应， 则称这棵二叉树为完全二叉树。（从上到下从左到右编号)
完全二叉树的叶结点仅出现在最下面两层
 最下层的叶结点一定出现在左边
 倒数第二层的叶结点一定出现在右边
完全二叉树中度为1的结点只有左孩子
同样结点数的二叉树 ， 完全二叉树的高度最小

通用树实现源码