使用二叉链表存储结构建立一棵二叉树,完成如下功能: 1.创建二叉树 2.先序遍历二叉树 3.中序遍历二叉树 4.后序遍历二叉树 5.求二叉树深度 6.求二叉树叶子结点个数
时间: 2023-11-14 12:17:15 浏览: 266
以下是使用二叉链表存储结构建立二叉树并实现各种功能的示例代码(使用 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
```
阅读全文