用c++编程实现:建立二叉树并输出下列二叉树的(1)结点个数;(2)叶子结点个数;(3)深度;(4)先序序列、中序序列和后序序列。
时间: 2023-12-08 18:08:56 浏览: 70
好的,我可以为您提供代码实现,以下是完整的 C++ 代码:
```cpp
#include <iostream>
using namespace std;
//定义二叉树结点结构体
struct Node{
int data;
Node* left;
Node* right;
Node(int x): data(x), left(NULL), right(NULL) {}
};
//函数:创建二叉树
Node* createTree(){
Node* root = NULL;
int x;
cin >> x;
if (x == -1) return NULL;
root = new Node(x);
root->left = createTree();
root->right = createTree();
return root;
}
//函数:统计二叉树结点个数
int countNodes(Node* root){
if (root == NULL) return 0;
return countNodes(root->left) + countNodes(root->right) + 1;
}
//函数:统计二叉树叶子结点个数
int countLeaves(Node* root){
if (root == NULL) return 0;
if (root->left == NULL && root->right == NULL) return 1;
return countLeaves(root->left) + countLeaves(root->right);
}
//函数:统计二叉树深度
int getDepth(Node* root){
if (root == NULL) return 0;
int leftDepth = getDepth(root->left);
int rightDepth = getDepth(root->right);
return max(leftDepth, rightDepth) + 1;
}
//函数:输出二叉树先序序列
void preOrder(Node* root){
if (root == NULL) return;
cout << root->data << " ";
preOrder(root->left);
preOrder(root->right);
}
//函数:输出二叉树中序序列
void inOrder(Node* root){
if (root == NULL) return;
inOrder(root->left);
cout << root->data << " ";
inOrder(root->right);
}
//函数:输出二叉树后序序列
void postOrder(Node* root){
if (root == NULL) return;
postOrder(root->left);
postOrder(root->right);
cout << root->data << " ";
}
int main() {
Node* root = createTree();
cout << "结点个数:" << countNodes(root) << endl;
cout << "叶子结点个数:" << countLeaves(root) << endl;
cout << "深度:" << getDepth(root) << endl;
cout << "先序序列:";
preOrder(root);
cout << endl;
cout << "中序序列:";
inOrder(root);
cout << endl;
cout << "后序序列:";
postOrder(root);
cout << endl;
return 0;
}
```
输入示例:
```
1 2 4 -1 -1 5 -1 -1 3 -1 6 -1 -1
```
输出示例:
```
结点个数:6
叶子结点个数:3
深度:3
先序序列:1 2 4 5 3 6
中序序列:4 2 5 1 3 6
后序序列:4 5 2 6 3 1
```
阅读全文