二叉树创建、前序遍历、中序遍历、后序遍历 的 递归与非递归实现 以及 层次遍历 二叉树的创建： #include "stdio.h" typedef char ElemType; #define MAXNUM 150 /* 二叉树结点定义 */ typedef struct BTNode { ElemType data; /* data field */ struct BTNode *lchild; struct BTNode *rchild; } BTNode; /* 辅助的二叉树索引数组 */ BTNode *p[MAXNUM+1]; /* 根据用户输入创建二叉树 */ /* 二叉树结点信息：数据域，以及在完全二叉树中的索引值 */ BTNode *Create_BiTree(void) { BTNode* t = NULL; int i; int j; char ch; printf("\n enter i, ch :"); scanf("%d,%c", &i, &ch); while (i != 0 && ch != '#' ) { BTNode* s = (BTNode*)malloc(sizeof(BTNode)); s->data = ch; s->lchild = s->rchild = NULL; p[i] = s; if ( i == 1 ) t = s; else { j = i/2; if ( i%2 == 0 ) p[j]->lchild = s; else p[j]->rchild = s; } printf("\n enter i, ch :"); scanf("%d,%c", &i, &ch); } return t; } int main(void) { BTNode* t; t = Create_BiTree(); /* preorder(t); printf(" preorder\n"); preorder_recursive(t); printf(" preorder_recursive\n"); Inorder(t); printf(" Inorder\n"); Inorder_recursive1(t); printf(" Inorder_recursive1\n"); Inorder_recursive2(t); printf(" Inorder_recursive2\n"); Postorder(t); printf(" Postorder\n"); Postorder_recursive(t); printf(" Postorder_recursive\n"); LevelOrder(t); printf(" LevelOrder\n"); */ getchar(); getchar(); return 0; } 二叉树的 前序遍历，递归、非递归的实现： /* 前序遍历的递归实现 */ void preorder(BTNode *bt) { if (bt) { printf("%c ",bt->data); preorder(bt->lchild); preorder(bt->rchild); } } /* 前序遍历的非递归实现 */ void preorder_recursive(BTNode *bt) { BTNode* p; BTNode* s[MAXNUM+1]; /* 辅助的模拟栈 */ int top; p=bt; top=-1; while(p||top != -1) { if(p) { printf("%c ",p->data); ++top; s[top]=p; p=p->lchild ; } /*p移向左孩子*/ else /*栈非空*/ { p=s[top]; --top; p=p->rchild; } } }...
