以二叉链表建立二叉树链式存储结构,实现前序遍历、求叶子结点的个数计算、中序遍历、后序遍历、求深度。画出其调用关系图和流程图
时间: 2024-01-29 08:04:33 浏览: 32
好的,我来回答你的问题。首先,关于你的要求,我会尊重你的隐私,不会泄漏你说的话。
对于二叉链表建立二叉树链式存储结构,我们可以定义一个节点结构体:
```
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
```
接着,我们可以通过输入来构建一棵二叉树:
```
TreeNode* buildTree() {
int val;
cin >> val;
if (val == -1) {
return NULL;
}
TreeNode* root = new TreeNode(val);
root->left = buildTree();
root->right = buildTree();
return root;
}
```
在这里,我们通过输入-1来表示一个空节点。根据这个函数可以构建一棵二叉树。接下来,我们可以实现各种遍历和功能:
前序遍历:
```
void preOrder(TreeNode* root) {
if (root == NULL) {
return;
}
cout << root->val << " ";
preOrder(root->left);
preOrder(root->right);
}
```
求叶子结点个数:
```
int countLeaf(TreeNode* root) {
if (root == NULL) {
return 0;
}
if (root->left == NULL && root->right == NULL) {
return 1;
}
return countLeaf(root->left) + countLeaf(root->right);
}
```
中序遍历:
```
void inOrder(TreeNode* root) {
if (root == NULL) {
return;
}
inOrder(root->left);
cout << root->val << " ";
inOrder(root->right);
}
```
后序遍历:
```
void postOrder(TreeNode* root) {
if (root == NULL) {
return;
}
postOrder(root->left);
postOrder(root->right);
cout << root->val << " ";
}
```
求深度:
```
int depth(TreeNode* root) {
if (root == NULL) {
return 0;
}
int leftDepth = depth(root->left) + 1;
int rightDepth = depth(root->right) + 1;
return max(leftDepth, rightDepth);
}
```
至于调用关系图和流程图,我可以为你生成一张简单的图,但由于平台限制,我无法直接展示图片,请您将下面的代码复制到一张画板上,绘制出对应的图形:
```
+--------------+
| buildTree |
+--------------+
|
V
+--------------+
| preOrder |
+--------------+
|
V
+--------------+
| countLeaf |
+--------------+
|
V
+--------------+
| inOrder |
+--------------+
|
V
+--------------+
| postOrder |
+--------------+
|
V
+--------------+
| depth |
+--------------+
```
希望我能够对你有所帮助。