论坛 › C\C++交流 › 二叉树遍历

我是小BH 发表于 2021-3-19 15:30:39

二叉树遍历

#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;
        for (int i = 0; i < 8; i++) {
                node = new TreeNode;
                node->data = i;
        }
        root->Left = node;
        root->Right = node;
        node->Left = node;
        node->Right = node;
        node->Left = node;
        node->Left = node;
        node->Right = node;
        node->Right = node;
        node->Left = NULL;
        node->Right = NULL;
        node->Left = NULL;
        node->Right = NULL;
        node->Left = NULL;
        node->Right = NULL;
        node->Left = NULL;
        node->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 发表于 2021-3-19 22:00:02

#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;

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

        root->Left = node;      
        root->Right = node;      
        node->Left = node;   
        node->Right = node;   
        node->Left = node;   
        node->Left = node;   
        node->Right = node;   
        node->Right = node;

        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 发表于 2021-3-20 18:47:58

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


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

查看完整版本: 二叉树遍历