二叉树的存储结构为： 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;}
举一反三
- 二叉树的非递归遍历是通过将递归工作栈自己进行管理来设计的，下列中根序遍历的非递归算法中（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()
- 写出下面程序的运行结果。 #include <iostream> using namespace std; class Base { public: void Who( ){cout<<"class Base"<<endl;} }; class Derived1:public Base { public: void Who( ){cout<<"class Derived1"<<endl;} }; class Derived2:public Base { public: void Who( ){cout<<"class Derived2"<<endl;} }; int main( ) { Base obj1,*p; Derived1 obj2; Derived2 obj3; p=& obj1; p->Who(); p=& obj2; p->Who(); p=& obj3; p->Who(); obj2.Who(); obj3.Who(); return 0; } ______ ______ ______ ______ ______
- 以下程序是二叉链表树中序遍历的非递归算法,请填空使之完成(注意:语句中不要留空格)。二叉树链表的结点类型的定义如下: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); ____; } /*栈顶元素出栈*/}
- 下面的程序段，实现对一棵二叉树的先根遍历。 public void preorder(BinaryNode p) // 先根次序遍历以p结点为根的子树，递归方法 { if (p != null) // 若二叉树不空 { System.out.print(p.data.toString() + " "); // 根先访问 ; // 遍历p的左子树，递归调用 ; // 遍历p的右子树，递归调用 } }