初学者提问:有关二叉树的中序遍历非递归算法的C语言实现

hwqyc 发布于 2012/09/07 16:23
阅读 458
收藏 0

下面代码是我在网上找到的二叉树的中序遍历非递归算法的C语言实现。我的疑问已经用问号标注,希望大家指教:

#include<stdio.h>
#include<malloc.h>
#define NUM_NODE 12
typedef struct Node{
int data;
struct Node *lchild,*rchild;
}BiTreeNode,*BiTree;


BiTree CreateTree(int n){
BiTree bt;
if(n<=0||n>NUM_NODE)return NULL;
if(!(bt=(BiTree)malloc(sizeof(BiTreeNode))))return NULL;
bt->data=n;
printf("%d\t",bt->data);
bt->lchild=CreateTree(2*n);
bt->rchild=CreateTree(2*n+1);
return bt;
}


void FreeTree(BiTree bt){
if(bt){
if(bt->lchild)
FreeTree(bt->lchild);
if(bt->rchild)
FreeTree(bt->rchild);
printf("%d\t",bt->data);
free(bt);
}
}


//中序遍历非递归
void InOrder(BiTree bt){
BiTree *stack,*top,p;
//创建栈
if(!(stack=(BiTree*)malloc(NUM_NODE*sizeof(BiTreeNode)))){
printf("InOrder failer for memory\n");
return;
}
//初始化堆栈
top=stack;
p=bt;
while(p||top>stack){ //p不为NULL或者堆栈不空    为什么不是*top>*stack????
if(p){
*top++=p; //p入栈     为什么不是(*top)++???
p=p->lchild;
}
else{
p=*--top; //栈顶元素出栈,并用p指向     为什么不是p=--(*top)???
if(p) printf("%d\t",p->data);
p=p->rchild;
}
}
}


int main(){
BiTree root;
printf("Create Tree\n");
root=CreateTree(1);
printf("\nInOrder\n");
InOrder(root);
printf("\nFree Tree\n");
FreeTree(root);
return 0;
}

栈里存放的到底是结点,还是指向结点的指针?

加载中
0
晓寒
晓寒
栈是一个指针栈,入栈的每一个元素是BiTree类型。是指向结点的指针。
top 和 stack 是栈的内存地址。 而*top 和 *stack 则是栈里的元素的内容。
也就是BiTree,这是一个树结点的地址。
比如:栈底在内存中的位置是 1000, stack则是1000,如果此时入栈一个元素,top增为1004,
入栈的那个元素假设是树要结点,内存地址为500,则此时*stack则为500,
如果你 --(*top)的话,实际上*top是没有内容的,这个操作是不可预知的。

另外,这个程序有一个问题,它在InOrder里创建栈时栈多分配了2倍的空间。sizeof(BiTreeNode)
应该改为sizeof(BiTree), 结点的大小为12字节,但BiTree的大小为4字节。

 

小提示: 贴代码时最好用插入代码,这样代码的格式好看一些。

晓寒
晓寒
回复 @hwqyc : 刚开始你可以这么理解。因为malloc返加的是void*型的一片内存。 你把它转成什么类型它就是什么类型。
h
hwqyc
嗯嗯,豁然开朗呐~~非常感谢前辈的耐心解答。另外还有一个小问题,malloc函数的前后是不是应该对应,比如stack=(BiTree*)malloc(NUM_NODE*sizeof(BiTree))中(BiTree*)和(BiTree)对应?
返回顶部
顶部