- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
我正在尝试使用单个堆栈实现树的后序遍历。我现在遇到段错误有人能给我解释一下原因吗?
这是算法:
1.1 Create an empty stack
2.1 Do following while root is not NULL
a) Push root's right child and then root to stack.
b) Set root as root's left child.
2.2 Pop an item from stack and set it as root.
a) If the popped item has a right child and the right child
is at top of stack, then remove the right child from stack,
push the root back and set root as root's right child.
b) Else print root's data and set root as NULL.
2.3 Repeat steps 2.1 and 2.2 while stack is not empty.
示例
。 1 的右 child 存在。 按 3 堆叠。按 1 堆叠。移动到左边的 child 。 堆栈: 3, 1
存在 2 的右 child 。按 5 堆叠。按 2 堆叠。移动到左边的 child 。 堆栈:3、1、5、2
4 的右子节点不存在。 '按 4 堆叠。移动到左边的 child 。 堆栈:3、1、5、2、4
当前节点为 NULL。从堆栈中弹出 4。 4 的右 child 不存在。打印 4. 将当前节点设置为 NULL。 堆栈:3、1、5、2
当前节点为 NULL。从堆栈中弹出 2。由于 2 的右子元素等于栈顶元素,从堆栈中弹出 5。现在将 2 压入堆栈。
将当前节点移动到 2 的右子节点,即 5 堆栈:3、1、2
5 的右子节点不存在。按 5 堆叠。移动到左边的 child 。 堆栈:3、1、2、5
当前节点为 NULL。从堆栈中弹出 5。 5 的右 child 不存在。打印 5. 将当前节点设置为 NULL。 堆栈:3、1、2
当前节点为 NULL。从堆栈中弹出 2。2 的右子元素不等于栈顶元素。打印 2. 将当前节点设置为 NULL。 堆栈: 3, 1
当前节点为 NULL。从堆栈中弹出 1。由于 1 的右子元素等于栈顶元素,因此从栈中弹出 3。现在将 1 压入堆栈。将当前节点移动到 1 的右子节点,即 3 堆栈:1
重复上述步骤并打印 6、7 和 3。弹出 1 和打印 1。
代码:问题出在 Ipostorder 函数中。如果您注释并运行,则不会出现段错误。
#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
int data;
struct node *left,*right;
}node;
typedef struct stack
{
node *data;
struct stack *next;
}stack;
stack *top=NULL;
int isEmpty()
{
if(top==NULL)
return 1;
else
return 0;
}
node *pop()
{
node *p=top->data;
top=top->next;
return p;
}
void push(node *num)
{
stack *p;
p=malloc(sizeof(stack));
p->data=num;
p->next=top;
top=p;
}
node *newNode(int key)
{
node *p=malloc(sizeof(node));
p->left=p->right=NULL;
p->data=key;
return p;
}
void insert(node **head,int key)
{
node *p;
p=*head;
if(!p)
{
*head=newNode(key);
return;
}
if(p->data>key)
insert(&(p->left),key);
else
insert(&(p->right),key);
}
void inorder(node *head)
{
if(head)
{
inorder(head->left);
printf("%d ",head->data);
inorder(head->right);
}
}
int search(node *head,int key)
{
if(head==NULL)
return 0;
if(head->data==key)
return 1;
if(head->data>key)
search(head->left,key);
else
search(head->right,key);
}
void Ipostorder(node *head)
{
do
{
while(head)
{
if(head->right) //If right child is present
push(head->right); //Push right child first
push(head); //Push root
head=head->left; //Goto left
}
head=pop();
if(head->right && top->data==head->right)
{
pop(); //Remove right child from stack
push(head); //Push root onto the stack
head=head->right;
}
else
{
printf(" %d",head->data);
head=NULL;
}
}while(!isEmpty());
}
void postorder(node *head)
{
if(head)
{
postorder(head->left);
postorder(head->right);
printf(" %d",head->data);
}
}
int main()
{
node *head;
int opt,choice=1,key;
while(choice!=5)
{
printf("\n\nBST\n1.Insert into BST\n2.Inorder Traversal\n3.Search\n4.Iterative preorder\n5.Exit\n\nChoice - ");
scanf("%d",&choice);
switch(choice)
{
case 1: printf("\nEnter the no of elements to be inserted - ");
scanf("%d",&opt);
printf("\nEnter the elements - ");
while(opt--)
{
scanf("%d",&key);
insert(&head,key);
}
printf("\nElement successfully inserted");
break;
case 2: printf("\nThe inorder traversal is - ");
inorder(head);
break;
case 3: printf("\nEnter the item to be searched - ");
scanf("%d",&key);
if(search(head,key))
printf("\nItem found");
else
printf("\nItem not found");
break;
case 4: printf("\nThe iterative postorder is - ");
Ipostorder(head);
printf("\nThe recursive postorder is - ");
postorder(head);
break;
case 5: exit(0);
break;
}
getchar();
getchar();
}
}
输入/输出
BST
1.Insert into BST
2.Inorder Traversal
3.Search
4.Iterative preorder
5.Exit
Choice - 1
Enter the no of elements to be inserted - 7
Enter the elements - 30 20 40 15 25 35 45
Element successfully inserted
BST
1.Insert into BST
2.Inorder Traversal
3.Search
4.Iterative preorder
5.Exit
Choice - 2
The inorder traversal is - 15 20 25 30 35 40 45
BST
1.Insert into BST
2.Inorder Traversal
3.Search
4.Iterative preorder
5.Exit
Choice - 4
Segmentation fault (core dumped)
最佳答案
Ipostorder
在验证 top
不为 NULL 之前取消引用它。同样,它在第一个 pop
之后取消引用 head
。
关于c - 后序树遍历中的段错误,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/28569624/
序 大家好呀,我是summo,这次来写写我在上班空闲(摸鱼)的时候做的一个小网站的事。去年阿里云不是推出了个活动嘛,2核2G的云服务器一年只要99块钱,懂行的人应该知道这个价格在业界已经是非常良心了
我尝试根据给定的级别顺序(BFS 顺序)构造 BST。我知道这是可能的,但我不知道我该怎么写。问题是我必须使用 BFS 序列。所以,我不能在这里使用递归,我必须迭代地编写我的程序......我发现这有
我是一名优秀的程序员,十分优秀!