//非递归操作 #include <stdio.h> #include <stdlib.h> #define MaxSize 200 typedef struct TreeNode{ int data; struct TreeNode *lchild,*rchild; }TreeNode,*Tree; typedef struct{ Tree data[MaxSize]; int top; }Stack; void InitStack(Stack &S) { S.top=-1; } bool isEmpty(Stack S) { if(S.top==-1) { return true; } return false; } int Push(Stack &S,Tree x) { if(S.top==MaxSize-1) { return -1; } S.data[++S.top]=x; return 0; } int Pop(Stack &S,Tree &x) { if(S.top==-1) { return -1; } x=S.data[S.top--]; return 0; } void CreateTree(Tree &T) { int x; scanf("%d",&x); if(x==-1) { T=NULL; return; } else { T=(Tree)malloc(sizeof(TreeNode)); T->data=x; printf("输入%d的左结点:",x); CreateTree(T->lchild); printf("输入%d的右结点:",x); CreateTree(T->rchild); } } //先序遍历非递归操作 void PreOrderTree(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 MidOrderTree(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 LatOrderTree(Tree T) { Stack S; InitStack(S); TreeNode *p=T; while(p || !isEmpty) { if(p) { Push(S,p); p=p->lchild; } else { Pop(S,p); p=p->rchild; } } } */ int main() { Tree T; CreateTree(T); PreOrderTree(T); return 0; }
标签:遍历,return,递归,top,Tree,二叉树,TreeNode,data,Stack From: https://www.cnblogs.com/simpleset/p/17627961.html