《数据结构(C语言版)》 第07章_二叉树.pptVIP

第7章　二叉树 2、 二叉树中序遍历的非递归实现 中序遍历一棵非空树t时 ，首先应该进入t的左子树访问，此时由于t的根结点及右子树尚未访问，因此必须将t保存起来，放入栈中，以便访问完其左子树后，从栈中取出t，进行其根结点及右子树的访问；对t的左子树和右子树的遍历也是如此。在整个二叉树中序遍历的过程中，程序要做的工作始终分成两个部分：当前正在处理的树（子树）和保存在栈中待处理的部分，只有这两部分的工作均完成后，程序方能结束。   void inorder1(bintree t)  { seqstack s; s.top=-1; while((t!=NULL) || (s.top!=-1)) { while (t) { push(s,t); t=t-lchild; } if (s.top!=-1) { t=pop(s); printf(%c ,t-data); t=t-rchild; } } } 3 、二叉树后序遍历的非递归实现  后序遍历一棵非空树t时，首先应该进入t的左子树访问，此时由于t的右子树及根结点尚未访问，因此必须将t保存在栈中，以便访问完其左子树后，从栈中取出t，进行其右子树及根结点的访问。值得注意的是，当一个元素位于栈顶即将被处理时，其左子树的访问一定已经完成，如果其右子树尚未遍历，接下来应该进入其右子树的访问，而此时该栈顶元素是不能出栈的，因为其根结点还未被访问；只有等到其右子树也访问完成后，该栈顶元素才能出栈，并输出其根结点的值。因此一个元素位于栈顶时，必须设法识别其右子树是否已被访问。 解决的方法为：使用seqstack类型中的数组tag, 用于标识栈中每个元素的状态： ? 每个元素刚进栈时，其tag值初始化为0； ? 当某一元素位于栈顶即将被处理时： （1）如果其tag值为0，意味着其右子树尚未访问， 于是将其右子树作为当前处理的对象，此时 该栈顶元素仍应该保留在栈中，并将其tag的 值改为1； （2）如果其tag值为1，意味着其右子树已被访问，  接下来应该访问其根结点，并将其出栈。 在整个二叉树后序遍历的过程中，程序要做的工作始终分成两个部分：当前正在处理的树（子树）和保存在栈中待处理的部分。只有这两部分的工作均完成后，程序方能结束。 void postorder1(bintree t)  { seqstack s; s.top=-1; while ((t)||(s.top!=-1)) { while (t) { s.top++; s.data[s.top]=t; s.tag[s.top]=0; t=t-lchild; }  while ((s.top-1) (s.tag[s.top]==1)) { t=s.data[s.top]; printf(%c ,t-data); s.top--; } if (s.top-1) { t=s.data[s.top]; s.tag[s.top]=1; t=t-rchild; } else t=NULL; } } 7．5 二叉树其它运算的实现  由于二叉树本身的定义是递归的，因此关于二叉树的许多问题或运算采用递归方式实现非常地简单和自然。1、二叉树的查找locate(t,x) bintree locate(bintree t, datatype x)  { bintree p; if (t==NULL) return NULL; else if (t-data==x) return t; el