为了账号安全,请及时绑定邮箱和手机立即绑定

二叉树非递归的后序遍历为什么不对呢

/ 猿问

二叉树非递归的后序遍历为什么不对呢

C++
lapitaya 2019-11-12 15:38:04


已经看了好长时间了,还是不知道为什么,求指点

输入abd..e..cf..g..

输出如下所示,是循环的,知道大概是在判断p->right == pre处出的问题,但是就是想不通为什么此处条件不正确,求大神解答

debfgca
进入1 b stack a
进入1 d stack ba
进入1 NULL stack dba
getTop:d
ino:1 
p->right:NULL d进入2 pre:d stack ba
getTop:b
ino:0
进入3 e
进入1 NULL stack eba
getTop:e
ino:0
 p->right:NULL e进入2 pre:e stack ba
 getTop:b
 ino:0
 进入3 e
 进入1 NULL stack eba
 getTop:e
 ino:0
  p->right:NULL e进入2 pre:e stack ba
#include <iostream>#include<stdlib.h>using namespace std;#define MAXSIZE 50typedef struct TNode{	char data;	struct TNode *left, *right;}TNode, *bitTree;typedef TNode ElemType;typedef struct{    ElemType data[MAXSIZE];    int top;} Sqstack;void InitStack(Sqstack &S);bool isEmpty(Sqstack S);void getTop(Sqstack S, ElemType &e);void push(Sqstack &S, ElemType x);void pop(Sqstack &S, ElemType &x);void printStack(Sqstack S);void createTree(bitTree &T);void preOrder(bitTree T);void inOrder(bitTree T);void postOrder(bitTree T);void inOrderStack(bitTree T, Sqstack S);void preOrderStack(bitTree T, Sqstack S);void postOrderStack(bitTree T, Sqstack S);int main() {    bitTree T;    createTree(T);	//输入 abd..e..cf..g..    postOrder(T);    cout << endl;    Sqstack S;    InitStack(S);    //后序遍历非递归算法    postOrderStack(T, S);    }//后序遍历非递归void postOrderStack(bitTree T, Sqstack S){    TNode *p = T, *pre = NULL;    ElemType x;    while(p || !isEmpty(S)){        if(p){            cout << "进入1 ";            push(S, *p);            p = p->left;            if(p) cout << p->data << " ";            else cout << "NULL" << " ";            cout << "stack ";            printStack(S);        }        else{            getTop(S, x);            p = &x;            cout << "getTop:" << x.data << endl;            cout << "ino:" << (x.right == pre) << endl;            if(!p->right || p->right == pre){//右边为空或右边已经遍历过                pop(S, *p);                cout << p->data;                pre = p;                p = NULL;                cout << "进入2 ";                cout << "pre:" << pre->data;                //if(p->right) cout << " p->right:" << p->right->data;                //else cout << " p->right:NULL ";                cout << " stack ";                printStack(S);            }            else{                cout << "进入3 ";                p = p->right;                if(p) cout << p->data << endl;                else cout << "NULL" << endl;            }        }    }    }void createTree(bitTree &T){    //cout << "init" << endl;    //以递归前序遍历方式创建,空用.表示    TNode s;    char data;    data = getchar();    if(data != '.'){        T = (TNode*)malloc(sizeof(TNode));        T->data = data;        T->left = NULL;        T->right = NULL;        createTree(T->left);        createTree(T->right);    }    else{        T = NULL;    }}void postOrder(bitTree T){    if(T){        postOrder(T->left);        postOrder(T->right);        cout << T->data;    }}void printStack(Sqstack S){	for(int i = S.top; i > -1; i--){		cout << S.data[i].data;	}	cout << endl;}void InitStack(Sqstack &S){    S.top = -1;}bool isEmpty(Sqstack S){    if(S.top == -1) return 1;    return 0;}void getTop(Sqstack S, ElemType &e){    e = S.data[S.top];}void push(Sqstack &S, ElemType x){    if(S.top != MAXSIZE-1){        S.data[++S.top] = x;    }}void pop(Sqstack &S, ElemType &x){    if(S.top != -1){        x = S.data[S.top--];    }}


查看完整描述

2 回答

?
qq_Leafson_0

      .......

查看完整回答
反对 回复 2019-11-12
?
lapitaya

//img1.mukewang.com/5dca619f00010ddb07640592.jpg不知道为啥代码不能换行,这是函数的截图,发现问题在第70行,p->right一直输出的是NULL,求大神解答

查看完整回答
反对 回复 2019-11-12

添加回答

回复

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信