二叉树遍历

我是小BH

#include<iostream>
using namespace std;
struct TreeNode {
        TreeNode* Left;
        TreeNode* Right;
        int data;
};
struct Stack {
        Stack* Next;
        TreeNode* treenode;
};
void PreOrderTraversal(TreeNode*,Stack*);
Stack* CreatStack();
void Push(Stack*,TreeNode*);
TreeNode* Pop(Stack*);
int IsEmpty(Stack*);
int main() {
        TreeNode* root;
        root = new TreeNode;
        root->data = 100;
        TreeNode *node[8];
        for (int i = 0; i < 8; i++) {
                node[i] = new TreeNode;
                node[i]->data = i;
        }
        root->Left = node[0];
        root->Right = node[4];
        node[0]->Left = node[1];
        node[0]->Right = node[2];
        node[2]->Left = node[3];
        node[4]->Left = node[5];
        node[4]->Right = node[6];
        node[5]->Right = node[7];
        node[1]->Left = NULL;
        node[1]->Right = NULL;
        node[3]->Left = NULL;
        node[3]->Right = NULL;
        node[7]->Left = NULL;
        node[7]->Right = NULL;
        node[6]->Left = NULL;
        node[6]->Right = NULL;
        Stack* S = CreatStack();
        PreOrderTraversal(root, S);
        cin.get();
        return 0;
}
Stack* CreatStack() {
        Stack* S=new Stack;
        S->Next = NULL;
        return S;
}
void Push(Stack* S,TreeNode* p) {
        Stack* temp = new Stack;
        temp->treenode = p;
        temp->Next = S->Next;
        S->Next = temp;
}
TreeNode* Pop(Stack* S) {
        if (IsEmpty(S)) {
                cout << "堆栈空！";
                return NULL;
        }
        else {
                Stack* temp = new Stack;
                temp = S->Next;
                S->Next = temp->Next;
                TreeNode* temptree = temp->treenode;
                delete(temp);
                return temptree;
        }
}
int IsEmpty(Stack* S) {
        return(S->Next == NULL);
}
void PreOrderTraversal(TreeNode* BT,Stack* S) {
        TreeNode* T = BT;
        while (T || !IsEmpty(S)) {
                while (T) {
                        Push(S, T);
                        cout << T->data << endl;
                        T = T->Left;
                }
                if(!IsEmpty(S)){
                        T = Pop(S);
                        T = T->Right;
                }
        }
}
有没有hxd帮我看看错在哪了
输出结果为：
100
0
1
2
3
(后面就不输出了)
vs2019报错cout << T->data << endl;这句引发了异常: 读取访问权限冲突。

xieglt

#include<iostream>

using namespace std;
struct TreeNode 
{
        TreeNode* Left;
        TreeNode* Right;
        int data;
        //设置一个是否遍历的标志位
        int flag;
};

struct Stack 
{
        struct Stack* Next;
        TreeNode* treenode;
};

void PreOrderTraversal(TreeNode*,Stack*);
Stack* CreatStack();
void Push(Stack*,TreeNode*);
TreeNode* Pop(Stack*);
int IsEmpty(Stack*);

int main() 
{
        TreeNode* root;
        root = new TreeNode;
        root->data = 100;
        root->flag = 0;

        TreeNode *node[8];

        for (int i = 0; i < 8; i++) 
        {
                node[i] = new TreeNode;
                node[i]->Left = NULL;
                node[i]->Right = NULL;
                node[i]->data = i;
                node[i]->flag = 0;
        }
/*
                 100
                 0               4
        1        2       5       6
               3            7
*/

        root->Left = node[0];        
        root->Right = node[4];       
        node[0]->Left = node[1];     
        node[0]->Right = node[2];    
        node[2]->Left = node[3];     
        node[4]->Left = node[5];     
        node[4]->Right = node[6];    
        node[5]->Right = node[7];

        Stack* S = CreatStack();
        PreOrderTraversal(root, S);
        cin.get();
        return 0;
}

Stack* CreatStack() 
{
        Stack* S=new Stack;
        S->Next = NULL;
        return S;
}

void Push(Stack* S,TreeNode* p) 
{
        Stack* temp = new Stack;
        temp->treenode = p;
        temp->Next = S->Next;
        S->Next = temp;
}

TreeNode* Pop(Stack* S) {
        if (IsEmpty(S)) {
                cout << "堆栈空！";
                return NULL;
        }
        else {
                Stack* temp = S->Next;
                S->Next = temp->Next;
                TreeNode* temptree = temp->treenode;
                delete(temp);
                return temptree;
        }
}
int IsEmpty(Stack* S) {
        return(S->Next == NULL);
}
void PreOrderTraversal(TreeNode* BT,Stack* S)
{
        TreeNode* T = BT;
        TreeNode * tmp = NULL;
        //取反标志位标志已遍历
        int flag = !BT->flag;

        do 
        {
                //遍历左子节点
                if(T != NULL)
                {
                        if(T->flag != flag)
                        {
                                cout << T->data << endl;
                                Push(S,T);
                                T = T->Left;
                                continue;
                        }
                }
                
                //遍历右子节点
                if(T!= NULL)
                {
                        tmp = T->Right;
                        if(tmp != NULL && tmp->flag != flag)
                        {
                                Push(S,T);
                                T = tmp;
                                continue;
                        }
                }
                
                //父节点出栈
                tmp = Pop(S);

                if(tmp != NULL)
                {
                        T = tmp;
                        T->flag = flag;
                }
                else
                {
                        break;
                }
        } while (1);
}

我是小BH

xieglt 发表于 2021-3-19 22:00

xxxd，我看到错误在哪了，是在创建树的时候有两个结点的left和right没有设为NULL