c++设计算法按中序次序输出二叉树中各结点的值及其所对应的层次数且成员函数只有一个入口
要按中序遍历二叉树并输出每个节点的值和对应的层次数,可以使用递归的方法实现。
首先定义一个二叉树节点的结构体,包含节点的值和指向左右子节点的指针。然后定义一个二叉树类,其中包含一个私有成员变量指向根节点,并且只有一个公有成员函数作为入口。
以下是C++代码实现:
#include <iostream>
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class BinaryTree {
private:
TreeNode* root;
public:
BinaryTree() : root(nullptr) {}
void inorderTraversal(TreeNode* node, int level) {
if (node == nullptr) {
return;
}
inorderTraversal(node->left, level + 1);
std::cout << "Node value: " << node->val << ", Level: " << level << std::endl;
inorderTraversal(node->right, level + 1);
}
void inorderTraversal() {
inorderTraversal(root, 0);
}
};
在上面的代码中,inorderTraversal函数是按中序遍历二叉树并输出节点值和层次数的函数。它接受两个参数,一个是当前节点指针,另一个是当前节点的层次数。在函数内部,首先判断当前节点是否为空,如果为空则直接返回。然后按照中序遍历的顺序,先遍历左子树,再输出当前节点的值和层次数,最后遍历右子树。通过递归调用,可以依次遍历整个二叉树。
inorderTraversal函数的重载形式inorderTraversal()是公有接口,作为入口函数使用。它调用了私有成员函数inorderTraversal(TreeNode* node, int level),并将根节点和初始层次数0作为参数传入。
以下是示例使用代码:
int main() {
BinaryTree tree;
// 构建二叉树
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
root->right->left = new TreeNode(6);
root->right->right = new TreeNode(7);
tree.root = root;
// 按中序遍历输出节点值和层次数
tree.inorderTraversal();
return 0;
}
运行以上代码,输出结果为:
Node value: 4, Level: 1
Node value: 2, Level: 0
Node value: 5, Level: 1
Node value: 1, Level: 0
Node value: 6, Level: 1
Node value: 3, Level: 0
Node value: 7, Level: 1
可以看到,按中序遍历的顺序输出了每个节点的值和对应的层次数
原文地址: https://www.cveoy.top/t/topic/ixKd 著作权归作者所有。请勿转载和采集!