答案及解析：[问答题]对二叉树进行遍历是二叉树的一个基本运算。遍历是指按某种策略访问二叉树的每个结点，且每个结点仅访问一次的过程。函数InOrder（　　）借助栈实现二叉树的非递归中序遍历运算。设二叉树采用二叉链表存储，结

问题：

[问答题] 对二叉树进行遍历是二叉树的一个基本运算。遍历是指按某种策略访问二叉树的每个结点，且每个结点仅访问一次的过程。函数InOrder（　　）借助栈实现二叉树的非递归中序遍历运算。设二叉树采用二叉链表存储，结点类型定义如下：typedef?struct?BtNode{ElemType data;/*结点的数据域，ElemType的具体定义省略*/struct?BtNode*lchild，*rchild;/*结点的左、右孩子指针域*/}BtNode，*BTree;在函数InOrder（　　）中，用栈暂存二叉树中各个结点的指针，并将栈表示为不含头结点的单向链表（简称链栈），其结点类型定义如下：typedef?struct?StNode{/*链栈的结点类型*/BTree?elem;/*栈中的元素是指向二叉链表结点的指针*/struct?StNode*link;}StNode;假设从栈顶到栈底的元素为en、en-1、…、e1，则不含头结点的链栈示意图如图5-1所示。中级软件设计师,历年真题,2009年上半年（下午）《软件设计师》真题

【C函数】int?InOrder(BTree root)/*实现二叉树的非递归中序遍历*/{BTree ptr;/*ptr用于指向二叉树中的节点*/StNode*q;/*q暂存链栈中新创建或待删除的节点指针*/StNode*stacktop=NULL;/*初始化空栈的栈顶指针stacktop*/ptr=root;/*ptr指向二叉树的根节点*/while((1)||stacktop!=NULL){while(ptr!=NULL){q=(StNode*)malloc(sizeof(StNode));if(q==NULL)return-1q->elem=ptr;（2）;stacktop=q/*stacktop指向新的栈顶*/ptr=(3);/*进入左子树*/}q=stacktop;(4);/*栈顶元素出栈*/visit(q);/*visit是访问节点的函数，其具体定义省略*/ptr=(5);/*进入右子树*/free(q);/*释放原栈顶元素的节点空间*/}return 0;}/*InOrder*/

Tags：软件水平考试中级软件设计师试题及答案

答案解析：

╋纠错

您可能感兴趣的问题