使用二叉链表存储结构建立一棵二叉树,完成如下功能: 1.创建二叉树 2.先序遍历二叉树 3.中序遍历二叉树 4.后序遍历二叉树 5.求二叉树深度 6.求二叉树叶子结点个数
时间: 2023-11-14 10:17:15 浏览: 201
编写采用二叉链表形式存储的二叉树的创建、先序、中序、后序和按层遍历的算法
5星 · 资源好评率100%
以下是使用二叉链表存储结构建立二叉树并实现各种功能的示例代码(使用 C++ 语言实现):
```cpp
#include <iostream>
using namespace std;
//二叉树结点定义
struct BinaryTreeNode {
int data;
BinaryTreeNode *left;
BinaryTreeNode *right;
};
//创建二叉树
BinaryTreeNode* createBinaryTree() {
int data;
cin >> data;
if (data == 0) {
return NULL;
}
BinaryTreeNode *node = new BinaryTreeNode;
node->data = data;
node->left = createBinaryTree();
node->right = createBinaryTree();
return node;
}
//先序遍历二叉树
void preOrder(BinaryTreeNode *root) {
if (root != NULL) {
cout << root->data << " ";
preOrder(root->left);
preOrder(root->right);
}
}
//中序遍历二叉树
void inOrder(BinaryTreeNode *root) {
if (root != NULL) {
inOrder(root->left);
cout << root->data << " ";
inOrder(root->right);
}
}
//后序遍历二叉树
void postOrder(BinaryTreeNode *root) {
if (root != NULL) {
postOrder(root->left);
postOrder(root->right);
cout << root->data << " ";
}
}
//求二叉树深度
int depth(BinaryTreeNode *root) {
if (root == NULL) {
return 0;
} else {
int leftDepth = depth(root->left);
int rightDepth = depth(root->right);
return max(leftDepth, rightDepth) + 1;
}
}
//求二叉树叶子结点个数
int leafCount(BinaryTreeNode *root) {
if (root == NULL) {
return 0;
} else if (root->left == NULL && root->right == NULL) {
return 1;
} else {
return leafCount(root->left) + leafCount(root->right);
}
}
int main() {
BinaryTreeNode *root = createBinaryTree();
cout << "先序遍历:";
preOrder(root);
cout << endl;
cout << "中序遍历:";
inOrder(root);
cout << endl;
cout << "后序遍历:";
postOrder(root);
cout << endl;
cout << "二叉树深度:" << depth(root) << endl;
cout << "叶子结点个数:" << leafCount(root) << endl;
return 0;
}
```
示例输入:
```
1 2 4 0 0 5 0 0 3 6 0 0 7 0 0
```
示例输出:
```
先序遍历:1 2 4 5 3 6 7
中序遍历:4 2 5 1 6 3 7
后序遍历:4 5 2 6 7 3 1
二叉树深度:3
叶子结点个数:4
```
阅读全文