以下程序是二叉链表树中序遍历的非递归算法,请填空使之完成(注意:语句中不要留空格)。二叉树链表的结点类型的定义如下:typedef struct node { char data; struct node *lchild,*rchild;}*bitree;void visit(bitree bt) /*bt为根结点的指针*/ {bitree p; p=bt; initstack(s); /*初始化栈s为空栈*/ while( p || !empty(s)) /*栈s不为空*/ if(p) { push (s,p);/* p 入栈*/ (1)______; } else { p=pop(s);/*栈顶元素出栈*/ printf(“%c”,p->data); p=p->rchild; }}
举一反三
- 以下程序是二叉链表树中序遍历的非递归算法,请填空使之完善。二叉树链表的结点类型的定义如下:typedef struct node /*C语言/{char data; struct node *lchild,*rchild;}*bitree;void vst(bitree bt) /*bt为根结点的指针*/{ bitree p; p=bt; initstack(s); /*初始化栈s为空栈*/while(p || !empty(s)) /*栈s不为空*/if(p) { push (s,p);____; } /*P入栈*/else { p=pop(s); printf(“%c”,p->;data); ____; } /*栈顶元素出栈*/}
- 二叉树中序遍历的非递归算法如下所示。请填写算法中下划线的空白处。[br][/br]Status Inorder(BiTree T){[br][/br] InitStack(s);push(s，T); While ( (1)){[br][/br] While (gettop(s，p)&&p) push (s， (2)); pop(s，p); if(!StackEmpty(s)){ pop(s，p);printf( (3)); push(s， (4));[br][/br] }//if[br][/br] }//while[br][/br] return ok;[br][/br]}//Inorder[br][/br]注：[br][/br]InitStack(s);初始化一个栈s；[br][/br]push(s，p);将所指向的结点进s栈[br][/br]；pop(s，p);s栈顶元素出栈；[br][/br]gettop(s，p);取s栈顶元素；[br][/br]StackEmpty(s);判栈s是否为空。
- 若已建立以下链表结构，指针p、s分别指向如图所示结点。 则不能将s所指结点插入到链表末尾的语句组是______。 A: p=p->next; s ->next=p; p->next=s; B: s ->next='\0'; p=p->next; p->next=s; C: p=p->next; s ->next=p->next; p->next=s; D: p=(*p).next; (*s ).next=(*p).next; (*p).next=s;
- 二叉树的非递归遍历是通过将递归工作栈自己进行管理来设计的，下列中根序遍历的非递归算法中（1）的正确判断语句应该是（ ）。template void BinaryTree :: InOrderTraverse () { stack S; BiTreeNode * p; S.makeEmpty( ); p = root; //初始化 do{ while ( p ) { S.push(p); p = p→leftChild; } if ( !S.empty( ) ) { //栈非空 p = S.top( ); S.pop( ); //退栈 cout<< p→data; //访问根结点 p = p→rightChild; //向右链走 } } while ( （1） );} A: p ！= NULL B: !empty( ) C: p!= NULL || !empty() D: p!= NULL && !empty()
- 二叉树的存储结构为： structBTreeNode{ElemTypedata;BTreeNode* lchild;BTreeNode* rchild;};请写出其非递归的中序遍历算法voidInOrderWithoutRecursion(BTreeNode* root) {if (root == NULL) return;BTNode* p = root;stack<BTNode*> s;while (!s.empty() || p) {//入栈中，左子树的左子树在入栈while (p) {_________________;__________________;}if (!s.empty()){//当p为空时，说明根和左子树都遍历完，该进入右子树 ________________;cout<< ”“<< p->data; _________________;}}cout<<endl;}