(1)编写二叉树的基本操作函数。 ①创建一棵二叉树 CreateBiTree(BiTree *T); ②先序遍历,递归方法 re_PreOrder(BiTree * tree ) ③中序遍历,递归方法 re_MidOrder(BiTree * tree ) ④后序遍历,递归方法 re_PostOrder(BiTree * tree ) (2)调用上述函数实现下列操作。 用递归方法分别先序、中序和后序遍历二叉树; 注意 要求动态显示二叉树的建立过程。
时间: 2024-02-13 18:02:56 浏览: 97
以下是基本操作函数的代码实现:
```c++
#include <iostream>
#include <cstdlib>
#include <queue>
using namespace std;
// 二叉树结构体定义
typedef struct BiTNode
{
char data; // 数据域
struct BiTNode *lchild, *rchild; // 左右子树指针
}BiTNode, *BiTree;
// 递归创建二叉树
void CreateBiTree(BiTree &T)
{
char ch;
cin >> ch;
if (ch == '#')
T = NULL;
else
{
T = new BiTNode;
T->data = ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
}
// 递归先序遍历
void re_PreOrder(BiTree T)
{
if (T != NULL)
{
cout << T->data << " ";
re_PreOrder(T->lchild);
re_PreOrder(T->rchild);
}
}
// 递归中序遍历
void re_MidOrder(BiTree T)
{
if (T != NULL)
{
re_MidOrder(T->lchild);
cout << T->data << " ";
re_MidOrder(T->rchild);
}
}
// 递归后序遍历
void re_PostOrder(BiTree T)
{
if (T != NULL)
{
re_PostOrder(T->lchild);
re_PostOrder(T->rchild);
cout << T->data << " ";
}
}
// 层序遍历
void levelOrder(BiTree T)
{
queue<BiTree> q;
if (T != NULL)
{
q.push(T);
}
while (!q.empty())
{
BiTree p = q.front();
q.pop();
cout << p->data << " ";
if (p->lchild != NULL)
q.push(p->lchild);
if (p->rchild != NULL)
q.push(p->rchild);
}
}
// 主函数
int main()
{
BiTree T;
CreateBiTree(T);
cout << "先序遍历:";
re_PreOrder(T);
cout << endl;
cout << "中序遍历:";
re_MidOrder(T);
cout << endl;
cout << "后序遍历:";
re_PostOrder(T);
cout << endl;
cout << "层序遍历:";
levelOrder(T);
cout << endl;
return 0;
}
```
在这个代码中,我们定义了一个二叉树结构体,并实现了二叉树的基本操作函数:创建二叉树、递归先序遍历、递归中序遍历、递归后序遍历。我们还实现了层序遍历函数,用于比较不同遍历方法的输出结果。
在主函数中,我们首先调用 CreateBiTree 函数创建一棵二叉树,然后依次调用不同的遍历函数输出遍历结果。最后,我们再次调用层序遍历函数输出二叉树的层序遍历结果。
在输出遍历结果时,我们可以看到每个节点的访问顺序,可以根据这个顺序验证遍历方法的正确性。同时,我们在程序中使用了递归算法,在实现上更为简单,易于理解。
至于要求动态显示二叉树的建立过程,这可以通过在 CreateBiTree 函数中添加一些输出语句来实现。例如,可以在每次递归调用前输出当前节点的值,这样就可以实现动态显示建树过程了。
阅读全文