UC知道树的递归算法
来源：百度知道 编辑：UC知道 时间：2024/05/07 13:52:34
题目是这样的
A是根结点，A的左子树是B，B的左子树是C，C的右子树是E，A的右子树是D，D的左子树是F，右子树是G，现在运行下面的程序，输出结果是什么
struct node
{char data;
struct node *lchild, rchild;
};
C算法如下：
void traversal(struct node *root)
{if (root)
{printf(“%c”, root->data);
traversal(root->lchild);
printf(“%c”, root->data);
traversal(root->rchild);
}
}
答案是：A B C C E E B A D F F D G G
可是我看不懂啊，谁能详细的告诉我程序是如何运行的
if(root)是什么意思
A是根结点，A的左子树是B，B的左子树是C，C的右子树是E，A的右子树是D，D的左子树是F，右子树是G，现在运行下面的程序，输出结果是什么
struct node
{char data;
struct node *lchild, rchild;
};
C算法如下：
void traversal(struct node *root)
{if (root)
{printf(“%c”, root->data);
traversal(root->lchild);
printf(“%c”, root->data);
traversal(root->rchild);
}
}
答案是：A B C C E E B A D F F D G G
可是我看不懂啊，谁能详细的告诉我程序是如何运行的
if(root)是什么意思
答案是正确的啊。
if(root)就是如果root!=0，这里root是一个指针，指向结构体struct node的指针，第一次进入函数它就是指向根节点A的指针
运行步骤：
如果指向A的指针不为空(不为0),打印'A',
递归调用函数指向A的左孩子节点
如果指向B的指针不为空(不为0),打印'B',
递归调用函数指向B的左孩子节点
如果指向C的指针不为空(不为0),打印'C',
递归调用函数指向C的左孩子节点
由于C的左孩子节点为空，所以本次递归traversal(root->lchild)结束，回到上一层递归中即从C的左孩子节点回到C中，然后执行traversal(root->lchild)这一句下面一句，打印出'C'
然后递归调用traversal(root->rchild);指向C的右孩子节点
如果指向E的指针不为空(不为0),打印'E',
然后再递归指向E的左孩子节点，为空再返回到E中，再次打印出'E',然后再指向E的右孩子节点，为空，E的递归结束返回上一层递归即C中，然后C也到达末尾结束返回上一层递归B中，然后执行traversal(root->lchild)这一句下面一句，打印出'B'
然后递归调用traversal(root->rchild);指向B的右孩子节点
......
如此不断进入某个节点的子节点操作后再从子节点返回父节点，层层进入再层层向上返回，从而遍历树中各个节点，最终得出结果：
A B C C E E B A D F F D G G
递归法前序遍历。
前序遍历是先访问根结点，再访问左儿子，再访问右儿子。如果左右儿子也是一颗树，就先访问左儿子的儿子结点，再访问右儿子的儿子结点。依此类推。即可得到上述答案。
递归是一个动态的过程
建议你拿张纸把树画出来
然后自己手动执行一遍遍历过程