二叉树的插入排序_第1页
二叉树的插入排序_第2页
二叉树的插入排序_第3页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、解题思路:1、采用二叉链表存储结构，中序遍历二叉树T的非递归算法；2、根指针进栈，遍历左子树后根指针退栈，遍历右子树；3、如果q不为空，且根结点值比左孩子的值小，则该二叉树不是二 叉排序树；若是根植大于左孩子，则将左孩子值出栈，q=p，再访问右 孩子。二叉树的先序序列和中序序列的定义TElemType pre = 49, 38, 13, 27, 46, 65, 97, 76; TElemType in = 13, 27, 38, 46, 49, 65, 76, 97; int plen = sizeof(pre)/sizeof(pre0);int ilen = sizeof(in)/sizeo

2、f(in0);/ len取为0,要么是因为二叉树为空树，要么是/因为输入的先序序列和中序序列不等长int len = (plen = ilen) ? plen : 0;Status InOrderTraverse(BiTree T)/ To doLinkStack S;BiTree p,q=NULL;InitStack(S);p=T;while(p|!StackEmpty(S)if(p)Push(S,p);p=p-lchild;elsePop(S,p);if(q!=NULL&p-datadata )return ERROR;q=p;p=p-rchild;return OK;int main()

3、int r;BiTree rt = NULL; /初始化为空二叉树CreateBiTree(rt);/ 创建二叉链表PrintBiTree(rt);r = InOrderTraverse(rt);/ To do if(r=1)printf(这棵树是二叉排序树！ n); elseprintf(这棵树不是二叉排序树！ n);DestoryBiTree(rt); / 销毁二叉链表 return 0;执行结果： C:W i nd owsSystem 3De bu gC p pl. exePpeordep： 49 38 13 27 46 65 97 76Inorder： 13 27 38 46 49 6

4、5 76 97Ppeorder： 27 13 46 38 76 97 65 49 13 2727 3838 4646 49549 6557697棵树是二叉排序树！*ress any key to continue -C:WindowsSystem32DebugCppl.exe*Ppeopdep： 49 27 13 65 76 46 97 38Inopdep： 13 65 27 76 49 46 38 97Ppeopdep： &5 13 76 27 38 97 46 49 13 &565 27这棵树不是二叉排序树！Pi-e&s any key to continue *C:WindowsSystem32Debug ppl.exe*Pi*e o i*d.e

人人文库> 全部分类> 行业资料 > 机电工程

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论