第五章树.pptVIP

第五章 树 任课教员：张 铭 /mzhang/DS/ mzhang@ 北京大学信息科学与技术学院 网络与信息系统研究所 ?版权所有，转载或翻印必究 主要内容 5.1 树的概念 5.2 树的链式存储 5.3 树的顺序存储 5.4 K叉树 5.1 树的概念 5.1.1 树和森林 5.1.2 森林与二叉树的等价转换 5.1.3 树的抽象数据类型 5.1.4 树的周游 树的逻辑结构 包含n个结点的有穷集合K (n0)，且在K上定义了一个关系N，关系N满足以下条件： 有且仅有一个结点k0∈K，它对于关系N来说没有前驱。结点k0称作树的根 除结点k0外，K中的每个结点对于关系N来说都有且仅有一个前驱 除结点k0外的任何结点k∈K，都存在一个结点序列k0，k1，…，ks，使得k0就是树根，且ks=k，其中有序对ki-1，ki∈N(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) 此定义精确地确定了从森林到二叉树的转换 森林到二叉树的等价转换 设B是一棵二叉树，rt是B的根，L是rt的左子树，R是rt的右子树，则对应于B的森林 F(B)的定义是： 若B为空，则F(B)是空的森林。 若B不为空，则F(B)是一棵树T1加上森林F(R)，其中树T1的根为rt，rt的子树为F(L) 树/森林的抽象数据类型 templateclass T class TreeNode { public: TreeNode(const T);//拷贝构造函数 virtual ~TreeNode(){}; //析构函数 bool isLeaf(); //如果结点是叶，返回true T Value(); //返回结点的值 TreeNodeT* LeftMostChild(); //返回第一个左孩子 TreeNodeT* RightSibling(); //返回右兄弟 树/森林的抽象数据类型 void setValue(T); //设置结点的值 //设置左子结点 void setChild(TreeNodeT* pointer); //设置右兄弟 void setSibling(TreeNodeT* pointer); //以第一个左子结点身份插入结点 void InsertFirst(TreeNodeT* node); //以右兄弟的身份插入结点 void InsertNext(TreeNodeT* node); }; 树/森林的抽象数据类型 template class T class Tree { public: Tree(); //构造函数