题目:使用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