数据结构 E HI K 孩子结点:结点的子树的根称为该结点的孩子。 双亲结点:B结点是A结点的孩子,则A结点是B结点 的双亲。 兄弟结点:同一双亲的孩子结点。 堂兄结点:同一层上结点 祖先结点:从根到该结点的所经分支上的所有结点。 子孙结点:以某结点为根的子树中任一结点都称为该 结点的子孙
数据结构 tjm 孩子结点：结点的子树的根称为该结点的孩子。 双亲结点：B结点是A结点的孩子，则A结点是B结点 的双亲。 兄弟结点：同一双亲的孩子结点。 堂兄结点：同一层上结点。 祖先结点: 从根到该结点的所经分支上的所有结点。 子孙结点：以某结点为根的子树中任一结点都称为该 结点的子孙。 A B C D E F G H I J K L M
数据结构 B D E F)(G)(H) K 结点的层次:根结点的层定义为1;根的孩子为 第二层结点,依此类推。 树的深度:树中最大的结点层。 有序树:子树有序的树。 无序树:不考虑子树的顺序。 森林:m(m>=0)棵互不相交的树的集合。 树的基本操作分为三大类:查找,插入,删除 (参见P119
数据结构 tjm 结点的层次：根结点的层定义为1；根的孩子为 第二层结点，依此类推。 树的深度：树中最大的结点层。 有序树：子树有序的树。 无序树：不考虑子树的顺序。 森林： m(m>=0)棵互不相交的树的集合。 A B C D E F G H I J K L M 树的基本操作分为三大类：查找，插入，删除 （参见P119）
数据结构 线性结构与树结构的比较: 线性结构: 树 第一个数据元素(无前驱)根结点(无前驱 最后一个数据元素(无后继)多个叶结点(无后继 其它数据元素(一个前驱,树中其它结点(一个 一个后继) 前驱,多个后继)
数据结构 tjm 线性结构与树结构的比较： 线性结构： 第一个数据元素（无前驱） 最后一个数据元素（无后继） 其它数据元素（一个前驱， 一个后继） 树： 根结点（无前驱） 多个叶结点（无后继） 树中其它结点（一个 前驱，多个后继）
数据结构 62二叉树 621二叉树的定义 定义:二叉树是n(n≥0个结点的有限集,它或为 空树(n=0),或由一个根结点和两棵分别称为左子 树和右子树的互不相交的二叉树构成。 特点: 每个结点至多有二棵子树即不存在度大于2的 结点); 叉树的子树有左、右之分,且其次序不能任 意颠倒。 二叉树的类型定义参见P121
数据结构 tjm 6.2 二叉树 6.2.1 二叉树的定义 定义：二叉树是n(n0)个结点的有限集，它或为 空树(n=0)，或由一个根结点和两棵分别称为左子 树和右子树的互不相交的二叉树构成。 特点： 每个结点至多有二棵子树(即不存在度大于2的 结点)； 二叉树的子树有左、右之分，且其次序不能任 意颠倒。 二叉树的类型定义参见P121
数据结构 二叉树的五种基本形态 A A A A B B B C 只有根结点 左、右子树 空二叉树的二叉树右子树为空左子树为空均非空 二叉树的基本操作也分为三大类:查找,插入, 删除(参见P121)
数据结构 tjm 二叉树的五种基本形态 A 只有根结点 的二叉树 空二叉树 A B 右子树为空 A B 左子树为空 A B C 左、右子树 均非空 二叉树的基本操作也分为三大类：查找，插入， 删除（参见P121）