数据结构考研分类复习真题 第六章 树和二叉树 (三)[14]

．设一棵二叉树的结点定义为

struct BinTreeNode{ElemType data; BinTreeNode *leftchild*rightchild;}

现采用输入广义表表示建立二叉树具体规定如下

()树的根结点作为由子树构成的表的表名放在表的最前面

()每个结点的左子树和右子树用逗号隔开若仅有右子树没有左子树逗号不能省略

()在整个广义表输入的结尾加上一个特殊的符号(例如#)表示输入结束

例如对于如图所示的二叉树其广义表表示为A(B(DE(G))C(F))

此算法的基本思路是依次从保存广义表的字符串ls中输入每个字符若遇到的是字母(假设以字母作为结点的值)则表示是结点的值应为它建立一个新的结点并把该结点作为左子女(当k=)或右子女(当k=)链接到其双亲结点上若遇到的是左括号(则表明子表的开始将k置为若遇到的是右括号)则表明子表结束若遇到的是逗号则表示以左子女为根的子树处理完毕接着处理以右子女为根的子树将K置为在算法中使用了一个栈s在进入子表之前将根结点指针进栈以便括号内的子女链接之用在子表处理结束时退栈相关的栈操作如下

MakeEmpty(s) 置空栈 Push(sp) 元素p入栈

Pop(s) 退栈 Top(s)存取栈顶元素的函数

下面给出了建立二叉树的算法其中有个语句缺失请阅读此算法并把缺失的语句补上(每空分)

void CreatBinTree(BinTreeNode *&BTchar ls){

Stack<BinTreeNode*>s; MakeEmpty(s);

BT=NULL; //置空二叉树

BinTreeNode *p;

int k; istream ins(ls) //把串ls定义为输入字符串流对象ins ;

char ch; ins>>ch; //从ins顺序读入一个字符

while (ch != #){ //逐个字符处理直到遇到#为止

switch(ch){

case (: ()______k=; break;

case ): pop(s); break;

case : ()______ break;

default :p=new BinTreeNode; ()_______;p>leftChild=NULL;p>rightChild=NULL;

if(BT==NULL) ()______else if (k==) top(s)>leftChild=p;

else top(s)>rightChild=p;

}

()______; }

}【清华大学 六 (分)】

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []