只包含递归和非递归遍历
#include <stdio.h> #include <stdlib.h> #define MaxSize 20 typedef struct node{ int data; struct node *lchild,*rchild; }TreeNode,*Tree; typedef TreeNode* Elem; //方便修改栈中元素类型 typedef struct{ Elem data[MaxSize]; int top; }Stack; void InitStack(Stack &S) //初始化栈 { S.top=-1; } bool isEmpty(Stack S) //判空 { if(S.top==-1) return true; else return false; } bool isFull(Stack S) //判满 { if(S.top==MaxSize-1) return true; else return false; } bool Push(Stack &S,Elem x) //压栈 { if(isFull(S)) return false; S.data[++S.top]=x; return true; } bool Pop(Stack &S,Elem &x) //弹栈 { if(isEmpty(S)) return false; x=S.data[S.top--]; return true; } bool GetTop(Stack S,Elem &x) //获取栈顶元素 { if(isEmpty(S)) return false; x=S.data[S.top]; return true; } void CreateTree(Tree &T) //先序创建二叉树,中序后序创建和递归遍历一样,只修改位置 { int x; scanf("%d",&x); if(x==-1) { T=NULL; return; } else { T=(TreeNode*)malloc(sizeof(TreeNode)); T->data=x; printf("输入%d的左结点:",x); CreateTree(T->lchild); printf("输入%d的右结点:",x); CreateTree(T->rchild); } } void PreOrder(Tree T) //先序遍历 { if(T!=NULL) { printf("%d ",T->data); PreOrder(T->lchild); PreOrder(T->rchild); } } void MidOrder(Tree T) //中序遍历 { if(T!=NULL) { MidOrder(T->lchild); printf("%d ",T->data); MidOrder(T->rchild); } } void LatOrder(Tree T) //后序遍历 { if(T!=NULL) { LatOrder(T->lchild); LatOrder(T->rchild); printf("%d ",T->data); } } void PreOrderByStack(Tree T) //先序非递归遍历 { Stack S; InitStack(S); TreeNode *p=T; while(p || !isEmpty(S)) { if(p) { printf("%d ",p->data); Push(S,p); p=p->lchild; } else { Pop(S,p); p=p->rchild; } } } void MidOrderByStack(Tree T) //中序非递归遍历 { Stack S; InitStack(S); TreeNode *p=T; while(p || !isEmpty(S)) { if(p) { Push(S,p); p=p->lchild; } else { Pop(S,p); printf("%d ",p->data); p=p->rchild; } } } void LatOrderByStack(Tree T) //后序非递归遍历 { Stack S; InitStack(S); TreeNode *p=T; TreeNode *r=NULL; while(p || !isEmpty(S)) { if(p) { Push(S,p); p=p->lchild; } else { GetTop(S,p); if(p->rchild&&p->rchild!=r) { p=p->rchild; } else { Pop(S,p); printf("%d ",p->data); r=p; p=NULL; } } } } int main() { Tree T; CreateTree(T); PreOrder(T); printf("\n"); PreOrderByStack(T); printf("\n"); MidOrder(T); printf("\n"); MidOrderByStack(T); printf("\n"); LatOrder(T); printf("\n"); LatOrderByStack(T); return 0; }
标签:遍历,return,递归,printf,rchild,data,Stack,TreeAPI From: https://www.cnblogs.com/simpleset/p/17753240.html