创建二叉树和实现二叉树的三种遍历a. 根据提示输入字符型数据创建二叉树,输入值为所有字符型数据b. 输出为遍历后的每个结点的值的顺序c. 创建二叉树并能实现二叉树的先序、中序、后序遍历
时间: 2023-10-25 13:02:49 浏览: 140
a. 根据提示输入字符型数据创建二叉树,输入值为所有字符型数据:
创建二叉树的步骤如下:
1. 定义一个指向二叉树结点的指针root,并初始化为空。
2. 依次输入字符型数据,并为每个数据创建一个新的结点。
3. 将第一个输入的数据作为根结点的值,将root指针指向根结点。
4. 依次输入其他数据,并找到合适的位置将其插入到二叉树中,保证二叉树的有序性。具体插入过程为,从根结点开始,如果当前结点的值小于插入值,则将结点移动到右子树进行判断;如果当前结点的值大于等于插入值,则将结点移动到左子树进行判断,直到找到合适的位置插入新结点。
b. 输出为遍历后的每个结点的值的顺序:
遍历二叉树的顺序有先序遍历、中序遍历和后序遍历三种。用递归方式实现这三种遍历的伪代码如下:
先序遍历:
preOrder(root):
if root is null:
return
输出(root的值)
preOrder(root的左子树)
preOrder(root的右子树)
中序遍历:
inOrder(root):
if root is null:
return
inOrder(root的左子树)
输出(root的值)
inOrder(root的右子树)
后序遍历:
postOrder(root):
if root is null:
return
postOrder(root的左子树)
postOrder(root的右子树)
输出(root的值)
c. 创建二叉树并能实现二叉树的先序、中序、后序遍历:
根据问题a中的方法创建二叉树,然后依次调用preOrder(root)、inOrder(root)和postOrder(root)函数可以实现二叉树的先序、中序、后序遍历。每次遍历输出的结果即为遍历后的每个节点的值的顺序。
阅读全文