以二叉链表为存储结构,编写算法建立一棵二叉树,并按前序遍历次序打印二叉树中的所有叶子结点。
时间: 2023-05-31 16:21:05 浏览: 118
### 回答1:
算法步骤如下:
1. 定义二叉树的结构体,包括数据域和左右子树指针域。
2. 定义一个函数,用于创建二叉树。函数输入为二叉树的根节点指针,输出为创建好的二叉树。
3. 在创建二叉树的过程中,如果当前节点的左右子树都为空,则该节点为叶子节点,将其值打印出来。
4. 定义一个函数,用于前序遍历二叉树。函数输入为二叉树的根节点指针,输出为前序遍历的结果。
5. 在前序遍历的过程中,如果当前节点的左右子树都为空,则该节点为叶子节点,将其值打印出来。
6. 调用创建二叉树函数和前序遍历函数,即可得到所有叶子节点的值。
代码实现如下:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int data;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 创建二叉树
TreeNode* createTree() {
int val;
scanf("%d", &val);
if (val == -1) {
return NULL;
}
TreeNode *root = (TreeNode*)malloc(sizeof(TreeNode));
root->data = val;
root->left = createTree();
root->right = createTree();
return root;
}
// 前序遍历二叉树
void preOrder(TreeNode *root) {
if (root == NULL) {
return;
}
printf("%d ", root->data);
preOrder(root->left);
preOrder(root->right);
}
// 打印所有叶子节点
void printLeaves(TreeNode *root) {
if (root == NULL) {
return;
}
if (root->left == NULL && root->right == NULL) {
printf("%d ", root->data);
}
printLeaves(root->left);
printLeaves(root->right);
}
int main() {
printf("请输入二叉树的前序遍历序列,-1表示空节点:\n");
TreeNode *root = createTree();
printf("前序遍历结果为:");
preOrder(root);
printf("\n所有叶子节点为:");
printLeaves(root);
printf("\n");
return ;
}
```
### 回答2:
二叉链表是一种常见的存储二叉树的方式,它采用链式存储结构,每个结点包含数据域和指向左右子树的指针。因此,我们可以通过遍历二叉树的方式,找到所有叶子结点并输出。
具体步骤如下:
1. 定义二叉树结点的结构体,包括数据域和指向左右子树的指针:
```
typedef struct node {
int data; // 数据域
struct node *left; // 左子树指针
struct node *right; // 右子树指针
} TreeNode;
```
2. 定义二叉树的建立函数,以先序遍历的方式输入结点值,如果输入的值为0,则表示该结点为空:
```
TreeNode* createTree() {
int value;
scanf("%d", &value);
if (value == 0) {
return NULL;
} else {
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->data = value;
node->left = createTree();
node->right = createTree();
return node;
}
}
```
3. 定义前序遍历函数,以输出所有叶子结点为目标,如果当前结点为空,则直接返回;如果当前结点为叶子结点,则输出它的值;否则分别遍历左右子树:
```
void preOrder(TreeNode* root) {
if (root == NULL) {
return;
}
if (root->left == NULL && root->right == NULL) {
printf("%d ", root->data);
}
preOrder(root->left);
preOrder(root->right);
}
```
4. 在主函数中调用上述函数,完成二叉树的建立和遍历:
```
int main() {
TreeNode* root = createTree();
preOrder(root);
return 0;
}
```
以上就是使用二叉链表存储二叉树,并按前序遍历次序打印二叉树中的所有叶子结点的算法实现。
### 回答3:
二叉链表是一种二叉树的存储结构,通过链表的方式来存储每个节点以及它们之间的关系。对于每个节点,除存储数据之外,还需要存储指向它的左右子节点的指针。
在基于二叉链表的存储结构下,我们可以采用递归的方式实现二叉树的建立和前序遍历。具体实现如下:
1. 声明二叉树节点的结构体,包含数据项以及左右子节点指针。
struct TreeNode {
int data;
TreeNode* left;
TreeNode* right;
TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};
2. 声明递归函数buildTree,该函数接受一个vector作为输入,该vector存储了按前序遍历顺序排列的二叉树节点的值。
TreeNode* buildTree(vector<int>& preorder, int& root_pos) {
if (root_pos >= preorder.size() || preorder[root_pos] == -1) {
return nullptr;
}
TreeNode* root = new TreeNode(preorder[root_pos]);
root->left = buildTree(preorder, ++root_pos);
root->right = buildTree(preorder, ++root_pos);
return root;
}
3. 定义递归函数printLeafNodes,该函数用于按前序遍历顺序打印二叉树中的所有叶子节点。
void printLeafNodes(TreeNode* root) {
if (root == nullptr) {
return;
}
if (root->left == nullptr && root->right == nullptr) {
cout << root->data << " ";
}
printLeafNodes(root->left);
printLeafNodes(root->right);
}
4. 根据以上递归函数,我们可以实现完整的算法如下:
void buildAndPrintTree(vector<int>& preorder) {
int root_pos = 0;
TreeNode* root = buildTree(preorder, root_pos);
cout << "二叉树前序遍历结果:";
printTree(root);
cout << "\n所有叶子节点:";
printLeafNodes(root);
}
在执行buildAndPrintTree函数时,输入的参数preorder表示按前序遍历顺序排列的二叉树节点值的vector。该函数会根据该vector构建一颗二叉树,并按照前序遍历顺序输出所有节点的值,同时输出该二叉树中所有叶子节点。
阅读全文