退栈→t,访问C t-> rchild→t B C ①① t=NUL,表示C的左 DBE EA 子树遍历结束 t=NUL,并且栈S 为空,遍历结束
退栈➔t，访问C， t->rchild➔t A B C D E t=NULL,并且栈S 为空，遍历结束 C A B C D E t=NULL,表示C的左 子树遍历结束 D B E A C
void Midorder(struct binode t) //t为根指针 struct binode*st[ maxing+1];/定义指针栈st[0.. maxing int top=0; //置空栈 d i while(t) //根指针t表示的为非空二叉树 if(top= maxing)exit( OVERFLOW);//栈已满,退出 stL++top]=t; //根指针进栈 t二t→> Ichilo: //t移向左子树 }/循环结束表示以栈顶元素的指向为 //根结点的二叉树的左子树遍历结束 if (top) //为非空栈 tt=stltop--] //弹出根指针 printf("%c",t->data);/访问根结点 t二t→> rchild: //遍历右子树 } while(top|t);/父结点未访问,或右子树未遍历
void Midorder(struct BiTNode *t) //t为根指针 { struct BiTNode *st[maxleng+1];//定义指针栈st[0..maxleng] int top=0； //置空栈 do { while(t) //根指针t表示的为非空二叉树 { if (top==maxleng) exit(OVERFLOW)；//栈已满,退出 st[++top]=t； //根指针进栈 t=t->lchild； //t移向左子树 } //循环结束表示以栈顶元素的指向为 //根结点的二叉树的左子树遍历结束 if (top) //为非空栈 { t=st[top--]； //弹出根指针 printf("%c",t->data)； //访问根结点 t=t->rchild； //遍历右子树 } } while(top||t)； //父结点未访问，或右子树未遍历 }
6.3.7遍历二叉树的应用 例.求二叉树中结点的个数 int preorder (struct BiTNode root) //求二叉树中结点的个数 i int n=O if (root) n=1; //根结点计数 n+-preorder (root->lchild) /递归计算左子树 n+= preorder( root->rchild);//递归计算右子树 return n; maino i int n: //n为计数器,假定二叉树已生成 n= preorder(root);//root为指针,执行 preorder(root,&n) printf("%d",n);//输出n
6.3.7 遍历二叉树的应用 例. 求二叉树中结点的个数 int preorder(struct BiTNode *root) //求二叉树中结点的个数 { int n=0 ; if (root) { n=1； //根结点计数 n+=preorder(root->lchild)； //递归计算左子树 n+=preorder(root->rchild)； //递归计算右子树 } return n; } main() { int n； //n为计数器,假定二叉树已生成 n=preorder(root)；//root为指针,执行preorder(root,&n) printf("%d",n)； //输出n }
例:将二叉数线索化(中序) T的中序序列:B,D,C,E,A,F,G(B roo t NULL TOA oI 二叉树T NULL 1|B|o 四N B ( NULL 0||0 山G 中序线索二叉树链表 T的中序线索二叉树
例：将二叉数线索化（中序）。 T的中序序列：B,D,C,E,A,F,G F A G B D C E 二叉树T F A G B D C E T的中序线索二叉树 NULL NULL 0 A 0 root 中序线索二叉树链表 1 F 0 1 B 0 1 G 1 0 C 0 1 D 1 1 E 1 NULL NULL
结点结构: Child ltag data rtag rchild 0/1 0/1 左小孩左标志结点值右标志右小孩 或前趋 或后继 void creat thread (struct BiTNode *t) //t为根指针 struct binode米st[ maxleng+1],pre=NUL;/前驱结点指针 int top=0; //置空栈 do i while(t) //根指针t表示的为非空二叉树 if(top= maxing)exit( OVERFLOW);//栈已满,退出 st[++top=t //根指针进栈 t二t→> Child: //t移向左子树
结点结构： void creat_thread(struct BiTNode *t) //t为根指针 { struct BiTNode *st[maxleng+1],pre=NULL; //前驱结点指针 int top=0； //置空栈 do { while(t) //根指针t表示的为非空二叉树 { if (top==maxleng) exit(OVERFLOW)；//栈已满,退出 st[++top]=t； //根指针进栈 t=t->lchild； //t移向左子树 } 0/1 0/1 lchild ltag data rtag rchild 左小孩 左标志 结点值 右标志 右小孩 或前趋 或后继