1、树的概念与定义,树是n（n0）个结点的有限集合T 。
当n=0时 ， 称为空树；当n0时 ，该集合满足如下条件： (1) 其中必有一个称为根（root）的特定结点 ， 它没有直接前驱 ， 但有零个或多个直接后继 。
(2) 其余n-1个结点可以划分成m（m0）个互不相交的有限集T1 ， T2 ， T3 ， Tm ， 其中Ti又是一棵树 ， 称为根root的子树 。
每棵子树的根结点有且仅有一个直接前驱 ， 但有零个或多个直接后继,图6.1 树的图示方法,结点：包含一个数据元素及若干指向其它结点的分支信息 。
结点的度：一个结点的子树个数称为此结点的度 。
叶结点：度为0的结点 ， 即无后继的结点 ， 也称为终端结点 。
分支结点：度不为0的结点 ， 也称 。

2、为非终端结点 。
孩子结点：一个结点的直接后继称为该结点的孩子结点 。
双亲结点：一个结点的直接前驱称为该结点的双亲结点 。
兄弟结点：同一双亲结点的孩子结点之间互称兄弟结点,祖先结点：一个结点的祖先结点是指从根结点到该结点的路径上的所有结点 。
在图6.1中 ， 结点K的祖先是A、B、E 。
子孙结点：一个结点的直接后继和间接后继称为该结点的子孙结点 。
在图6.1中 ， 结点D的子孙是H、I、 J、 M 。
树的度： 树中所有结点的度的最大值 。
结点的层次：从根结点开始定义 ， 根结点的层次为1 ， 根的直接后继的层次为2 ， 依此类推 。
树的高度（深度）： 树中所有结点的层次的最大值 。
有序树：在树T中 ， 如果各子树Ti之间是 。

3、有先后次序的 ， 则称为有序树 。
森林： m（m0）棵互不相交的树的集合 。
将一棵非空树的根结点删去 ， 树就变成一个森林；反之 ， 给森林增加一个统一的根结点 ， 森林就变成一棵树,ADT Tree 数据对象D：一个集合 ， 该集合中的所有元素具有相同的特性 。
数据关系R： 若D为空集 ， 则为空树 。
若D中仅含有一个数据元素 ， 则R为空集 ， 否则R=H ， H是如下的二元关系： (1) 在D中存在唯一的称为根的数据元素root ，它在关系H下没有前驱 。
(2) 除root以外 ，D中每个结点在关系H下都有且仅有一个前驱,基本操作： (1) InitTree（Tree）： 将Tree初始化为一棵空树 。
(2) Destory 。

4、Tree（Tree）： 销毁树Tree 。
(3) CreateTree（Tree）： 创建树Tree 。
(4) TreeEmpty（Tree）： 若Tree为空 ，则返回TRUE ，否则返回FALSE 。
(5) Root（Tree）： 返回树Tree的根 。
(6) Parent（Tree ，x）： 树Tree存在 ，x是Tree中的某个结点 。
若x为非根结点 ， 则返回它的双亲 ，否则返回“空” 。
,7) FirstChild（Tree ， x）： 树Tree存在 ，x是Tree中的某个结点 。
若x为非叶子结点 ， 则返回它的第一个孩子结点 ，否则返回“空” 。
(8) NextSibling（Tree ， x）： 。

5、 树Tree存在 ， x是Tree中的某个结点 。
若x不是其双亲的最后一个孩子结点 ， 则返回x后面的下一个兄弟结点 ，否则返回“空,9) InsertChild（Tree ，p ，Child）：树Tree存在 ， p指向Tree中某个结点 ， 非空树Child与Tree不相交 。
将Child插入Tree中 ，做p所指向结点的子树 。
(10) DeleteChild（Tree ， p ， i）： 树Tree存在 ，p指向Tree中某个结点 ，1id ， d为p所指向结点的度 。
删除Tree中p所指向结点的第i棵子树 。
(11) TraverseTree（Tree ， Visit（）： 树Tree存在 ， Visit（）是对结点进行访 。

6、问的函数 。
按照某种次序对树Tree的每个结点调用Visit（）函数访问一次且最多一次 。
若Visit（）失败 ，则操作失败,二叉树的定义与基本操作,定义：我们把满足以下两个条件的树形结构叫做二叉树（Binary Tree）： （1） 每个结点的度都不大于2； （2） 每个结点的孩子结点次序不能任意颠倒 。
由此定义可以看出 ， 一个二叉树中的每个结点只能含有0、 1或2个孩子 ， 而且每个孩子有左右之分 。
我们把位于左边的孩子叫做左孩子 ， 位于右边的孩子叫做右孩子,图6.2给出了二叉树的五种基本形态,与树的基本操作类似 ， 二叉树有如下基本操作： (1) Initiate（bt）：将bt初始化为空二叉树 。
(2) 。

7、 Create(bt)： 创建一棵非空二叉树bt 。
(3) Destory（bt）： 销毁二叉树bt 。
(4) Empty（bt）：若bt为空 ， 则返回TRUE ， 否则返回FALSE 。
(5) Root(bt)： 求二叉树bt的根结点 。
若bt为空二叉树 ，则函数返回“空” 。
,6) Parent（bt ，x）：求双亲函数 。
求二叉树bt中结点x的双亲结点 。

来源：(未知)

【学习资料】网址：/a/2021/0323/0021754656.html

标题：概念|树的概念和定义