</pre><p>最近捡起来二叉树的学习，因为之前只学会了使用二叉树的递归算法，所以想自己琢磨下非递归算法</p><pre name="code" class="cpp">
二叉树类的声明
class Tree{
private:
Tree * leftchild;
Tree * rightchild;
stringdata;
public:
Tree(){
leftchild = NULL;
rightchild = NULL;
}
Tree * buildtree();
void backread(Tree *t);
void show(Tree * t); //递归算法遍历二叉树检验结果是否正确
};
二叉树的先序建立
Tree * Tree::buildtree(){
string str;
int temp = 0;
int tag = 0;
Tree* root = new Tree;
Tree* p = root;
stack<Tree*> s;
cout << "请输入前序遍历序列，以#表示NULL" << endl;
cin >> str;
while (str[temp] != NULL){
if (str[temp] != '#'){//先建立至最左结点
p->data = str[temp];
p->leftchild = new Tree;
s.push(p);
p = p->leftchild;
tag = 0;//tag==0表示刚进去左孩子
}else{
p = s.top();//p跳回栈顶
if (tag == 0){
p->leftchild = NULL;
tag = 1;//tag==1表示从左孩子回来
}else{//tag != 0则表示第二次进入这个栈顶元素了
p->rightchild = NULL;//先给栈顶左孩子赋值NULL作为记号
if (str[temp + 1] == NULL){//字符串遍历到结尾则建立结束
break;
}
if (!s.empty()){
s.pop();//当一个栈里的元素第二次被访问时就应该pop
p = s.top();
}else{
p = NULL;
}
}
if (p != NULL){//p!=NULL说明栈顶元素的左结点为NULL，第一次访问栈顶元素
p->rightchild = new Tree;
p = p->rightchild;
}
if (str[temp + 1] != '#'){//从左结点回到某一结点的时，如果str下一个字符不是#说明该结点还有右节点
p = s.top()->rightchild;
p->rightchild = new Tree;
s.pop();
}
}
temp = temp + 1;
}
return root;
}
二叉树的后序遍历
后序遍历中用了一些奇技淫巧，因为需要判断栈里的元素是否为第二次遍历，而需要第二次遍历的结点是一定有右孩子的，所以在第一次访问的时候检查一次，如果有右孩子则push一个标志指针，如果在pop时栈顶元素为标志指针就说明里边的下一个元素是已经访问过的，就一并输出
void Tree::backread(Tree* t){
int tag = 0;
stack<Tree*> s;
Tree* n = new Tree;
Tree* p = t;
string a;
do{
if (p != NULL){//将左孩子入栈
s.push(p);
a = s.top()->data;
p = p->leftchild;
tag = 0;//tag == 0 表示刚进入左孩子
}else{
if (tag == 1 && s.top()->rightchild == NULL){//tag == 1 表示刚从左孩子回来
cout << s.top()->data << endl;//如果该结点的没有右孩子则输出并pop掉
s.pop();
}
while (!s.empty() && s.top() == n){//遇到了标志指针，则将标志指针之后的元素输出
s.pop();
cout << s.top()->data << endl;
s.pop();
}
if (s.empty()){
break;
}
p = s.top()->rightchild;//访问栈顶右孩子
if (p != NULL){//有右孩子则将该结点入栈并加入标志指针，且访问这个右节点的左孩子
s.push(n);
s.push(p);
p = p->leftchild;
}
tag = 1;
}
}while (!s.empty());
}