问题描述
- 关于c 二叉树---遍历疑问
-
原码如下：
//Program 11.7 Sorting integers using a binary tree
#include
#include
#include
//Function prototypes
struct Node *createnode(long value);
struct Node *addnode(long value,struct Node *pNode);
void listnodes(struct Node *pNode);
void freenodes(struct Node *pNode);
//Defines a node in a binary tree sotring integers
struct Node
{
long item;
int count;
struct Node *pLeft;
struct Node *pRight;
};
//Function main-execution starts here
int main(void)
{
long newvalue=0;
struct Node *pRoot=NULL;
char answer='n';
do
{
printf("Enter the node value:");
scanf("%ld",&newvalue);
if(pRoot==NULL)
pRoot=createnode(newvalue);
else
addnode(newvalue,pRoot);
printf("nDo you want to enter another(y or n)?");
while(answer=getchar())
if(tolower(answer)=='y'||tolower(answer)=='n')break;
} while(tolower(answer)=='y');
printf("The value in ascending sequence are:");
listnodes(pRoot); //Output the contents of the tree
freenodes(pRoot); //Release the heap memory
return 0;
}
struct Node *createnode(long value)
{
struct Node *pNode=(struct Node *)malloc(sizeof(struct Node));
pNode->item=value;
pNode->count=1;
pNode->pLeft=pNode->pRight=NULL;
return pNode;
}
//add a new node to the tree
struct Node *addnode(long value,struct Node *pNode)
{
if(pNode==NULL)
return createnode(value);
if(value==pNode->item)
{
++pNode->count;
return pNode;
}
if(valueitem)
{
if(pNode->pLeft==NULL)
{
pNode->pLeft=createnode(value);
return pNode->pLeft;
}
else
return addnode(value,pNode->pLeft);
}
else
{
if(pNode->pRight==NULL)
{
pNode->pRight=createnode(value);
return pNode->pRight;
}
else
return addnode(value,pNode->pRight);
}
}
//List the node values in ascending sequence
void listnodes(struct Node *pNode)
{
int i=0;
if(pNode->pLeft!=NULL)
listnodes(pNode->pLeft);
for(i=0;icount;i++)
printf("%10ldt",pNode->item);if(pNode->pRight!=NULL)
listnodes(pNode->pRight);
}
//Release memory allocated to nodes
void freenodes(struct Node *pNode)
{
if(pNode==NULL)
return ;
if(pNode->pLeft!=NULL)
freenodes(pNode->pLeft);if(pNode->pRight!=NULL)
freenodes(pNode->pRight);free(pNode);
}
以下函数理解：
//List the node values in ascending sequence
void listnodes(struct Node *pNode)
{
int i=0;
if(pNode->pLeft!=NULL)
listnodes(pNode->pLeft);
for(i=0;icount;i++)
printf("%10ldt",pNode->item);if(pNode->pRight!=NULL)
listnodes(pNode->pRight);
}
当输入：56、33、77、-10、100、-5、200
输入结果为：-10、-5、33、56、77、100、200
疑问点：
输出-10、-5我能理解；第二次输入后就不能理解了
是否当遍历树过程pNode->pRight==NULL&&pNode->pLeft==NULL下次执行
节点是否会移到上一层？？
请帮忙解答一下谢谢！！
解决方案
listnode是一个递归函数，如果出现pNode->pRight==NULL&&pNode->pLeft==NULL的情况，函数执行的顺序是这样的：先遍历pNode的上一
层，然后遍历pNode（此时没有输出pNode的上一层），因为pNode没有pLeft和pRight，所以直接输出pNode，pNode的遍历结束，然后输出pNode的上一层，也就是你理解的节点移到上一层。不对之处请指教。
解决方案二：
kaixinde104 kaixinde104 首先谢谢你的回答；另我现在的疑问是=>当pNode移到 上层时pNode->pRight！=NULL&&pNode->pLeft！=NULL条件满足接点不是会向下移吗!!
你加我Q吧这样描述清楚点249035477谢谢了