实现二叉树的创建(先序)、递归及非递归的先、中、后序遍历
请按先序遍历输入二叉树元素(每个结点一个字符,空结点为'='): ABD==E==CF==G== 先序递归遍历: A B D E C F G 中序递归遍历: D B E A F C G 后序递归遍历: D E B F G C A 层序递归遍历: ABCDEFG 先序非递归遍历: A B D E C F G 中序非递归遍历: D B E A F C G 后序非递归遍历: D E B F G C A 深度: 3 请按任意键继续. . .
1 #include<stdio.h> 2 #include<stdlib.h> 3 4 #define OK 1 5 #define ERROR 0 6 #define TRUE 1 7 #define FALSE 0 8 #define OVERFLOW -1 9 10 #define STACK_INIT_SIZE 100 11 #define STACKINCREMENT 10 12 13 typedef int Status; 14 15 typedef char ElemType; 16 typedef struct BTNode 17 { 18 ElemType data; 19 struct BTNode *leftChild; 20 struct BTNode *rightChild; 21 }BTNode, *BinTree; 22 23 typedef BinTree SElemType; 24 25 typedef struct{//栈结构定义 26 SElemType *base; 27 SElemType *top; 28 int stacksize; 29 }SqStack; 30 31 BinTree CreateBinTree(BinTree T); 32 Status Visit(ElemType e); 33 Status Depth(BinTree T); 34 Status PreOrderRecursionTraverse(BinTree T, Status (*Visit)(ElemType e)); 35 Status InOrderRecursionTraverse(BinTree T, Status (*Visit)(ElemType e)); 36 Status PostOrderRecursionTraverse(BinTree T, Status (*Visit)(ElemType e)); 37 Status LevelOrderRecursionTraverse(BinTree T, Status (*Visit)(ElemType e)); 38 39 //定义栈的相关操作 40 Status InitStack(SqStack *S); 41 Status DestroyStack(SqStack *S); 42 Status ClearStack(SqStack *S); 43 Status StackEmpty(SqStack S); 44 int StackLength(SqStack S); 45 Status GetTop(SqStack S,SElemType *e); 46 Status Push(SqStack *S,SElemType e); 47 Status Pop(SqStack *S,SElemType *e); 48 Status StackTraverse(const SqStack *S); 49 50 Status PreOrderNoneRecursionTraverse(BinTree T, Status (*Visit)(ElemType e)); 51 Status InOrderNoneRecursionTraverse(BinTree T, Status (*Visit)(ElemType e)); 52 Status PostOrderNoneRecursionTraverse(BinTree T, Status (*Visit)(ElemType e)); 53 54 int main() 55 { 56 int depth; 57 BinTree Tree = NULL; 58 Status(*visit)(ElemType e) = Visit; 59 printf_s("请按先序遍历输入二叉树元素(每个结点一个字符,空结点为'='): "); 60 Tree = CreateBinTree(Tree); 61 62 printf_s(" 先序递归遍历: "); 63 PreOrderRecursionTraverse(Tree,visit); 64 printf_s(" 中序递归遍历: "); 65 InOrderRecursionTraverse(Tree,visit); 66 printf_s(" 后序递归遍历: "); 67 PostOrderRecursionTraverse(Tree,visit); 68 printf_s(" 层序递归遍历: "); 69 LevelOrderRecursionTraverse(Tree,visit); 70 71 printf_s(" 先序非递归遍历: "); 72 PreOrderNoneRecursionTraverse(Tree,visit); 73 printf_s(" 中序非递归遍历: "); 74 InOrderNoneRecursionTraverse(Tree,visit); 75 printf_s(" 后序非递归遍历: "); 76 PostOrderNoneRecursionTraverse(Tree,visit); 77 78 printf_s(" 深度: "); 79 depth = Depth(Tree); 80 printf_s("%d ", depth); 81 system("pause"); 82 return 0; 83 } 84 85 //创建二叉树 86 BinTree CreateBinTree(BinTree T) 87 { 88 char ch; 89 scanf_s("%c", &ch); 90 if (ch == '=') 91 { 92 T = NULL; 93 } 94 else 95 { 96 if (!(T=(BTNode *) malloc(sizeof(BTNode)))) 97 { 98 exit(OVERFLOW); 99 } 100 T->data = ch; //生成根结点 101 T->leftChild = CreateBinTree(T->leftChild); 102 T->rightChild = CreateBinTree(T->rightChild); 103 } 104 return T; 105 } 106 107 //访问二叉树 108 Status Visit(ElemType e) 109 { 110 if (e == '