C 二叉樹創(chuàng)建、前序遍歷、中序遍歷、后序遍歷 的 遞歸與非遞歸實(shí)現(xiàn) 以及 層次遍歷

1、二叉樹創(chuàng)建、前序遍歷、中序遍歷、后序遍歷的遞歸與非遞歸實(shí)現(xiàn)以及 層次遍 歷二叉樹的創(chuàng)建：#include stdio.h”typedef char ElemType;#define MAXNUM 150/*二叉樹結(jié)點(diǎn)定義*/typedef struct BTNode(ElemType data;struct BTNode *lchild;struct BTNode *rchild; BTNode;/*輔助的二叉樹索引數(shù)組*/BTNode *pMAXNUM+1;/*根據(jù)用戶輸入創(chuàng)建二叉樹*/*二叉樹結(jié)點(diǎn)信息：數(shù)據(jù)域，以及在完全二叉樹中的索引值*/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;二叉樹的前序遍歷，遞歸、非遞歸的實(shí)現(xiàn):/*前序遍歷的遞歸實(shí)現(xiàn)*/void preorder (BTNode *bt)(if (bt)(printf (%c , bt-data);preorder(bt-lchild);preorder(bt-rchild);/*前序遍歷的非遞歸實(shí)現(xiàn)*/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;二叉樹的中序遍歷，遞歸、非遞歸的實(shí)現(xiàn):/*中序遍歷的遞歸實(shí)現(xiàn)*/void Inorder(BTNode *bt)(if (bt)(Inorder(bt-lchild);printf (%c ”, bt-data); /* 訪問根結(jié)點(diǎn) */ Inorder(bt-rchild); /* inorder */*中序遍歷的非遞歸實(shí)現(xiàn)*/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二叉樹的后序遍歷，遞歸、非遞歸的實(shí)現(xiàn):/*后序遍歷的遞歸實(shí)現(xiàn)*/void Postorder(BTNode *bt)(if (bt)(Postorder(bt-lchild);Postorder(bt-rchild);printf (%c , bt-data);/*后序遍歷的非遞歸實(shí)現(xiàn)*/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);/*訪問隊(duì)首結(jié)點(diǎn)的數(shù)據(jù)域*/if (queuefront-lchild!=NULL)/*將隊(duì)首結(jié)點(diǎn)的左