无法使用非递归中序方法遍历二叉树
Cannot traverse a binary tree with non-recursive inorder method
我正在尝试遍历使用键盘输入数据构建的二叉树。数据插入二叉树成功。我有一个 switch 语句,其中 'case 3' 应该使用非递归 Inorder 遍历算法遍历(并打印)二叉树。但是,当调用 'case 3' 时,它会出现 EXC_BAD_ACCESS 错误,这对我来说毫无意义。如果有人能帮助我解决这个问题,我会非常高兴。
(RootPtr 是全局定义的二叉树的顶级 0 级节点;而 GetNodeS 基本上是类型 StackPtr 指针的初始化函数(使用 malloc)。)
提前谢谢大家。
相关代码如下:
这些是结构定义,
Typedef struct treeItem
{
int data;
struct treeItem *left;
struct treeItem *right;
}Tree , *TreePtr;
typedef struct stackItem
{
TreePtr t;
struct stackItem *next;
}Stack , *StackPtr;
这些是 Push 和 Pop 函数,
void PushS (TreePtr TreePointer)
{
StackPtr TemPtr;
GetNodeS(&TemPtr);
(*TemPtr).t = TreePointer;
(*TemPtr).next = S;
S = TemPtr;
}
void PopS(TreePtr TreePointer)
{
StackPtr TemPtr;
GetNodeS(&TemPtr);
if (S != NULL)
{
TreePointer = (*S).t;
TemPtr = S;
S = (*S).next;
FreeNodeS(TemPtr);
}
else
printf("\nEmpty stack!");
}
这是遍历函数,
void iterative (TreePtr TemPtr)
{
DONE = 0;
TemPtr = RootPtr;
S = NULL;
if(items==0)
{
printf("\nTree is empty.\n\n");
DONE = 1;
}
else
{
printf("\nIterative nonrecursive inorder traversal:");
while (DONE == 0)
{
if(TemPtr != NULL)
{
PushS(TemPtr);
TemPtr = (*TemPtr).left;
}
else
if(S != NULL)
{
PopS(TemPtr);
printf(" %d", (*TemPtr).data); //the line I get the ERROR
TemPtr = (*TemPtr).right;
}
else
{
DONE = 1;
}
}
}
}
这是我尝试调用迭代遍历函数的切换情况,
case 3:
TreePtr TemPtr;
GetNode(&TemPtr);
iterative(TemPtr);
break;
您正在取消引用出现错误的行上的空指针。这就是 EXC_BAD_ACCESS 错误的原因。
if(TemPtr != NULL)
{
...
}
else // TemPtr must be NULL here
PopS(TemPtr);
不会更改 TempPtr
,因为它是按值传递的。
然后这里:
printf(" %d", (*TemPtr).data);
*TemPtr
是空指针解引用。
我正在尝试遍历使用键盘输入数据构建的二叉树。数据插入二叉树成功。我有一个 switch 语句,其中 'case 3' 应该使用非递归 Inorder 遍历算法遍历(并打印)二叉树。但是,当调用 'case 3' 时,它会出现 EXC_BAD_ACCESS 错误,这对我来说毫无意义。如果有人能帮助我解决这个问题,我会非常高兴。
(RootPtr 是全局定义的二叉树的顶级 0 级节点;而 GetNodeS 基本上是类型 StackPtr 指针的初始化函数(使用 malloc)。)
提前谢谢大家。
相关代码如下:
这些是结构定义,
Typedef struct treeItem
{
int data;
struct treeItem *left;
struct treeItem *right;
}Tree , *TreePtr;
typedef struct stackItem
{
TreePtr t;
struct stackItem *next;
}Stack , *StackPtr;
这些是 Push 和 Pop 函数,
void PushS (TreePtr TreePointer)
{
StackPtr TemPtr;
GetNodeS(&TemPtr);
(*TemPtr).t = TreePointer;
(*TemPtr).next = S;
S = TemPtr;
}
void PopS(TreePtr TreePointer)
{
StackPtr TemPtr;
GetNodeS(&TemPtr);
if (S != NULL)
{
TreePointer = (*S).t;
TemPtr = S;
S = (*S).next;
FreeNodeS(TemPtr);
}
else
printf("\nEmpty stack!");
}
这是遍历函数,
void iterative (TreePtr TemPtr)
{
DONE = 0;
TemPtr = RootPtr;
S = NULL;
if(items==0)
{
printf("\nTree is empty.\n\n");
DONE = 1;
}
else
{
printf("\nIterative nonrecursive inorder traversal:");
while (DONE == 0)
{
if(TemPtr != NULL)
{
PushS(TemPtr);
TemPtr = (*TemPtr).left;
}
else
if(S != NULL)
{
PopS(TemPtr);
printf(" %d", (*TemPtr).data); //the line I get the ERROR
TemPtr = (*TemPtr).right;
}
else
{
DONE = 1;
}
}
}
}
这是我尝试调用迭代遍历函数的切换情况,
case 3:
TreePtr TemPtr;
GetNode(&TemPtr);
iterative(TemPtr);
break;
您正在取消引用出现错误的行上的空指针。这就是 EXC_BAD_ACCESS 错误的原因。
if(TemPtr != NULL)
{
...
}
else // TemPtr must be NULL here
PopS(TemPtr);
不会更改 TempPtr
,因为它是按值传递的。
然后这里:
printf(" %d", (*TemPtr).data);
*TemPtr
是空指针解引用。