采用递归方法建立和遍历二叉树。首先建立二叉树的根结点,然后建立其左右子树,直到空子树为止。后序遍历二叉树时,先遍历左子树,后遍历右子树,最后访问根结点。
时间: 2023-08-22 19:04:20 浏览: 79
二叉树的几种操作,包括递归先序建立二叉树、先序遍历、中序遍历、后序遍历、非递归的各种遍历
下面是采用递归方法建立和遍历二叉树的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int data;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 建立二叉树
TreeNode *createTree() {
int val;
TreeNode *node;
scanf("%d", &val);
if (val == -1) {
node = NULL;
} else {
node = (TreeNode*)malloc(sizeof(TreeNode));
node->data = val;
node->left = createTree();
node->right = createTree();
}
return node;
}
// 后序遍历二叉树
void postorderTraversal(TreeNode *root) {
if (root) {
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%d ", root->data);
}
}
int main() {
TreeNode *root = createTree();
printf("后序遍历结果:");
postorderTraversal(root);
printf("\n");
return 0;
}
```
在上述代码中,首先定义了一个 TreeNode 结构体,用于表示二叉树中的节点。在 createTree 函数中,采用递归的方式建立二叉树。每次读入一个节点的值,如果该值为 -1,表示该节点为空,返回 NULL;否则创建一个新节点,将该值赋值给节点的 data 域,并递归地创建左右子树,最后返回该节点。
在 postorderTraversal 函数中,采用递归的方式后序遍历二叉树。对于每个节点,先递归遍历其左子树,然后递归遍历其右子树,最后输出该节点的值。由于后序遍历的顺序是左右根,因此需要先递归遍历左右子树,最后再输出根节点的值。
在主函数中,调用 createTree 函数建立二叉树,然后调用 postorderTraversal 函数后序遍历二叉树,并输出遍历结果。
总之,采用递归方法建立和遍历二叉树可以简洁明了地实现二叉树的操作。
阅读全文