递归和非递归方式实现二叉树的建立和遍历

递归和非递归方式实现二叉树的建立和遍历2013-05-24

#include<stdio.h> #include<stdlib.h> #define MAXSIZE 20 typedef struct BiTnode{char data;struct BiTnode *lchild,*rchild; }BiTnode,*BiTree; int i = 0; BiTree Create（BiTree t,char s[]） {char ch;ch = s[i++];if（ch == " "）{ t = NULL;}else { if（！（t = （BiTree）malloc（sizeof（BiTnode）））） {printf（"fail to malloc！
"）;exit（0）; } else{t->data = ch;t->lchild = Create（t->lchild,s）;t->rchild = Create（t->rchild,s）; }}return t; } /* void display（BiTree t） {BiTree stack[MAXSIZE],p;int top = -1;if（t）{ p = t; while（top > -1 || p） {while（p）{ stack[++top] = p; p = p->lchild; } if（top > -1）{ p = stack[top--]; printf（"%c ",p->data）; p = p->rchild; } } printf（"
"）;} } /*//* void display（BiTree t） {BiTree stack[MAXSIZE],p;int top = -1;if（t）{ p = t; while（top > -1 || p） {while（p）{printf（"%c ",p->data）;stack[++top] = p; p = p->lchild; } if（top > -1）{ p = stack[top--]; p = p->rchild; } } printf（"
"）;} } *//* void display（BiTree t） {BiTree stack[MAXSIZE], p;int top = -1;if （t）{stack[++top] = t;while （top > -1）{p = stack[top--];printf（"%c ", p->data）;if （p->rchild） { stack[++top] = p->rchild; }if （p->lchild） {stack[++top] = p->lchild; }}printf（"
"）;} }*//* void display（BiTree t） {BiTree m,stack[MAXSIZE];int top = -1;int flag; if（t）{ loop: flag = 1; m = NULL; while（t） {stack[++top] = t;t = t->lchild; } while（flag） {t = stack[top];if（t->rchild == m）{ printf（"%c ",t->data）; top--; m = t;}else{ flag = 0; t = t->rchild;} } if（top>-1）goto loop;}printf（"
"）; } */void display（BiTree t） { BiTree p = t, stack[MAXSIZE];int tag[MAXSIZE]; int top = -1; do {while（p ！= NULL） {stack[++top] = p;tag[top] = 0;p = p->lchild;} if（top > -1） {if（！tag[top]） { p = stack[top];p = p->rchild;tag[top] = 1;}else{printf（"%c ", stack[top--]->data）;}}}while（（p ！= NULL）||（top > -1））;printf（"
"）; } /*void display（BiTree t） {if（t）{ printf（"%c ",t->data）; display（t->lchild）; display（t->rchild）锛？} }*//*void display（BiTree t） {if（t）{ display（t->lchild）; printf（"%c ",t->data）; display（t->rchild）锛？} }*/ /*void display（BiTree t） {if（t）{display（t->lchild）; display（t->rchild）; printf（"%c ",t->data）;} }*/int main（int argc,char *argv[]） {BiTree t;char s[] = "abcde fg";t = Create（t,s）;display（t）;return 0; }

本文出自 “驿落黄昏” 博客，请务必保留此出处 http://yiluohuanghun.blog.51cto.com/3407300/631727