对给出数值进行二叉搜索树排序,包括前序、中序、后序3种排列方式

第一篇：对给出数值进行二叉搜索树排序,包括前序、中序、后序3种排列方式

数据结构程序报告（2）

2011.3.29

2.需求分析：

（1）功能：对给出数值进行二叉搜索树排序，包括前序、中序、后序3种排列方式（2）输入输出要求：选择要进行的操作： 1新输入一组数并创建相应的二叉排序树 ○

2前序输出二叉排序树中所有的数 ○3中序输出二叉排序树中所有的数 ○4后序输出二叉排序树中所有的数 ○5按其它任意键退出 ○3.概要设计：（算法）

二叉搜索树的插入需要运用检索的方法，查找待插入关键码是否在树中，如果存在则不允许重复插入重复关键码，若直到找到叶结点还没发现关键码，则把新节点插入到待插入方向作为新的叶结点，二叉搜索树就是按照给定的关键码顺序动态插入而得到的。

深度优先周游二叉树分为3种方法，前序法按照根结点、左子树、右子树顺序；中序法按照左子树、根结点、右子树顺序；后序法按照左子树、右子树、根结点顺序，用递归实现对二叉树的深度优先周游。

4.详细设计：（具体方法）

首先创建一个结点Node的结构体包括：数据data，左孩子Lchild，右孩子Rchild，然后创建一个tree类，实现了以下功能：Print（）输出，Choose（）选择要进行的操作1-5依次是输入新数组、前序输出、中序输出、后续输出、退出，InsertBST（）创建一个新的二叉搜索树，PrintTree1（）前序输出，PrintTree2（）中序输出，PrintTree3（）后、序输出。

附程序：

#include using namespace std;

typedefstruct Node { int data;struct Node *Lchild;struct Node *Rchild;}BiNode,*BiTree;

class tree{ public: tree(){};void Print(BiTree *root){ int choice;cout<<“请选择你要的操作:”;cin>>choice;Choose(choice,root);};void Choose(intchoice,BiTree *root){

int i;int key;intnum;switch(choice)

{ case 1: cout<<“请输入二叉搜索树元素个数:”;cin>>num;cout<<“请输入二叉搜索树的元素:n”;for(i=0;i

{ cin>>key;InsertBST(root,key);

} break;case 2: PrintTree1(*root);cout<<“n”;break;case 3: PrintTree2(*root);cout<<“n”;

break;

case 4:

PrintTree3(*root);cout<<“n”;break;default: exit(0);

} };voidInsertBST(BiTree *root,int key){ BiTree s;

if(*root==NULL)//递归结束条件

{

s=(BiNode *)malloc(sizeof(BiNode));//申请新的节点 s->data=key;s->Lchild=NULL;s->Rchild=NULL;

(*root)=s;

} else if(key<(*root)->data)InsertBST(&((*root)->Lchild),key);//将s插入左子树 else if(key>(*root)->data)

InsertBST(&((*root)->Rchild),key);//将s插入右子树 };void PrintTree1(BiTree root){ if(root!=NULL){ cout<data;PrintTree1(root->Lchild);PrintTree1(root->Rchild);} };void PrintTree2(BiTree root){ if(root!=NULL){ PrintTree2(root->Lchild);cout<data;PrintTree2(root->Rchild);

} };void PrintTree3(BiTree root){ { PrintTree3(root->Lchild);if(root!=NULL)

PrintTree3(root->Rchild);

} };};//主函数 int main(){

tree c;BiTree root;

root=NULL;//初始化

cout<<“1.新输入一组数并创建相应的二叉搜索树.n”;cout<<“2.前序输出二叉搜索树中所有的数.n”;cout<<“3.中序输出二叉搜索树中所有的数.n”;cout<<“4.后序输出二叉搜索树中所有的数.n”;cout<<“5.按其它任意键退出.n”;c.Print(&root);while(true)

{ getchar();c.Print(&root);

} cout<data;

return 0;}

5．测试数据：

（1）请选择你要的操作：1 请输入二叉树搜索的元素个数：4 请输入二叉搜索树的元素： 4 2 5 7 请选择你要的操作：2 4257 请选择你要的操作：3 2457 请选择你要的操作：4 2754

（2）请选择你要的操作：1 请输入二叉树搜索的元素个数：5 请输入二叉搜索树的元素： 5 2 7 1 4 请选择你要的操作：2 42157 请选择你要的操作：3

12457 请选择你要的操作：4 12754

（3）请选择你要的操作：1 请输入二叉树搜索的元素个数：7 请输入二叉搜索树的元素： 5 2 7 1 3 6 9 请选择你要的操作：2 42135769 请选择你要的操作：3 12345679 请选择你要的操作：4 13269754

（4）请选择你要的操作：1 请输入二叉树搜索的元素个数：6 请输入二叉搜索树的元素： 4 3 7 9 6 2 请选择你要的操作：2 432769 请选择你要的操作：3

234679 请选择你要的操作：4 236974 测试截图：

6．总结：

程序调试中的问题及解决方法：在创建搜索树时算法是从书上借鉴的，进行了修改，对于二叉搜索树的检索，每一次只需与结点的一棵子树作比较。而在执行插入操作时，也不必像在有序线性表中插入元素需要移动大量的数据，只需改动某个结点的空指针插入一个叶结点即可，插入一个新结点操作的时间复杂度是根到插入位置的路径长度，因此在树形比较平衡时二叉搜索树的效率相当高。

心得体会：通过本题我认识到了二叉树的构建及排序的原理及应用，成功的编译出了可以实现功能的程序，总体来说程序不难，但好的算法很关键，因为二叉搜索树时间和空间复

杂度都要控制到相对小，才能迅速准确的计算出结果。

7．使用说明：

1新输入一组数并创建相应的二叉排序树 ○

2前序输出二叉排序树中所有的数 ○3中序输出二叉排序树中所有的数 ○4后序输出二叉排序树中所有的数 ○5按其它任意键退出 ○