第六章节树和森林.ppt

第六章 树 主要内容 6.1 树的定义和基本术语 6.2 树的链式存储结构 6.3 树的顺序存储结构 6.4 K叉树 6.1 树的概念 6.1.1 树和森林 6.1.2 森林与二叉树的等价转换 6.1.3 树的抽象数据类型 6.1.4 树的周游 树的定义 树的逻辑结构描述 包含n个结点的有穷集合K (n0)，且在K上定义了一个关系R={r}，关系R满足以下条件： 有且仅有一个结点k0∈K，它对于关系r来说没有前驱。结点k0称作树的根 除结点k0外，K中的每个结点对于关系r来说都有且仅有一个前驱 除结点k0外的任何结点k∈K，都存在一个结点序列k0，k1，…，ks，使得k0就是树根，且ks=k，其中有序对ki-1，ki∈R(1≤i≤s)。这样的结点序列称为从根到结点k的一条路径 树结构中的基本概念 若k，k′∈N，则称k是k′的父结点（或称“父母”），而k′则是k的 子结点(或“儿子”、“子女”) 若有序对k，k′及k，k″∈N，则称k′和k″互为兄弟 若有一条由 k到达ks的路径，则称k是ks的祖先，ks是k的子孙 树形结构中，两个结点的有序对，称作连接这两结点的一条边 树结构中的基本概念 没有子树的结点称作树叶或终端结点 非终端结点称为分支结点 一个结点的子树的个数称为度数 根结点的层数为0，其它任何结点的层数等于它的父结点结点的层数加1 树结构中的概念 有序树 在树T中如果子树T1，T2，…，Tm的相对次序是重要的，则称树T为有向有序树，简称有序树。 在有序树中可以称T1是根的第一棵子树，T2是根的第二棵子树，等等 森林与树 森林(forest) 森林是零棵或多棵不相交的树的集合(通常是有序集合)。 自然界的树和森林是不同的概念，而数据结构的树和森林只有微小的差别。删去树根，树就变成森林。加上一个结点作树根，森林就变成树 树形结构的各种表示法 树形结构的各种表示法 树形结构的各种表示法 树形结构的各种表示法 森林与二叉树的等价转换 在树或森林与二叉树之间有一个自然的一一对应的关系。 任何森林都唯一地对应到一棵二叉树；反过来，任何二叉树也都唯一地对应到一个森林。 树所对应的二叉树里 一个结点的左子结点是它在原来树里的第一个子结点 右子结点是它在原来的树里的下一个兄弟 森林到二叉树的等价转换过程 连线：将兄弟结点用线连接起来 切线：保留父结点与其第一个子结点的 连线，将父结点到其他子结点的连 线切掉 旋转：以根为轴，平面向下顺时针方向旋转一 定的角度。旋转只是为了调整画面，使 得转化之后的二叉树看起来比较规整。 森林与二叉树的等价转换 森林到二叉树的等价转换规则 把森林F看作树的有序集合，F=(T1，T2，…，Tn)，对应于F的二叉树B(F)的定义是： 若n=0，则B（F）为空 若n0，则B(F)的根是T1的根W1，B(F)的左子树是B(T11，T12，…，T1m)，其中T11，T12，…，T1m是W1的子树；B(F)的右子树是B(T2，…，Tn) 此定义精确地确定了从森林到二叉树的转换 二叉树到森林的等价转换过程 旋转：以根为轴，平面逆时针方向旋转 补线：若结点x是父结点y的左子结点，则把x的右子结点，右子结点的右子结点，依次类推，直到最右子结点，用连线与y连接起来 删线：去掉所有父结点到右子结点的连线 二叉树到森林的等价转换 设B是一棵二叉树，root是B的根，BL是root的左子树，BR是root的右子树，则对应于B的森林 F(B)的定义是： 若B为空，则F(B)是空的森林。 若B不为空，则F(B)是一棵树T1加上森林F(BR)，其中树T1的根为root，root的子树为F(BL) 树/森林的抽象数据类型 templateclass T class TreeNode { public: TreeNode(const T value);//拷贝构造函数 virtual ~TreeNode(){}; //析构函数 bool isLeaf(); //如果结点是叶，返回true T Value(); //返回结点的值 TreeNodeT* LeftMostChild(); //返回第一个左孩子 TreeNodeT* RightSibling(); //返回右兄弟 树/森林的抽象数据类型 void setValue(const T value); //设置结点的值 /