數(shù)據(jù)結(jié)構(gòu)第六章一二次作業(yè)

1、上機(jī)題（1）編寫完整程序，用先序遍歷法建立二叉樹的二叉鏈表存儲結(jié)構(gòu)。輸出該二叉樹的先、中、后序遍歷結(jié)點(diǎn)訪問次序以及層次遍歷結(jié)點(diǎn)訪問次序。（建議結(jié)點(diǎn)數(shù)據(jù)域類型為char）/ erchashu.cpp : Defines the entry point for the console application./#include stdafx.h#include#includetypedef struct node char data; struct node *lchild, *rchild; *BiT, BiTNode;BiT crtBT() char ch; BiT bt; ch=getcha

2、r(); if(ch=#) return NULL; bt=new BiTNode(); bt-data=ch; bt-lchild=crtBT(); bt-rchild=crtBT(); return bt; void preorder(BiT bt) if(bt) printf(%c,bt-data); preorder(bt-lchild); preorder(bt-rchild); /printf(n);void midorder(BiT bt) if(bt) midorder(bt-lchild); printf(%c,bt-data); midorder(bt-rchild); /

3、printf(n);void lasorder(BiT bt) if(bt) lasorder(bt-lchild); lasorder(bt-rchild); printf(%c,bt-data); /printf(n);int main(int argc, char* argv) BiT bt;bt=crtBT(); preorder(bt);printf(n);midorder(bt);printf(n);lasorder(bt);printf(n); return 0;（2)從鍵盤輸入n個數(shù)據(jù)建立n元完全二叉樹順序存儲結(jié)構(gòu)。實現(xiàn)該完全二叉樹的先、中、后序遍歷。#include stda

4、fx.h#include#includevoid preorder(int j,int i,char *s) if (ji) return; printf(%c,sj); preorder(j*2+1,i,s); preorder(j*2+2,i,s); void midorder(int j,int i,char *s) if (ji) return; preorder(j*2+1,i,s); printf(%c,sj); preorder(j*2+2,i,s); void lasorder(int j,int i,char *s) if (ji) return; preorder(j*2+

5、1,i,s); preorder(j*2+2,i,s); printf(%c,sj);int main(int argc, char* argv) int i=0; char *bt;char s100;scanf(%s,s);bt=s;while(si!=0) i+;/printf(%dn,i); preorder(0,i,bt);printf(n);midorder(0,i,bt);printf(n);lasorder(0,i,bt);printf(n); return 0;算法（1）已知二叉樹（二叉鏈表）根結(jié)點(diǎn)指針為bt，求該二叉樹中的葉子數(shù)目。int preorder(BiT bt)i

6、nt k=0; if(bt) if(!bt-lchild&!bt-rchild) k+; preorder(bt-lchild); preorder(bt-rchild); return k;（2）已知某二叉樹（三叉鏈表）的根結(jié)點(diǎn)地址root，該樹中各結(jié)點(diǎn)的左、右兒子指針域已正確填充，寫一個算法將所有結(jié)點(diǎn)的雙親指針域正確填充。void preorder(BiT bt)if(bt=root) return ; if(bt) bt-lchild-parent=bt; bt-rchild-parent=bt; preorder(bt-lchild); preorder(bt-rchild); （3）

7、已知某二叉樹（二叉鏈表）的根結(jié)點(diǎn)指針bt。編寫算法，將該二叉樹中所有結(jié)點(diǎn)的左右子樹互換。void preorder(BiT bt)char c; if(bt) c=bt-lchild;bt-lchild=bt-rchild; bt-rchild=c; preorder(bt-lchild); preorder(bt-rchild); (4) 已知n個結(jié)點(diǎn)的完全二叉樹結(jié)點(diǎn)數(shù)據(jù)域值按結(jié)點(diǎn)編號次序順序存于一維數(shù)組（元素下標(biāo)范圍0.n-1）。編寫算法，由該數(shù)組首地址以及數(shù)組長度n建立對應(yīng)的二叉鏈表存儲結(jié)構(gòu)。void preorder(BiT bt,int n,char *s,int j) if(bt)

8、 bt-lchild=s2*j+1; bt-rchild=s2*j+2; preorder(bt-lchild); preorder(bt-rchild); /*調(diào)用方式數(shù)組：chn;s=ch;j=0;preorder(BiT bt,int n ,char *s,int j)*/上機(jī)題（1）編寫完整程序，實現(xiàn)中序遍歷線索二叉樹存儲結(jié)構(gòu)、線索化以及中序遍歷。#include stdafx.h#include#includeenum PT LINK, THREAD ; typedef struct node char data;struct node *lchild, *rchild;enum P

9、T ltag, rtag; *SBiT, SBiT_Node;SBiT crtSBT()char ch; SBiT bt; ch=getchar(); if(ch=#) return NULL; bt=new SBiT_Node(); bt-data=ch; bt-lchild=crtSBT(); bt-rchild=crtSBT(); return bt; SBiT first(SBiT bt) while(bt&bt-ltag=LINK) bt=bt-lchild;return bt;/SBiT next(SBiT p) if(p-rtag=THREAD) return p-rchild;

10、 return first(p-rchild); void midtravel(SBiT p,SBiT root) p=first(root);while(p) printf(%c,p-data); p=next(p); void mit(SBiT bt, SBiT &pr) if(bt) mit(bt-lchild, pr);if(pr) if(pr-rchild) pr-rtag=LINK;else pr-rtag=THREAD; pr-rchild=bt; if(bt-lchild) bt-ltag=LINK;else bt-ltag=THREAD; bt-lchild=pr; pr=b

11、t;mit(bt-rchild, pr);int main(int argc, char* argv) SBiT bt;bt=crtSBT();SBiT pr=NULL;mit(bt, pr);pr-rtag=THREAD;midtravel(pr,pr);printf(n); return 0;(2) 編寫完整程序，用堆棧實現(xiàn)前/中/后序非遞歸遍歷，并與遞歸遍歷結(jié)果比較。#include#includetypedef struct Nodechar data; Node *leftchild; Node *rightchild;Node;/* 初始化一棵二叉樹排序樹。*/void InitB

12、inaryTree(Node*root,char elem) *root=(Node*)malloc(sizeof(Node); if(!(*root) printf(Memory allocation for root failed.n); return; (*root)-data=elem; (*root)-leftchild=NULL; (*root)-rightchild=NULL;/* 向二叉樹排序樹中插入結(jié)點(diǎn)。*/void InsertNode(Node *root,char elem) Node *newnode=NULL; Node *p=root,*last_p=NULL;

13、newnode=(Node*)malloc(sizeof(Node); if(!newnode) printf(Memory allocation for newnode failed.n); return; newnode-data=elem; newnode-leftchild=NULL; newnode-rightchild=NULL; while(NULL!=p) last_p=p; if(newnode-datadata) p=p-leftchild; else if(newnode-datap-data) p=p-rightchild; else printf(Node to be

14、 inserted has existed.n); free(newnode); return; p=last_p; if(newnode-datadata) p-leftchild=newnode; else p-rightchild=newnode; /* 創(chuàng)建一棵二叉樹排序樹。*/void CreatBinarySearchTree(Node *root,char data,int num) int i; for(i=0;idata); PreOrderRec(root-leftchild); PreOrderRec(root-rightchild); /* 前序遍歷二叉樹，非遞歸方法。

15、*/void PreOrderNoRec(Node *root)printf(非遞歸方法：); Node *p=root; Node *stack30; int num=0; while(NULL!=p|num0) while(NULL!=p) printf(%c ,p-data); stacknum+=p; p=p-leftchild; num-; p=stacknum; p=p-rightchild; printf(n);/* 中序遍歷二叉樹，遞歸方法。*/void InOrderRec(Node *root) if(NULL!=root) InOrderRec(root-leftchil

16、d); printf(%c ,root-data); InOrderRec(root-rightchild); /* 中序遍歷二叉樹，非遞歸方法，使用棧。*/void InOrderNoRec(Node *root)printf(非遞歸方法：); Node *p=root; int num=0; Node *stack30; while(NULL!=p|num0) while(NULL!=p) stacknum+=p; p=p-leftchild; num-; p=stacknum; printf(%c ,p-data); p=p-rightchild; printf(n);/* 后序遍歷二叉

17、樹，遞歸方法。*/void PostOrderRec(Node *root) if(NULL!=root) PostOrderRec(root-leftchild); PostOrderRec(root-rightchild); printf(%c ,root-data); /* 后序遍歷二叉樹，非遞歸方法。*/void PostOrderNoRec(Node *root)printf(非遞歸方法：); Node *p=root; Node *stack30; int num=0; Node *have_visited=NULL; while(NULL!=p|num0) while(NULL!

18、=p) stacknum+=p; p=p-leftchild; p=stacknum-1; if(NULL=p-rightchild|have_visited=p-rightchild) printf(%c ,p-data); num-; have_visited=p; p=NULL; else p=p-rightchild; printf(n);int main() Node *root=NULL; int num=0; char data=A,B,C,D,E,F,G; num=sizeof(data)/sizeof(char); CreatBinarySearchTree(&root,da

19、ta,num); printf(前序遍歷二叉樹:n); PreOrderNoRec(root); PreOrderRec(root); printf(n); printf(中序遍歷二叉樹：n); InOrderNoRec(root); InOrderRec(root); printf(n); printf(后序遍歷二叉樹：n); PostOrderNoRec(root); PostOrderRec(root); printf(n); return 0;算法（1）二叉樹的直徑定義為從根結(jié)點(diǎn)至葉子的最大路徑長度。編寫算法，求二叉樹(二叉鏈表)的直徑。int height(BiT bt) if(!bt) return 0; hl=height(bt-lchild)