创建二叉树,分别以先序遍历、中序遍历、后序遍历访问二叉树,并输出二叉树的叶子结点及叶子结点的个数的c++源代码
时间: 2023-12-14 22:39:03 浏览: 82
以下是创建二叉树,并分别以先序遍历、中序遍历、后序遍历访问二叉树的c++源代码:
```c++
#include<iostream>
using namespace std;
//定义二叉树结构体
struct TreeNode {
char data;
TreeNode *left;
TreeNode *right;
};
//创建二叉树
TreeNode *createTree() {
char ch;
TreeNode *root = NULL;
cin >> ch;
if (ch != '#') {
root = new TreeNode();
root->data = ch;
root->left = createTree();
root->right = createTree();
}
return root;
}
//先序遍历二叉树
void preorder(TreeNode *root) {
if (root == NULL) {
return;
}
cout << root->data << " ";
preorder(root->left);
preorder(root->right);
}
//中序遍历二叉树
void inorder(TreeNode *root) {
if (root == NULL) {
return;
}
inorder(root->left);
cout << root->data << " ";
inorder(root->right);
}
//后序遍历二叉树
void postorder(TreeNode *root) {
if (root == NULL) {
return;
}
postorder(root->left);
postorder(root->right);
cout << root->data << " ";
}
//统计叶子结点个数并输出叶子结点
int countLeaves(TreeNode *root) {
if (root == NULL) {
return 0;
}
if (root->left == NULL && root->right == NULL) {
cout << root->data << " ";
return 1;
}
return countLeaves(root->left) + countLeaves(root->right);
}
int main() {
TreeNode *root = createTree();
cout << "先序遍历:";
preorder(root);
cout << endl;
cout << "中序遍历:";
inorder(root);
cout << endl;
cout << "后序遍历:";
postorder(root);
cout << endl;
cout << "叶子结点:";
int leaves = countLeaves(root);
cout << endl;
cout << "叶子结点个数:" << leaves << endl;
return 0;
}
```
在程序中,#表示空节点。当输入#时,说明该节点为空,返回NULL。在主函数中,先创建二叉树,再分别以先序遍历、中序遍历、后序遍历访问二叉树,并输出叶子结点及叶子结点的个数。
阅读全文