二叉樹的插入排序

1、解題思路:1、采用二叉鏈表存儲結(jié)構(gòu)，中序遍歷二叉樹T的非遞歸算法；2、根指針進棧，遍歷左子樹后根指針退棧，遍歷右子樹；3、如果q不為空，且根結(jié)點值比左孩子的值小，則該二叉樹不是二 叉排序樹；若是根植大于左孩子，則將左孩子值出棧，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);/ 創(chuàng)建二叉鏈表PrintBiTree(rt);r = InOrderTraverse(rt);/ To do if(r=1)printf(這棵樹是二叉排序樹！ n); elseprintf(這棵樹不是二叉排序樹！ n);DestoryBiTree(rt); / 銷毀二叉鏈表 return 0;執(zhí)行結(jié)果： 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