C 二叉树创建、前序遍历、中序遍历、后序遍历 的 递归与非递归实现 以及 层次遍历

1、二叉树创建、前序遍历、中序遍历、后序遍历的递归与非递归实现以及 层次遍 历二叉树的创建：#include stdio.h”typedef char ElemType;#define MAXNUM 150/*二叉树结点定义*/typedef struct BTNode(ElemType data;struct BTNode *lchild;struct BTNode *rchild; BTNode;/*辅助的二叉树索引数组*/BTNode *pMAXNUM+1;/*根据用户输入创建二叉树*/*二叉树结点信息：数据域，以及在完全二叉树中的索引值*/BTNode *Create_BiTree(voi

2、d)(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;pi = s;if ( i = 1 )t = s;elsej = i/2;if ( i%2 = 0 )pj-lchild = s;else心-rchild=s;printf(n enter i, ch :);sca

3、nf (%d,%c, &i, &ch);return t;BTNode* t;t = Create_BiTree ();/*preorder(t);printf( preordern);preorder_recursive(t);printf( preorder_recursiven);Inorder(t);printf( Inordern);Inorder_recursive1(t);printf( Inorder_recursive1n);Inorder_recursive2(t);printf( Inorder_recursive2n);Postorder(t);printf( Post

4、ordern);Postorder_recursive(t);printf( Postorder_recursiven);LevelOrder(t);printf( LevelOrdern);*/getchar();getchar();return 0;二叉树的前序遍历，递归、非递归的实现:/*前序遍历的递归实现*/void preorder (BTNode *bt)(if (bt)(printf (%c , bt-data);preorder(bt-lchild);preorder(bt-rchild);/*前序遍历的非递归实现*/void preorder_recursive(BTNode

5、 *bt)(BTNode* p;BTNode* s MAXNUM+1; /* 辅助的模拟栈 */ int top;p=bt;top=-1;while(p|top != -1)(if(p)(printf (%c , p-data);+top;二叉树的中序遍历，递归、非递归的实现:/*中序遍历的递归实现*/void Inorder(BTNode *bt)(if (bt)(Inorder(bt-lchild);printf (%c ”, bt-data); /* 访问根结点 */ Inorder(bt-rchild); /* inorder */*中序遍历的非递归实现*/void Inorder_r

6、ecursive1(BTNode *bt )(BTNode* p,*sMAXNUM+1;int top;p=bt;top=-1;m同)if (p+top;s top=p;p=p-lchild ; /*p移向左孩子*/else /*栈非空*/p=s top;top;printf (%c ,p-data) p=p-rchild;“递void Inorder_recursive2(BTNode *bt)BTNode* p,*sMAXNUM+1;int top;p=bt;top=-1;if (p & p-lchild)+top;s top = p;Ip = p-lchild;elseif (p)pri

7、ntf (%c , p-data);if (p & p-rchild )p = p-rchild;else if ( top = 0)p = s top;top;printf (%c , p-data);p = p-rchild;else二叉树的后序遍历，递归、非递归的实现:/*后序遍历的递归实现*/void Postorder(BTNode *bt)(if (bt)(Postorder(bt-lchild);Postorder(bt-rchild);printf (%c , bt-data);/*后序遍历的非递归实现*/void Postorder_recursive(BTNode *pt)

8、(BTNode *sMAXNUM+1;int top = -1;BTNode *p = pt;BTNode *pre = NULL;while ( p | top != -1 )(if (p )(+top;s top = p;p = p-lchild;pre = p;else(p = s top/ -top;if ( p-rchild = NULL | p-rchild = pre )p = s top;-top;printf(%c , p-data);pre =p;p = NULL;elsep = p-rchild;层次遍历：/*层次遍历二叉树*/void LevelOrder (BTNode *bt)(BTNode* queue 100;int front=0,rear=0;if (bt=NULL)return;queuerear=bt;rear+;do(printf (%c , queuefront-data);/*访问队首结点的数据域*/if (queuefront-lchild!=NULL)/*将队首结点的左