二叉树遍历

我是小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

1. #include<iostream>
   
2. 
   
3. using namespace std;
   
4. struct TreeNode
   
5. {
   
6.         TreeNode* Left;
   
7.         TreeNode* Right;
   
8.         int data;
   
9.         //设置一个是否遍历的标志位
   
10.         int flag;
    
11. };
    
12. 
    
13. struct Stack
    
14. {
    
15.         struct Stack* Next;
    
16.         TreeNode* treenode;
    
17. };
    
18. 
    
19. void PreOrderTraversal(TreeNode*,Stack*);
    
20. Stack* CreatStack();
    
21. void Push(Stack*,TreeNode*);
    
22. TreeNode* Pop(Stack*);
    
23. int IsEmpty(Stack*);
    
24. 
    
25. int main()
    
26. {
    
27.         TreeNode* root;
    
28.         root = new TreeNode;
    
29.         root->data = 100;
    
30.         root->flag = 0;
    
31. 
    
32.         TreeNode *node[8];
    
33. 
    
34.         for (int i = 0; i < 8; i++)
    
35.         {
    
36.                 node[i] = new TreeNode;
    
37.                 node[i]->Left = NULL;
    
38.                 node[i]->Right = NULL;
    
39.                 node[i]->data = i;
    
40.                 node[i]->flag = 0;
    
41.         }
    
42. /*
    
43.                  100
    
44.                  0               4
    
45.         1        2       5       6
    
46.                3            7
    
47. */
    
48. 
    
49.         root->Left = node[0];        
    
50.         root->Right = node[4];      
    
51.         node[0]->Left = node[1];     
    
52.         node[0]->Right = node[2];   
    
53.         node[2]->Left = node[3];     
    
54.         node[4]->Left = node[5];     
    
55.         node[4]->Right = node[6];   
    
56.         node[5]->Right = node[7];
    
57. 
    
58.         Stack* S = CreatStack();
    
59.         PreOrderTraversal(root, S);
    
60.         cin.get();
    
61.         return 0;
    
62. }
    
63. 
    
64. Stack* CreatStack()
    
65. {
    
66.         Stack* S=new Stack;
    
67.         S->Next = NULL;
    
68.         return S;
    
69. }
    
70. 
    
71. void Push(Stack* S,TreeNode* p)
    
72. {
    
73.         Stack* temp = new Stack;
    
74.         temp->treenode = p;
    
75.         temp->Next = S->Next;
    
76.         S->Next = temp;
    
77. }
    
78. 
    
79. TreeNode* Pop(Stack* S) {
    
80.         if (IsEmpty(S)) {
    
81.                 cout << "堆栈空！";
    
82.                 return NULL;
    
83.         }
    
84.         else {
    
85.                 Stack* temp = S->Next;
    
86.                 S->Next = temp->Next;
    
87.                 TreeNode* temptree = temp->treenode;
    
88.                 delete(temp);
    
89.                 return temptree;
    
90.         }
    
91. }
    
92. int IsEmpty(Stack* S) {
    
93.         return(S->Next == NULL);
    
94. }
    
95. void PreOrderTraversal(TreeNode* BT,Stack* S)
    
96. {
    
97.         TreeNode* T = BT;
    
98.         TreeNode * tmp = NULL;
    
99.         //取反标志位标志已遍历
    
100.         int flag = !BT->flag;
     
101. 
     
102.         do
     
103.         {
     
104.                 //遍历左子节点
     
105.                 if(T != NULL)
     
106.                 {
     
107.                         if(T->flag != flag)
     
108.                         {
     
109.                                 cout << T->data << endl;
     
110.                                 Push(S,T);
     
111.                                 T = T->Left;
     
112.                                 continue;
     
113.                         }
     
114.                 }
     
115.                
     
116.                 //遍历右子节点
     
117.                 if(T!= NULL)
     
118.                 {
     
119.                         tmp = T->Right;
     
120.                         if(tmp != NULL && tmp->flag != flag)
     
121.                         {
     
122.                                 Push(S,T);
     
123.                                 T = tmp;
     
124.                                 continue;
     
125.                         }
     
126.                 }
     
127.                
     
128.                 //父节点出栈
     
129.                 tmp = Pop(S);
     
130. 
     
131.                 if(tmp != NULL)
     
132.                 {
     
133.                         T = tmp;
     
134.                         T->flag = flag;
     
135.                 }
     
136.                 else
     
137.                 {
     
138.                         break;
     
139.                 }
     
140.         } while (1);
     
141. }
     

复制代码

我是小BH

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

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