填空题
阅读下列说明和C函数代码,将应填入
(n) 处的字句写在对应栏内。
[说明]
对二叉树进行遍历是二叉树的一个基本运算。遍历是指按某种策略访问二又树的每个结点,且每个结点仅访问一次的过程。函数InOrder()借助栈实现二叉树的非递归中序遍历运算。
设二叉树采用二叉链表存储,结点类型定义如下:
typedef struct BtNode
ElemType data; /*结点的数据域,ElemType的具体定义省略*/
struct BtNode *lchiid,*rchiid; /*结点的左、右孩子指针域*/
BtNode,*BTree;
在函数InOrderO中,用栈暂存二叉树中各个结点的指针,并将栈表示为不含头结点的单向链表(简称链栈),其结点类型定义如下:
typedef struct StNode /*链栈的结点类型*/
BTree elem; /*栈中的元素是指向二叉链表结点的指针*/
Struct StNode *link;
StNode;
假设从栈顶到栈底的元素为e
n,e
n-1,…,e
1,则不含头结点的链栈示意图如图21-11所示。