数据结构_二叉排序树
概念
二叉排序树是一颗特殊的二叉树,它是一颗二叉树但同时满足如下条件:对于树上的任意一个结点,其上的数值必大于等于其左子树上任意结点数值,必小于等于其右子树上任意结点的数值。
由于各个数字插入的顺序不同,所得到的二叉排序树的形态也很可能不同,所以不同的插入顺序对二叉排序树的形态有重要的影响,但其都有一个共同点:若对二叉排序树进行中序遍历,那么其遍历结果必然是一个递增序列,所以通过建立二叉排序树就能对原无需序列进行排序,并实现动态维护。
例3.5 二叉排序树 (1201)
题目描述:输入一系列整数,建立二叉排序数,并进行前序,中序,后序遍历。
输入:输入第一行包括一个整数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
#include<stdio.h> #include<string.h> using namespace std; struct Node{ Node *lchild; Node *rchild; int x; }Tree[]; int loc; Node *create(){ Tree[loc].lchild=Tree[loc].rchild=NULL; return &Tree[loc++]; } void preOrder(Node *T){ printf("%d ",T->x); if(T->lchild) preOrder(T->lchild); if(T->rchild) preOrder(T->rchild); } void postOrder(Node *T){ if(T->lchild) postOrder(T->lchild); if(T->rchild) postOrder(T->rchild); printf("%d ",T->x); } void inOrder(Node *T){ if(T->lchild) inOrder(T->lchild); printf("%d ",T->x); if(T->rchild) inOrder(T->rchild); } Node *insert(Node *T,int y){ if(T==NULL){ T=create(); T->x=y; return T; } else if(y>T->x) T->rchild=insert(T->rchild,y); else T->lchild=insert(T->lchild,y); return T; } int main(){ int n; while(scanf("%d",&n)!=EOF){ Node *T=NULL; loc=; while(n--){ int t; scanf("%d",&t); T=insert(T,t); } preOrder(T); printf("\n"); inOrder(T); printf("\n"); postOrder(T); printf("\n"); } return ; }
相关推荐
Dyancsdn 2020-06-28
路漫 2020-06-28
tulensa 2020-06-28
前驱为104,需要注意的是他的前驱只有两种可能:为叶子结点或,或者只有左子树。所以删除一个结点时有两种方法:用前驱或后继的数据覆盖删除点的数据,用前驱的左子树接到前驱位置上,或用后继的右子树接到后继上
roseying 2020-05-11
范范 2019-12-27
RikkaTakanashi 2019-11-27
hanyujianke 2019-11-06