当前位置:首页 C++ > 正文

题目:使用C++实现一个基于父结点表示法的二叉树,并实现二叉树的前序遍历、中序遍历和后序遍历算法。

作者::2023-05-02 20:16:59 C++阅读 2382

下面是一个基于父结点表示法的二叉树的实现,其中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
野牛程序员教少儿编程与信息学竞赛-微信|电话:15892516892
相关推荐

最新推荐

热门点击