利用前序遍历建立二叉树
时间: 2023-10-22 19:29:56 浏览: 43
利用前序遍历构建二叉树的方法如下所示:
1. 首先定义一个结构体,结构体中包含一个字符类型的数据和两个指向左右子节点的指针。
2. 创建一个函数create_by_pre,该函数用于利用前序遍历构建二叉树。函数中首先读取一个字符ch,如果ch为"#",则表示当前节点为空,将其指针置为NULL;否则,创建一个新节点,并给节点的data赋值为ch。然后递归调用create_by_pre函数,将返回的指针赋值给新节点的左子节点指针,再次递归调用create_by_pre函数,将返回的指针赋值给新节点的右子节点指针。最后,返回构建的二叉树。
3. 创建前序遍历函数preOrder,用于按照前序遍历的顺序输出二叉树的节点。如果当前节点不为空,则先输出当前节点的数据,然后递归调用preOrder函数输出左子节点和右子节点。
4. 创建中序遍历函数inOrder,用于按照中序遍历的顺序输出二叉树的节点。如果当前节点不为空,则先递归调用inOrder函数输出左子节点,然后输出当前节点的数据,最后递归调用inOrder函数输出右子节点。
5. 创建后序遍历函数postOrder,用于按照后序遍历的顺序输出二叉树的节点。如果当前节点不为空,则先递归调用postOrder函数输出左子节点和右子节点,最后输出当前节点的数据。
6. 在主函数main中,首先创建一个空指针T,并通过调用create_by_pre函数利用前序遍历构建二叉树并将返回的指针赋值给T。然后分别调用preOrder、inOrder和postOrder函数输出前序遍历、中序遍历和后序遍历的结果。
代码中的包含了创建二叉树、前序遍历、中序遍历和后序遍历的函数。您可以在输入过程中根据需要添加节点的数据,然后通过调用相应的遍历函数输出二叉树的节点顺序。<span class="em">1</span>