能够根据指定序列(例如先序序列)创建二叉树和实现二叉树的先序、中序、后序遍历算法,并在主函数中调用函数遍历输出1中创建的二叉树。的运行结果,实验思路和结论
时间: 2024-03-23 15:39:28 浏览: 67
好的,我理解了你的问题。以下是回答:
实验思路:
1. 首先,我们需要定义二叉树的结构体,包含数据域和指向左右子树的指针。
2. 根据指定的序列建立二叉树,可以采用递归的方法。
3. 实现二叉树的先序、中序、后序遍历算法,同样采用递归的方法。
4. 在主函数中调用以上函数,遍历输出创建的二叉树。
实验代码:
```c++
#include<iostream>
using namespace std;
struct TreeNode
{
char data;
TreeNode *left;
TreeNode *right;
};
void CreateBinaryTree(TreeNode *&T, char *preOrder, char *inOrder, int len);
void PreOrder(TreeNode *T);
void InOrder(TreeNode *T);
void PostOrder(TreeNode *T);
int main()
{
char preOrder[] = {'A', 'B', 'D', 'E', 'C', 'F', 'G'};
char inOrder[] = {'D', 'B', 'E', 'A', 'F', 'C', 'G'};
TreeNode *root = NULL;
CreateBinaryTree(root, preOrder, inOrder, sizeof(preOrder) / sizeof(preOrder[0]));
cout << "先序遍历结果:";
PreOrder(root);
cout << endl;
cout << "中序遍历结果:";
InOrder(root);
cout << endl;
cout << "后序遍历结果:";
PostOrder(root);
cout << endl;
return 0;
}
void CreateBinaryTree(TreeNode *&T, char *preOrder, char *inOrder, int len)
{
if (len <= 0)
{
T = NULL;
return;
}
T = new TreeNode;
T->data = *preOrder;
T->left = NULL;
T->right = NULL;
int rootIndex = 0;
while (rootIndex < len && *(inOrder + rootIndex) != *preOrder)
{
rootIndex++;
}
CreateBinaryTree(T->left, preOrder + 1, inOrder, rootIndex);
CreateBinaryTree(T->right, preOrder + rootIndex + 1, inOrder + rootIndex + 1, len - rootIndex - 1);
}
void PreOrder(TreeNode *T)
{
if (T == NULL)
{
return;
}
cout << T->data << " ";
PreOrder(T->left);
PreOrder(T->right);
}
void InOrder(TreeNode *T)
{
if (T == NULL)
{
return;
}
InOrder(T->left);
cout << T->data << " ";
InOrder(T->right);
}
void PostOrder(TreeNode *T)
{
if (T == NULL)
{
return;
}
PostOrder(T->left);
PostOrder(T->right);
cout << T->data << " ";
}
```
实验结论:
通过以上代码实现了根据指定序列创建二叉树并实现了二叉树的先序、中序、后序遍历算法。在主函数中调用以上函数,输出了创建的二叉树的遍历结果。
阅读全文