题目:使用C++实现一个基于父结点表示法的二叉树,并实现二叉树的前序遍历、中序遍历和后序遍历算法。
作者::2023-05-02 20:16:59 C++阅读 2858
下面是一个基于父结点表示法的二叉树的实现,其中TreeNode结构体表示树中的一个结点:
#include<iostream>
#include<vector>
using namespace std;
// 二叉树结点的定义
struct TreeNode {
int val; // 结点的值
int left_child; // 左子结点的下标
int right_child; // 右子结点的下标
};
class BinaryTree {
private:
vector<TreeNode> tree; // 存储二叉树的数组
// 前序遍历,递归实现
void preOrder(int root) {
if (root == -1) return; // 如果根结点不存在,直接返回
cout << tree[root].val << " "; // 输出根结点的值
preOrder(tree[root].left_child); // 遍历左子树
preOrder(tree[root].right_child); // 遍历右子树
}
// 中序遍历,递归实现
void inOrder(int root) {
if (root == -1) return; // 如果根结点不存在,直接返回
inOrder(tree[root].left_child); // 遍历左子树
cout << tree[root].val << " "; // 输出根结点的值
inOrder(tree[root].right_child); // 遍历右子树
}
// 后序遍历,递归实现
void postOrder(int root) {
if (root == -1) return; // 如果根结点不存在,直接返回
postOrder(tree[root].left_child); // 遍历左子树
postOrder(tree[root].right_child); // 遍历右子树
cout << tree[root].val << " "; // 输出根结点的值
}
public:
// 构造函数
BinaryTree() {}
// 插入结点
void insertNode(int val, int parent) {
TreeNode node = {val, -1, -1}; // 创建一个新的结点
if (tree.empty()) { // 如果二叉树为空
tree.push_back(node); // 把新结点作为根结点
} else {
if (parent == -1) { // 如果父结点不存在
cout << "Parent does not exist!" << endl;
return;
}
if (tree[parent].left_child == -1) { // 如果父结点的左子树为空
tree[parent].left_child = tree.size(); // 把新结点作为左子结点
tree.push_back(node); // 把新结点插入到数组中
} else if (tree[parent].right_child == -1) { // 如果父结点的右子树为空
tree[parent].right_child = tree.size(); // 把新结点作为右子结点
tree.push_back(node); // 把新结点插入到数组中
} else {
cout << "Parent has two children!" << endl;
}
}
}
// 前序
void preOrderTraversal() {
preOrder(0); // 从根结点开始遍历
cout << endl;
}
// 中序遍历
void inOrderTraversal() {
inOrder(0); // 从根结点开始遍历
cout << endl;
}
// 后序遍历
void postOrderTraversal() {
postOrder(0); // 从根结点开始遍历
cout << endl;
}
};
int main() {
BinaryTree tree; // 创建一个二叉树对象
tree.insertNode(1, -1); // 插入根结点
tree.insertNode(2, 0); // 插入左子结点
tree.insertNode(3, 0); // 插入右子结点
tree.insertNode(4, 1); // 插入左子结点的左子结点
tree.insertNode(5, 1); // 插入左子结点的右子结点
tree.insertNode(6, 2); // 插入右子结点的左子结点
tree.insertNode(7, 2); // 插入右子结点的右子结点
// 测试前序遍历
cout << "Pre-order traversal: ";
tree.preOrderTraversal();
// 测试中序遍历
cout << "In-order traversal: ";
tree.inOrderTraversal();
// 测试后序遍历
cout << "Post-order traversal: ";
tree.postOrderTraversal();
return 0;
}以上就是基于父结点表示法的二叉树的实现,包括插入结点、前序遍历、中序遍历和后序遍历算法的实现。孩子们可以通过阅读程序注释来理解代码的含义,并可以直接编译运行程序进行测试。
野牛程序员教少儿编程与信息学奥赛-微信|电话:15892516892

