中跟遍历

遍历"/>

中跟遍历

// 先序(附带叶子标记)建树
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stack>
#include<string>
using namespace std;
struct node
{char data;node* lchild;node* rchild;
};
void buildtree(char* str,node* root)
{stack<node*> sta;int pos = 0;int len = strlen(str);node* tmp;root->data = str[pos++];root->lchild = NULL;root->rchild = NULL;sta.push(root);while(pos < len){while(true){node* nl = new node;nl->data = str[pos];nl->lchild = NULL;nl->rchild = NULL;if(str[pos]=='*'){free(nl);break;}sta.top()->lchild = nl;sta.push(nl);++pos;}tmp = sta.top();sta.pop();++pos;while(str[pos]=='*'){if(!sta.empty()){tmp = sta.top();sta.pop();}++pos;}if(pos >= len)break;node* nr = new node;nr->data = str[pos];nr->lchild = NULL;nr->rchild = NULL;sta.push(nr);tmp->rchild = nr;++pos;}return;
}
void visit_rootsecond(node* root)
{stack<node*> sta;bool _end = false;node* p;sta.push(root);while(!sta.empty()){p = sta.top();while(p){p = p->lchild;sta.push(p);}sta.pop();p = sta.top();printf("%c",p->data);p = p->rchild;sta.pop();if(p){sta.push(p);continue;}while(p==NULL){if(sta.empty()){_end = true;break;}p = sta.top();sta.pop();p = p->rchild;}if(!_end){sta.push(p);}}
}
int main()
{char* str = new char[100];gets(str);//printf("%s",str);node* root = new node;buildtree(str,root);return 0;
}