主要内容 #
- 二叉排序树知识点回顾
- 二叉排序树习题练习
1. 二叉排序树知识点回顾 #
二叉排序树本质是一棵二叉树,它的特别之处在于:
- 对于树中的每个结点,如果它有左子树,那么左子树上所有结点的值都比该结点小;
- 对于树中的每个结点,如果它有右子树,那么右子树上所有结点的值都比该结点大。
举个简单的例子,下图就是一棵二叉排序树:
以根节点为例,左子树上所有结点的值都比 45小,右子树上所有结点的值都比 45大。不仅是根结点,整棵二叉树上的非叶子结点都是如此,这样的二叉树就是一棵二叉排序树。
2. 二叉排序树习题练习 #
2.1 题目描述:
输入一系列整数,建立二叉排序数,并进行前序,中序,后序遍历。
2.2 输入:
输入第一行包括一个整数 n(1<=n<=100)。接下来的一行包括 n 个整数。 2.3 输出: 可能有多组测试数据,对于每组数据,将题目所给数据建立一个二叉排序树, 并对二叉排序树进行前序、中序和后序遍历。每种遍历结果输出一行。每行最后 一个数据之后有一个空格。
2.4 样例输入:
5
1 6 5 9 8
2.5 样例输出:
1 6 5 9 8
1 5 6 8 9
5 8 9 6 1
2.6 提示:
输入中可能有重复元素,但是输出的二叉树遍历序列中重复元素不用输出。
2.7 示例程序:
#include<stdio.h> #include<string.h> struct Node{ //二叉树结构体 Node *lchild; //左儿子指针 Node *rchild; //右儿子指针 int c; //保存数字 }Tree[110]; //静态数组 int loc; //静态数组中被使用元素个数 Node *creat() //申请未使用的结点 { Tree[loc].lchild=Tree[loc].rchild=NULL;//初始化左右儿子为空 return &Tree[loc++];//返回指针,且loc累加 } void postOrder(Node *T) //后序遍历 { if(T->lchild!=NULL) { postOrder(T->lchild); } if(T->rchild!=NULL) { postOrder(T->rchild); } printf("%d ",T->c); } void inOrder(Node *T) //中序遍历 { if(T->lchild!=NULL) { inOrder(T->lchild); } printf("%d ",T->c); if(T->rchild!=NULL) { inOrder(T->rchild); } } void preOrder(Node *T) //前序遍历 { printf("%d ",T->c); if(T->lchild!=NULL) { preOrder(T->lchild); } if(T->rchild!=NULL) { preOrder(T->rchild); } } Node *Insert(Node *T,int x)//插入数字 { if(T==NULL) //若当前树为空 { T=creat(); //建立结点 T->c=x; //数字直接插入其根结点 return T; //返回根结点指针 } else if(x<T->c) //若x小于根结点数值 { T->lchild=Insert(T->lchild,x);//插入到左子树上 } else if(x>T->c) //若x大于根结点数值 { T->rchild=Insert(T->rchild,x);//插入到右子树上,若根结点数值与x一样,根据题目要求直接忽略 } return T; //返回根结点指针 } int main() { int n; while(scanf("%d",&n)!=EOF) { loc=0; Node *T=NULL; //二叉排序树树根结点为空 for(int i=0;i<n;i++)//依次输入n个数字 { int x; scanf("%d",&x); T=Insert(T,x);//插入到排序树中 } preOrder(T); //前序遍历 printf("\n"); //输出空行 inOrder(T); //中序遍历 printf("\n"); postOrder(T); //后序遍历 printf("\n"); } return 0; }