第六章 西北大学树和二叉树

为空集,则为空树。若D中仅含有一个数据元素,则R为空集,否则R={H},H是如下的二元关系:(1) 在D中存在唯一的称为根的数据元素root,它在关系H下没有前驱。(2) 除root以外,D中每个结点在关系H下都有且仅有一个前驱。基本操作:⑴InitTree(Tree):将Tree初始化为一棵空树。(2) DestoryTree(Tree):销毁树Tree。(3) CreateTree(Tree):创建树Tree。(4) TreeEmpty(Tree):若Tree为空,则返回TRUE,否则返回FALSE。(5) Root(Tree):返回树Tree的根。(6) Parent(Tree,x):树Tree存在,x是Tree中的某个结点。若x为非根结点,则返回它的双亲,否则返回“空”。(7) FirstChild(Tree,x):树Tree存在,x是Tree中的某个结点。若x为非叶子结点,则返回它的第一个孩子结点,否则返回“空”。(8) NextSibling(Tree,x):树Tree存在,x是Tree中的某个结点。若x不是其双亲的最后一个孩子结点,则返回x后面的下一个兄弟结点,否则返回“空”。基本操作:(9) InsertChild(Tree,p,Child):树Tree存在,p指向Tree中某个结点,非空树Child与Tree不相交。将Child插入Tree中,做p所指向结点的子树。(10) DeleteChild(Tree,p,i):树Tree存在,p指向Tree中某个结点,1≤i≤d,d为p所指向结点的度。删除Tree中p所指向结点的第i棵子树。(11) TraverseTree(Tree,Visit()):树Tree存在,Visit()是对结点进行访问的函数。按照某种次序对树Tree的每个结点调用Visit()函数访问一次且最多一次。若Visit()失败,则操作失败。