软基上机实验报告-二叉树(拓展题)(共4页)

1、精选优质文档-倾情为你奉上 ex4_2扩展题1）实现二叉排序树的插入函数2）main函数中，输入一组无序数，调用二叉排序树插入算法，将元素放入二叉树中3）中序遍历这颗二叉树，得到排序顺序。ex4-3扩展题1）编写函数求一颗二叉树的深度2）求一颗二叉排序树的排序的反序结果，即将二叉排序树每个节点的左右子树交换，然后中序遍历之。1、 程序流程说明1.二叉树的插入算法（4-2）：在基本题中我已说明了二叉排序树的创建过程，基本原理就是先建立一个节点，然后通过数值大小的比较将节点拼接到这颗树上，故插入算法仅仅是将二叉排序树创建过程中的一个节点插入的部分取出来即可。2.求二叉树的深度及反序（4-3）：求二

2、叉树的深度：可以采用递归去做，首先从根节点开始，访问左子树，访问右子树，然后以相应的左右子树为根节点继续向下访问。每一次的向下访问将深度加一，然后返回左右子树中值较大的那一个。反序二叉树：仍然用递归去做，首先从根节点开始，将左右子树交换，然后以根节点的左右子树为根节点继续交换。 二、程序代码二叉树的插入算法：void enter(bnode *t,int x)bnode *p,*q;p=(bnode *)malloc(sizeof(bnode);p->lchild=NULL;p->rchild=NULL;p->data=x;if(*t=NULL)*t=p;elseq=*t;w

3、hile(q!=NULL)if(p->data<q->data)if(q->lchild!=NULL)q=q->lchild;elseq->lchild=p;q=NULL;break;elseif(q->rchild!=NULL)q=q->rchild;elseq->rchild=p;p=NULL;break; 求二叉树的深度以及反序：int deep(bnode *p)if(p=NULL)return 0;int i=1;int j=1;i=deep(p->lchild);j=deep(p->rchild);return (i

4、>j?i:j)+1;void opposite(bnode *p)if(p=NULL)return;bnode *h;h=p->lchild;p->lchild=p->rchild;p->rchild=h;if(p->lchild!=NULL)opposite(p->lchild);if(p->rchild!=NULL)opposite(p->rchild);三、测试数据4-2二叉树的插入算法：输入：Please input your tree0 to end:190 381 12 40 410 394 540 760 85 476 800

5、 146 9 445 0inorder is(before):9 12 40 85 146 190 381 394 410 445 476 540 760 800please input the numbers you want to input(use 0 to end):600输出：inorder is(after):9 12 40 85 146 190 381 394 410 445 476 540 600 760 8004-3二叉树的深度及反序输入：Please input your tree0 to end:190 381 12 40 410 394 540 760 85 476 8

6、00 146 9 445 600 0输出：inorder is:9 12 40 85 146 190 381 394 410 445 476 540 600 760 800the deepth is: 6after opposite the inorder is:800 760 600 540 476 445 410 394 381 190 146 85 40 12 9四、上机时遇到的问题1.问题现象： 插入元素时运行直接崩溃原因： 至今为止未找到原因解决办法： 突然想到可以用建立过程去解决，就截取了一部分建立函数过来2.问题现象： 求深度时当传入一个空二叉树时，运行崩溃原因：没有对空二叉树这种情况进行特殊的处理解决方法： 进行判断，当为空二叉树时返回0实际运行结果4-2二叉树的插入算法：求二叉树的深度及反序：5、 小结与体会1.这次实验让我对二叉树的创建过程有了一个全新的认识，也让我明白了其实树的创建过程无非就是一群插入过程的集合。2.同时经过了基础题加拓展题的训练，我发现了一些共通性，当一