二叉排序树
二叉排序树
喜欢ctrl的cxk
发布于 2019-11-08 16:58:57
发布于 2019-11-08 16:58:57
代码可运行
运行总次数：0
代码可运行
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/weixin_42449444/article/details/86181257
题目描述:
输入一系列整数，建立二叉排序树，并进行前序，中序，后序遍历。
输入描述:
输入第一行包括一个整数n(1<=n<=100)。 接下来的一行包括n个整数。
输出描述:
可能有多组测试数据，对于每组数据，将题目所给数据建立一个二叉排序树，并对二叉排序树进行前序、中序和后序遍历。 每种遍历结果输出一行。每行最后一个数据之后有一个空格。
输入中可能有重复元素，但是输出的二叉树遍历序列中重复元素不用输出。
输入样例：
5
1 6 5 9 8输出样例：
1 6 5 9 8
1 5 6 8 9
5 8 9 6 1 相关知识：
1.先序遍历的递归过程为：若二叉树为空，遍历结束。否则：①访问根结点；②先序遍历根结点的左子树；③先序遍历根结点的右子树。 简单来说先序遍历就是在深入时遇到结点就访问。
2.中序遍历的递归过程为：若二叉树为空，遍历结束。否则：①中序遍历根结点的左子树；②访问根结点；③中序遍历根结点的右子树。简单来说中序遍历就是从左子树返回时遇到结点就访问。
3.后序遍历的递归过程为：若二叉树为空，遍历结束。否则：①后序遍历根结点的左子树；②后序遍历根结点的右子树；③访问根结点。简单来说后序遍历就是从右子树返回时遇到结点就访问。
AC代码：
#include <bits/stdc++.h>
using namespace std;
typedef struct TreeNode
{
int data;
TreeNode *lchild,*rchild;
}*Tree;
//插入构造平衡二叉树
void Insert(Tree &root,int x)
{
if(root == NULL)
{
//root = new TreeNode;
root = (Tree)malloc(sizeof(TreeNode));
root->data = x;
root->lchild = root->rchild = NULL;
}
else if(x < root->data)
{
Insert(root->lchild,x);
}
else if(x > root->data)
{
Insert(root->rchild,x);
}
}
//先序遍历
void Preorder(Tree bt)
{
if(bt)
{
printf("%d ", bt->data);
Preorder(bt->lchild);
Preorder(bt->rchild);
}
}
//中序遍历
void Inorder(Tree bt)
{
if(bt)
{
Inorder(bt->lchild);
printf("%d ", bt->data);
Inorder(bt->rchild);
}
}
//后序遍历
void Postorder(Tree bt)
{
if(bt)
{
Postorder(bt->lchild);
Postorder(bt->rchild);
printf("%d ", bt->data);
}
}
int main()
{
int n;
while(cin >> n && n)
{
int temp;
Tree T = NULL;
for (int i = 0; i < n; ++i)
{
cin >> temp;
Insert(T,temp);
}
Preorder(T);
cout << endl;
Inorder(T);
cout << endl;
Postorder(T);
cout << endl;
}
return 0;
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2019/01/09 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
