该问题要求设计程序,利用二叉链表结构,建立一棵二叉树。并能递归实现二叉树的先序遍历、中序遍历和后序遍历三种遍历算法,能用队列实现二叉树的层次遍历算法,并按层次输出(标出层号),并能统计树叶数,结点数,层高等信息。
时间: 2023-10-08 19:10:56 浏览: 84
算法之二叉树的层序遍历(利用队列实现,需熟练手写)
5星 · 资源好评率100%
好的,我会提供一份C++的代码,实现该问题的要求。
首先,我们需要定义一个二叉树节点的结构体:
```c++
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
```
接下来,我们可以用递归方式实现先序、中序和后序遍历:
```c++
// 先序遍历
void preorderTraversal(TreeNode* root) {
if (root == nullptr) return;
cout << root->val << " ";
preorderTraversal(root->left);
preorderTraversal(root->right);
}
// 中序遍历
void inorderTraversal(TreeNode* root) {
if (root == nullptr) return;
inorderTraversal(root->left);
cout << root->val << " ";
inorderTraversal(root->right);
}
// 后序遍历
void postorderTraversal(TreeNode* root) {
if (root == nullptr) return;
postorderTraversal(root->left);
postorderTraversal(root->right);
cout << root->val << " ";
}
```
接下来,我们可以用队列实现层次遍历:
```c++
// 层次遍历
void levelTraversal(TreeNode* root) {
if (root == nullptr) return;
queue<TreeNode*> q;
q.push(root);
int level = 0;
while (!q.empty()) {
int size = q.size();
cout << "Level " << level << ": ";
for (int i = 0; i < size; i++) {
TreeNode* node = q.front();
q.pop();
cout << node->val << " ";
if (node->left != nullptr) q.push(node->left);
if (node->right != nullptr) q.push(node->right);
}
cout << endl;
level++;
}
}
```
最后,我们可以统计树叶数、结点数和层高:
```c++
// 统计树叶数
int countLeaves(TreeNode* root) {
if (root == nullptr) return 0;
if (root->left == nullptr && root->right == nullptr) return 1;
return countLeaves(root->left) + countLeaves(root->right);
}
// 统计结点数
int countNodes(TreeNode* root) {
if (root == nullptr) return 0;
return countNodes(root->left) + countNodes(root->right) + 1;
}
// 统计层高
int getHeight(TreeNode* root) {
if (root == nullptr) return 0;
int leftHeight = getHeight(root->left);
int rightHeight = getHeight(root->right);
return max(leftHeight, rightHeight) + 1;
}
```
接下来,我们可以实现建立二叉树的函数:
```c++
// 建立二叉树
TreeNode* buildTree() {
int val;
cin >> val;
if (val == -1) {
return nullptr;
}
TreeNode* node = new TreeNode(val);
node->left = buildTree();
node->right = buildTree();
return node;
}
```
最后,我们可以在main函数中调用这些函数来建立二叉树、遍历二叉树和统计信息:
```c++
int main() {
TreeNode* root = buildTree();
cout << "Preorder Traversal: ";
preorderTraversal(root);
cout << endl;
cout << "Inorder Traversal: ";
inorderTraversal(root);
cout << endl;
cout << "Postorder Traversal: ";
postorderTraversal(root);
cout << endl;
levelTraversal(root);
cout << "Number of Leaves: " << countLeaves(root) << endl;
cout << "Number of Nodes: " << countNodes(root) << endl;
cout << "Height of Tree: " << getHeight(root) << endl;
return 0;
}
```
这样,你就可以用这份代码来建立二叉树、遍历二叉树和统计信息了。
阅读全文