数据结构c/c++语言,分文件编写程序:二叉树的基本操作及应用 ①创建二叉树 ②遍历二叉树(先序、中序、后序) ③计算叶子结点个数及树的深度 ④查找指定结点的双亲 ⑤查找指定结点的兄弟(要求是输入命令式)
时间: 2024-02-28 08:56:45 浏览: 53
好的,我可以为你提供一个基本的C++实现,分为头文件和源文件两部分:
二叉树头文件 BinaryTree.h:
```c++
#ifndef BINARY_TREE_H
#define BINARY_TREE_H
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class BinaryTree {
public:
BinaryTree();
~BinaryTree();
void createTree(TreeNode*& root);
void preorderTraversal(TreeNode* root);
void inorderTraversal(TreeNode* root);
void postorderTraversal(TreeNode* root);
int countLeafNodes(TreeNode* root);
int getDepth(TreeNode* root);
TreeNode* getParent(TreeNode* root, int val);
TreeNode* getSibling(TreeNode* root, int val);
private:
void destroyTree(TreeNode* root);
};
#endif
```
二叉树源文件 BinaryTree.cpp:
```c++
#include "BinaryTree.h"
#include <iostream>
using namespace std;
BinaryTree::BinaryTree() {}
BinaryTree::~BinaryTree() {}
void BinaryTree::createTree(TreeNode*& root) {
int val;
cin >> val;
if (val == -1) {
root = nullptr;
}
else {
root = new TreeNode(val);
createTree(root->left);
createTree(root->right);
}
}
void BinaryTree::preorderTraversal(TreeNode* root) {
if (root) {
cout << root->val << " ";
preorderTraversal(root->left);
preorderTraversal(root->right);
}
}
void BinaryTree::inorderTraversal(TreeNode* root) {
if (root) {
inorderTraversal(root->left);
cout << root->val << " ";
inorderTraversal(root->right);
}
}
void BinaryTree::postorderTraversal(TreeNode* root) {
if (root) {
postorderTraversal(root->left);
postorderTraversal(root->right);
cout << root->val << " ";
}
}
int BinaryTree::countLeafNodes(TreeNode* root) {
if (!root) {
return 0;
}
if (!root->left && !root->right) {
return 1;
}
return countLeafNodes(root->left) + countLeafNodes(root->right);
}
int BinaryTree::getDepth(TreeNode* root) {
if (!root) {
return 0;
}
int leftDepth = getDepth(root->left);
int rightDepth = getDepth(root->right);
return max(leftDepth, rightDepth) + 1;
}
TreeNode* BinaryTree::getParent(TreeNode* root, int val) {
if (!root) {
return nullptr;
}
if ((root->left && root->left->val == val) || (root->right && root->right->val == val)) {
return root;
}
TreeNode* left = getParent(root->left, val);
TreeNode* right = getParent(root->right, val);
if (left) {
return left;
}
if (right) {
return right;
}
return nullptr;
}
TreeNode* BinaryTree::getSibling(TreeNode* root, int val) {
if (!root) {
return nullptr;
}
TreeNode* parent = getParent(root, val);
if (!parent) {
return nullptr;
}
if (parent->left && parent->left->val == val) {
return parent->right;
}
if (parent->right && parent->right->val == val) {
return parent->left;
}
return nullptr;
}
void BinaryTree::destroyTree(TreeNode* root) {
if (root) {
destroyTree(root->left);
destroyTree(root->right);
delete root;
}
}
```
使用示例:
```c++
#include "BinaryTree.h"
int main() {
BinaryTree tree;
TreeNode* root = nullptr;
tree.createTree(root);
cout << "preorder traversal: ";
tree.preorderTraversal(root);
cout << endl;
cout << "inorder traversal: ";
tree.inorderTraversal(root);
cout << endl;
cout << "postorder traversal: ";
tree.postorderTraversal(root);
cout << endl;
cout << "leaf nodes: " << tree.countLeafNodes(root) << endl;
cout << "depth: " << tree.getDepth(root) << endl;
cout << "parent of 5: " << tree.getParent(root, 5)->val << endl;
cout << "sibling of 5: " << tree.getSibling(root, 5)->val << endl;
tree.destroyTree(root);
return 0;
}
```
注意:以上代码只是一个基本实现,可能存在一些不足之处,需要根据具体情况进行修改和优化。
阅读全文