数据结构二叉排序树的实现 (用顺序和二叉链表作存储结构 )课程设计

ptr=NULL;

else if(ptr->rr()==NULL) ptr=ptr->rl(); else

ptr=ptr->rr(); } private: int data;

node *left; //左孩子结点 node *right; //右孩子结点 }; int main() { int t,i=0,j;

cout<<\ 10计科一班 杨 旭（1010311114）\ cout<<\二叉排序树T的输入:\ cout<<\输入数字个数(结点个数):\ cin>>t;

cout<<\输入\个数字，数字之间用空格隔开:\ cin>>j;

node *x=new node(j);

for(;i>j; x->insert(x,j); }

cout<<\中序遍历为:\

x->inorder(x); //作中序遍历 cout<<\

cout<<\二叉排序树T的元素查找和删除:\ cout<<\输入操作(当输入-1时程序结束):\ cin>>j; while(j!=-1) {

node *t=x->find(x,j); //定位结点 if(t!=NULL) {

node *&y=x->findy(x,j); x->dele(y); cout<<\中序遍历为:\ x->inorder(x); }

else cout<<\无\

cout<<\输入操作(当输入-1时程序结束):\ cin>>j; } return 0; }

七、运行结果

输入节点数

输入二叉树数，并输出中序遍历

当输入25时，二叉树中无该数据，输出无25

输入-1表示退出

八、时间复杂度分析

1、 查找函数最坏的情况是要找的点正好是二叉树的最深的叶子结点，此时时间复杂度＝O（n）。 2、 插入函数最坏的情况是要插入的点正是二叉树的最深的那一支的叶子