编写二叉树的创建及遍历方法
时间: 2023-12-12 16:03:51 浏览: 23
非常感谢您的提问!关于二叉树的创建和遍历方法,我可以详细地为您介绍。
二叉树是一种树形结构,它的每个节点最多只有两个子节点。二叉树通常用于数据搜索和排序,因为在二叉树中查找和插入的速度非常快。
要创建一个二叉树,首先需要定义二叉树节点的结构,包括数据成员和指针。
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
其中,val 表示节点的值,left 和 right 分别指向左右子节点。
然后,可以使用递归的方式创建二叉树。代码如下:
TreeNode* createTree() {
int val;
cin >> val;
if (val == -1)
return NULL;
TreeNode* root = new TreeNode(val);
root->left = createTree();
root->right = createTree();
return root;
}
这里使用 -1 表示空节点,如果输入的值是 -1,则返回空节点。
遍历二叉树有三种方式:前序遍历、中序遍历和后序遍历。它们的区别在于遍历的顺序不同。
前序遍历先遍历根节点,然后遍历左子树,最后遍历右子树。代码如下:
void preOrder(TreeNode* root) {
if (!root)
return;
cout << root->val << " ";
preOrder(root->left);
preOrder(root->right);
}
中序遍历先遍历左子树,然后遍历根节点,最后遍历右子树。代码如下:
void inOrder(TreeNode* root) {
if (!root)
return;
inOrder(root->left);
cout << root->val << " ";
inOrder(root->right);
}
后序遍历先遍历左子树,然后遍历右子树,最后遍历根节点。代码如下:
void postOrder(TreeNode* root) {
if (!root)
return;
postOrder(root->left);
postOrder(root->right);
cout << root->val << " ";
}
以上就是关于二叉树创建和遍历的介绍,希望能对您有所帮助!