ch06-树和二叉树(1)

树和二叉树 树型结构 非线性结构之一以分枝关系定义的层次结构在客观世界和计算机程序设计中应用广泛如机构等级组织如语法分析重点学习树型结构的存储结构及操作 树 直观描述树 tree 是n个具有相同特性的数据元素的有限集若n 0 则称树为空树若树非空 则有且仅有一个根 root 结点 其余结点可分为m个互不相交的子集T1 T2 Tm 其中每个子集又是一棵树 并称为根的子树 树的递归特性 若树非空 对每一棵子树总是唯一地存在一个结点可由根直接到达 根 子树 基本术语结点 node 表示树中的元素 包括数据项及若干指向其子树的分支结点的度 degree 结点拥有的子树数叶子 leaf 度为0的结点孩子 child 结点子树的根称为该结点的孩子双亲 parents 孩子结点的上层结点叫该结点的 兄弟 sibling 同一双亲的孩子树的度 一棵树中最大的结点度数结点的层次 level 从根结点算起 根为第一层 它的孩子为第二层 深度 depth 树中结点的最大层次数森林 forest m m 0 棵互不相交的树的集合 基本术语 有序树树中结点的各子树从左至右是有次序的 不能互换 无序树树中结点的各子树从左至右是无次序的 结点A的度 3结点B的度 2结点M的度 0 叶子 K L F G M I J 结点A的孩子 B C D结点B的孩子 E F 结点I的双亲 D结点L的双亲 E 结点B C D为兄弟结点K L为兄弟 树的度 3 结点A的层次 1结点M的层次 4 树的深度 4 结点F G为堂兄弟结点A是结点F G的祖先 树的ADT定义 ADTTree D D是具有相同特性的数据元素的集合R 若D为空集 则称为空树若D仅含一个数据元素 则R为空集 否则R H H是如下二元关系 树的ADT定义 续 p InitTree 二叉树定义定义 二叉树是n n 0 个结点的有限集 它或为空树 n 0 或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成特点每个结点至多有二棵子树 即不存在度大于2的结点 二叉树的子树有左 右之分 且其次序不能任意颠倒基本形态 二叉树的ADT定义 ADTBinaryTree D D是具有相同特性的数据元素的集合R 若D为空集 则R也为空 称BinaryTree为空二叉树若D不为空集 则R H H是如下二元关系 二叉树的ADT定义 续 p InitBiTree 二叉树的性质 性质1在二叉树的第i层上至多有2i 1个结点 i 1 性质2深度为k的二叉树至多有2k 1个结点 k 1 性质3对任何一棵二叉树T 如果其叶结点数为n0 度为2的结点数为n2 则n0 n2 1两种特殊形态的二叉树满二叉树 深度为k且有2k 1个结点的二叉树完全二叉树 对满二叉树的结点进行连续编号 并约定编号从根结点起 自上而下 自左向右 则深度为k的 有n各结点的二叉树 当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时 称之为完全二叉树 二叉树的性质 性质4具有n个结点的完全二叉树的深度为log2n 1性质5如果对一棵有n个结点的完全二叉树的结点按层序编号 则对任一结点i有 1 如果i 1 则结点i是二叉树的根 无双亲 如果i 1 则其双亲结点是i 22 如果2i n 则结点i无左孩子 否则其左孩子是结点2i3 如果2i 1 n 则结点i无右孩子 否则其右孩子是结点2i 1 i 2 i i 1 2i 2i 1 2i 2 2i 3 i 1 i 2i 2 2i 3 2i 2i 1 结点i和i 1在同一层上 结点i和i 1不在同一层上 完全二叉树上结点及其左右子结点之间的关系 树的存储结构树的存储结构双亲表示法实现 定义结构数组存放树的结点 每个结点含两个域 数据域 存放结点本身信息双亲域 指示本结点的双亲结点在数组中位置特点 找双亲容易 找孩子难 defineMAX TREE SIZE100TypedefstructPTNnode TElemTypedata intparent 双亲位置域 PTNode Typedefstruct PTNodenodes MAX TREE SIZE intn 结点数 Ptree 0 1 1 2 4 4 4 0 如何找孩子结点 孩子表示法多重链表 每个结点有多个指针域 分别指向其子树的根结点同构 结点的指针个数相等 为树的度D结点不同构 结点指针个数不等 为该结点的度d 孩子链表 每个结点的孩子结点用单链表存储 再用含n个元素的结构数组指向每个孩子链表 孩子结点 typedefstructCTNode intchild 该结点在表头数组中下标structCTNode next 指向下一孩子结点 ChildPtr 表头结点 typedefstructtnode TElemTypedata 数据域ChildPtr firstchild 指向第一个孩子结点 CTBox 树 typedefstruct CTBoxnodes MAX TREE SIZE intn r 结点数和根的位置 CTree 如何找双亲结点 带双亲的孩子链表 孩子兄弟表示法 二叉树表示法 实现 用二叉链表作树的存储结构 链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点特点操作容易破坏了树的层次 typedefstructCSNode ElemTypedata structCSNode fch nsib CSNode CSTree 二叉树的存储结构 顺序存储结构链式存储结构 二叉树的顺序存储结构 用一组地址连续的存储单元依次自上而下 自左向右存储完全二叉树上的结点 即将编号为i的结点元素存储在一维数组中下标为i 1的分量中对于一般二叉树 将其每个结点与完全二叉树上的结点相对照 存储在一维数组中的相应分量上 defineMAX TREE SIZE100 二叉树最大结点数typedefTElemTypeSqBiTree MAX TREE SIZE 0号单元存储根结点SqBiTreebt 二叉树的顺序存储结构 1 2 3 4 5 6 7 8 9 10 11 12 完全二叉树 存储为 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 0 bt 二叉树的顺序存储结构 特点仅适用于存储完全二叉树 否则可能存在严重的空间浪费 如最坏情况 深度为k的二叉树 只有k个结点 单支树 需要用2k 1个单元的数组空间来存储 1 2 3 4 存储为 1 2 0 3 0 0 0 1 2 3 4 5 6 0 bt 4 7 二叉树的顺序存储结构 1 2 3 4 存储为 1 0 2 0 0 0 3 1 2 3 4 5 6 0 bt 0 7 0 0 0 0 8 9 10 11 0 0 4 12 13 14 二叉树的链式存储结构 二叉树中的结点设计含两个指针域含三个指针域二叉树的链式存储结构根据不同的结点结构构成不同的链式存储结构二叉链表三叉链表 data lchild rchild data lchild parent rchild data lchild rchild parent 链式存储结构二叉链表 typedefstructBiTNode TElemTypedata structBiTNode lchild rchild BiTNode BiTree BiTreeT 在n个结点的二叉链表中 有n 1个空指针域 三叉链表 typedefstructBiTNode TElemTypedata structBiTNode lchild rchild parent BiTNode BiTree BiTreeT 树与二叉树转换 将树转换成二叉树加线 在兄弟之间加一连线抹线 对每个结点 除了其左孩子外 去除其与其余孩子之间的关系旋转 以树的根结点为轴心 将整树顺时针转45 树转换成的二叉树其右子树一定为空 将二叉树转换成树加线 若p结点是双亲结点的左孩子 则将p的右孩子 右孩子的右孩子 沿分支找到的所有右孩子 都与p的双亲用线连起来抹线 抹掉原二