二叉树先序非递归创建及先序中序后序非递归遍历

#include<stdio.h> #include<stdlib.h> #include<iostream> using namespace std; #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -2 #define STACKINCRMENT 10 typedef struct BiTNode { char data; struct BiTNode *lchild, *rchild;//左右孩子 }BiTNode, *BiTree; typedef struct { BiTree *base; BiTree *top; int stacksize; } Sqstack; int nodenum = 0; int InSqstack(Sqstack &S) { S.base = (BiTree *)malloc(STACKINCRMENT * sizeof(BiTNode)); if (!S.base)exit(OVERFLOW); S.top = S.base; S.stacksize = STACKINCRMENT; return OK; } int GetTop(Sqstack S,BiTree &e) { if (S.top == S.base)return ERROR; e =*(S.top - 1); return OK; } int Push(Sqstack &S, BiTree e) { if (S.top - S.base >= S.stacksize) { S.base = (BiTree*)realloc(S.base, (S.stacksize + STACKINCRMENT) * sizeof(BiTNode)); if (!S.base)exit(OVERFLOW); S.top = S.base + S.stacksize; S.stacksize += STACKINCRMENT; } *(S.top++) = e; return OK; } int Pop(Sqstack &S, BiTree &e) { if (S.top == S.base)return ERROR; e = *(--S.top); return OK; } int Empty(Sqstack S) { if (S.top == S.base) return OK; else return ERROR; } typedef struct QNode { BiTree data; struct QNode *next; }QNode, *QueuePtr; typedef struct { QueuePtr front; QueuePtr rear; }LinkQueue;//队列typedef struct QNode //队列的相关函数 int InitQueue(LinkQueue &Q) { Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode)); if (!Q.front) exit(OVERFLOW); Q.front->next = NULL; return OK; } int QueueEmpty(LinkQueue Q) { if (Q.front == Q.rear) return TRUE; else return FALSE; } int EnQueue(LinkQueue &Q, BiTree e) { QueuePtr p; p = (QueuePtr)malloc(sizeof(QNode)); if (!p) exit(OVERFLOW); p->data = e; p->next = NULL; Q.rear->next = p; Q.rear = p; return OK; } int DeQueue(LinkQueue &Q, BiTree &e) { QueuePtr p; if (Q.front == Q.rear) return ERROR; p = Q.front->next; e = p->data; Q.front->next = p->next; if (Q.rear == p) Q.rear = Q.front; free(p); return OK; } int QueueLength(LinkQueue Q) { QueuePtr p; int n = 0; p = Q.front; while (p != Q.rear) { n++; p = p->next; } return n; } int GetHead(LinkQueue Q, BiTree &e) { //若队列不空，则用e返回Q的队头元素，并返回OK，否则返回ERROR QueuePtr p; if (Q.front == Q.rear) return ERROR; p = Q.front->next; e = p->data; return OK; } int CreateBiTree(BiTree &T) { Sqstack S; InSqstack(S); T = NULL; char ch[20]; int i = 0; BiTree R = T, p, pre; cin >> ch; if (Empty(S) && ch[i] == '#')//栈空且输入为#时创建完毕 return OK; do { if (ch[i] != '#')//输入不为空 { p = (BiTree)malloc(sizeof(BiTree)); p->data = ch[i]; p->lchild = NULL; p->rchild = NULL; if (Empty(S))//栈空，创建根节点 { T = p; R = p; pre = p; Push(S, p);//将节点入栈 } else //栈不空，创建子节点 { GetTop(S, R); if (R->lchild != pre)//创建左孩子并将当前元素入栈 { R->lchild = p; pre = R->lchild; Push(S, p); } else if (R->lchild == pre)//创建右孩子,出栈 栈顶元素，pre指向上一节点的左节点（左节点已创建完毕）右孩子入栈 { R->rchild = p; Pop(S, R); Push(S, p); pre = p; R = p; } } } else if (ch[i] == '#') { GetTop(S, R); if (R->lchild != pre)pre = R->lchild;// else { Pop(S, R); if (!Empty(S)) { GetTop(S, R); pre = R->lchild; } }//左右节点创建完毕，出栈 } i++; } while (!Empty(S)); return OK; } void PreOrderTraverse(BiTree T) { Sqstack S; BiTree p; InSqstack(S); if (T == NULL)printf("the tree is empyt"); while (T != NULL) //访问当前节点及其全部左子树 { printf("%c", T->data); Push(S, T); T = T->lchild; } while (!Empty(S)) { Pop(S, p);//取得栈顶元素的右子树 p = p->rchild; while (NULL != p)//同样访问当前节点及其全部左子树 { printf("%c", p->data); Push(S, p); p = p->lchild; } } } void inOrderTraverse(BiTree T) { Sqstack S; BiTree q; InSqstack(S); if(NULL==T)printf("the tree is empyt"); q = T; while ((NULL != q) || !Empty(S)) { if(q) { Push(S, q); q = q->lchild; } else { Pop(S, q); printf("%c", q->data); q = q->rchild; } } } void PostOrderTraverse(BiTree T) { if(T==NULL) printf("the tree is empyt"); Sqstack S; InSqstack(S); BiTree pre,pc;//pre上次访问节点，pc当前访问节点 pc = T; pre = NULL; while (pc) { Push(S, pc); pc = pc->lchild; } while (!Empty(S)) { Pop(S, pc); if(pc->rchild==NULL||pc->rchild==pre) { printf("%c", pc->data); pre = pc; } else { Push(S,pc); pc = pc->rchild; while (pc) { Push(S,pc); pc = pc->lchild; } } } } int NodeCount(BiTree T) { Sqstack S; BiTree p; InSqstack(S); Push(S, T); while (!Empty(S)) { while (GetTop(S, p) && p) { nodenum++; Push(S, p->lchild); } Pop(S, p); if (!Empty(S)) { Pop(S, p); Push(S, p->rchild); } } return OK; } int LeafCount(BiTree T,int &count) { //利用先序遍历思路求叶子结点数 Sqstack S; BiTree p; InSqstack(S); Push(S, T); while (!Empty(S)) { while (GetTop(S, p) && p)Push(S, p->lchild); Pop(S, p); if (!Empty(S)) { Pop(S, p); if (p->lchild == NULL&&p->rchild == NULL) { printf("%c", p->data); ++count; } Push(S, p->rchild); } } return OK; } int ExchangeBiTree(BiTree &T) { //利用层序遍历思路交换 BiTree p, temp; LinkQueue Q; InitQueue(Q); if (T == NULL)return OK; EnQueue(Q, T); while (!QueueEmpty(Q)) { DeQueue(Q, p); if (p->lchild || p->rchild) { temp = p->lchild; p->lchild = p->rchild; p->rchild = temp; } if (p->lchild)EnQueue(Q, p->lchild); if (p->rchild)EnQueue(Q, p->rchild); } return OK; } int LevelOrderTraverse(BiTree T) { //层序非递归 BiTree p; LinkQueue Q; InitQueue(Q); if (T == NULL)return OK; EnQueue(Q, T); while (!QueueEmpty(Q)) { DeQueue(Q, p); if (!(printf("%c", p->data)))return ERROR; if (p->lchild)EnQueue(Q, p->lchild); if (p->rchild)EnQueue(Q, p->rchild); } return OK; } int Depth(BiTree T) { int depth[2] = { 0,0 }; if (T == NULL) printf("the tree is empyt"); Sqstack S; InSqstack(S); BiTree pre, pc;//pre上次访问节点，pc当前访问节点 pc = T; pre = NULL; while (pc) { Push(S, pc); pc = pc->lchild; } while (!Empty(S)) { Pop(S, pc); if (pc->rchild == NULL || pc->rchild == pre) { depth[0] = S.top - S.base; depth[1]= depth[1]>depth[0] ? depth[1] : depth[0]; pre = pc; } else { Push(S, pc); pc = pc->rchild; while (pc) { Push(S, pc); pc = pc->lchild; } } } return depth[1]+1; } void main() { int count = 0; BiTree T, B; printf("创建二叉树，按先后顺序输入二叉树中结点的值：\n"); CreateBiTree(T); NodeCount(T); printf("二叉树结点个数为：%d\n", nodenum); printf("二叉树的深度为：%d\n", Depth(T)); printf("先序遍历二叉树\n"); PreOrderTraverse(T); printf("中序遍历二叉树\n"); inOrderTraverse(T); printf("后序遍历二叉树\n"); PostOrderTraverse(T); printf("\n"); LeafCount(T,count); printf("统计二叉树叶子节点个数:%d\n", count); printf("交换二叉树的左右子树\n"); printf("先序遍历二叉树\n"); PreOrderTraverse(T); printf("\n"); printf("中序遍历二叉树\n"); inOrderTraverse(T); printf("\n"); printf("后序遍历二叉树\n"); PostOrderTraverse(T); printf("\n"); }