[工学]数据结构第四章2010.ppt

数据结构 (data structures) 第四章 肖慧青 2010.4 第四章 树 tree §4.1 树的基本概念 概述 树形结构的特点 每个结点最多只有一个直接前驱 每个结点可以有多个直接后继 所以，可以表达更复杂的数据 例：家族成员间的血缘关系 一、树的定义 树是n(n=0)个结点的有穷集合，当n0时， 有且仅有一个称为根的结点; 其余结点可分为m(m0)个互不相交的非空集合T1，T2，…，Tm， 这些集合中的每一个都是一棵树，称为根的子树 说明 （n0） n=1时，树只含一个结点，满足两个条件 所以，任何只含一个结点的集合是一棵树 n1时，须具体判断n个结点集合是否是一棵树 例如：判断老王是否是树 王小一、王小二是树 所以，王一是树 王小三是树 所以，王二是树 王一、王二是树 所以，老王是树 递归判定 下列为非树形结构 说明 根没有直接前驱 对树上任一结点x来说，x是它任一子树的根结点的唯一的直接前驱 二、树的基本概念 结点的度：结点拥有的子树数。 叶子（终端结点）：度为零的结点。 分支结点（非终端结点）：度不为零的结点。 树的度：树内各结点的度的最大值。 双亲(父结点)：若树中结点A是结点B的直接前驱，则称A为B～ 孩子（子结点）：B为A～ 兄弟：双亲相同的结点 子孙：一棵树或子树上的任何结点（不包括根本身）称为根的～ 祖先：若B是A的子孙，则A是B的～ 结点的层数(深度)：根的层数为1，其余结点的层数为双亲的层数加1 树的高度（深度）：一棵树中所有结点层数的最大值 三、树形结构 是一种“分支层次”结构 在实际应用中 树中的一个结点存储实际问题中的一个数据元素 结点间的逻辑关系往往用来表示数据元素间的重要关系 四、树的基本运算 求根 root(t) 求双亲 parent(t,x) 求孩子 child(t,x,i) 建树 create(x,t1,t2, …,tk) k=1 剪枝 delete(t,x,i) §4.2 二叉树 binary tree 一、二叉树的基本概念 定义 二叉树是n(n=0)个结点的有穷集合， 当n0时， 有且仅有一个称为根的结点; 其余结点可分为两个互不相交的集合T1、T2， 它们每一个都是一棵二叉树，分别称为根的左子树和右子树。 二叉树与树的区别 二叉树是一类与树不同的树形结构 二叉树的任一结点都有两棵子树，且有次序关系，分别称为该结点的左孩子和右孩子（可以是空） 二叉树上任一结点的度定义为该结点的孩子数（即非空子树数） 二叉树即使一结点只有一棵非空子树，仍需区别左孩子或右孩子 二叉树的基本形态 二叉树的基本运算 初始化 initiate(bt) 求根 root(bt) 求双亲 parent(bt,x) 求左孩子 lchild(bt,x) 求右孩子 rchild(bt,x) 建树 create(x,lbt,rbt) 剪枝 delleft(bt,x) delright(bt,x) 二、二叉树的性质 1、在二叉树中，第i层的结点数最多为2i-1 ( i≥1) 2、深度为k的二叉树的结点总数最多为 2k-1 (k≥1) 3、对任何一棵二叉树T，如果叶子数为n0，而度为2的结点数为n2，则n0=n2+1 满二叉树：深度为K的二叉树，具有2k-1个结点 完全二叉树：如果在一棵深度为k (k ≥ 1)的满二叉树上，删去第k层上最右边的连续j(0≤j2k-1)个结点，就得到一棵深度为k的～ 4、有n个结点的完全二叉树，其深度[log2 n]下+1 [m]下 取下整，表示不超过m的最大整数 如[3.6]下=3, [3]下=3 同理，取上整 按层编号 将一棵树中的所有n个结点，按从第一层到最大层，每层从左到右的顺序依次标记为1,2, …,n，则可以得到一个足以反映二叉树结构的线性序列 如： 5、如果将一棵有n个结点的完全二叉树按层编号，则对任一编号为i (1≤i≤n)的结点x有： 若 i=1，则结点x是根 若 i1，则x的双亲的编号是 [i/2]下 若 2 in ，则结点x无左孩子 若2 i ≤ n，则其左孩子的编号是2i 若2i+1n ，则结点x无右孩子 若2 i+1 ≤ n,? 则其右孩子 的编号是2 i+1 所以，完全二叉树上结点之间的父子关系可由它们编号之间的关系 来表达。 §4.3 二叉树的存储结构 二叉树通常有两类存储结构： 顺序存储结构 链式存储结构 一、二叉树的链式存储结构 二叉链表 结点形式 则：所有存储