测试例子：输入ab#d##c#e##
输出：abdce
bdace
dbeca
#include<stdio.h> #include<stdlib.h> #include<iostream> #include<stack> using namespace std; struct Node { Node *rchild; Node *lchild; char data; }; int loc; #if 0 Node *create() { Tree[loc].lchild = Tree[loc].rchild = NULL; return &Tree[loc++]; } #endif Node *createtree(Node *bt) { char c; cin >> c; if (c == '#') { bt == NULL; //return ; } else { bt = new Node; bt->data = c; bt->lchild = createtree(bt->lchild); bt->rchild = createtree(bt->rchild); } return bt; } void preOrder(Node *bt) { if (bt != NULL) { printf("%c", bt->data); if (bt->lchild) preOrder(bt->lchild); //printf("%c",bt->data); if (bt->rchild) preOrder(bt->rchild); //printf("%c",bt->data); } //printf("\n"); } void inOrder(Node *bt) { if (bt != NULL) { //printf("%c",bt->data); if (bt->lchild) inOrder(bt->lchild); printf("%c", bt->data); if (bt->rchild) inOrder(bt->rchild); //printf("%c",bt->data); } //printf("\n"); } void postOrder(Node *bt) { if (bt != NULL) { //printf("%c",bt->data); if (bt->lchild) postOrder(bt->lchild); //printf("%c",bt->data); if (bt->rchild) postOrder(bt->rchild); printf("%c", bt->data); } //printf("\n"); } //非递归 void PreOrderStack(Node *bt) { stack<Node*> pre; Node *cur = bt; //pre.push(cur); while (!cur || !pre.empty()) { while(cur!=null){ printf("%c", cur->data); pre.push(cur); cur = cur->lchild; } if(!pre.empty()) { cur = pre.top(); pre.pop(); cur = cur->rchild; } } } void InOrderStack(Node *bt) { stack<Node*> In; Node *cur = bt; while (!cur || !In.empty()) { while(cur!=null){ In.push(cur); cur = cur->lchild; } if(!In.empty()) { cur = In.top(); printf("%c", cur->data); In.pop(); cur = cur->rchild; } } } //要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点P，先将其入栈。 //如果P不存在左孩子和右孩子，则可以直接访问它；或者P存 在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点。 //若非上述两种情况，则将P的右孩子和左孩子依次入栈，这样就保证了 每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。 void PostOrderStack(Node *bt) { stack<Node*> post; Node *cur = bt; Node *pre = NULL; post.push(bt); while (!post.empty()) { cur = post.top(); if ((cur->lchild == NULL&&cur->rchild == NULL) || (pre != NULL && (pre == cur->rchild || pre == cur->lchild))) { printf("%c", cur->data); post.pop(); pre = cur; } else { if (cur->rchild) //注意栈的先进后出，所以右子树先进 post.push(cur->rchild); if (cur->lchild) post.push(cur->lchild); } } } int main() { loc = 0; Node *bt; bt = createtree(bt); preOrder(bt); printf("\n"); inOrder(bt); printf("\n"); postOrder(bt); printf("\n"); //system("pause"); return 0; }
