数据结构 清华大学出版社 严蔚敏吴伟民编著

}

/*****************删除单链表的第i个位置上的元素***********************/ void Delete(NODE *head,int i){ if(i>ListLen(head) || i<=0) printf(\ else{ int j=0;

NODE *p=head,*q; while(p && jnext; j++; }

q=(NODE *)malloc(sizeof(NODE)); q=p;

p=p->next;

q->next=p->next; } }

/*****************在单链表的第i个位置插入元素e***********************/ void Insert(NODE *head,int i,int e){ if(i>=(ListLen(head)+2) || i<=0) printf(\ else{ int j=0;

NODE *p=head,*q; while(p && jnext; j++; }

q=(NODE *)malloc(sizeof(NODE)); q->data=e;

q->next=p->next; p->next=q; } }

/*****************输入你要查找的位置***********************/ int Select(NODE *head,int e){ NODE *p=head; int j=0;

while(p && p->data!=e){ p=p->next; j++; }

if(!p) return 0;

else return j; }

/*****************合并两个表***********************/ NODE *Union(NODE *la,NODE *lb){ int i,j,k,l;

for(i=1;i<=ListLen(lb);i++){ k=Get(lb,i); j=Select(la,k); if(j==0){

l=ListLen(la); Insert(la,l+1,k); } }

return la; }

/*****************合并两个表构建一个新表***********************/ NODE *SortedUnion(NODE *la,NODE *lb){ int i,j,k,l=1; NODE *p;

for(i=1;i<=ListLen(lb);i++){ k=Get(lb,i); j=Select(la,k); if(j==0){ p=la;

p=p->next;

while(p && (p->data)next; l++; }

Insert(la,l,k);l=1; } }

return la; }

int main(){

NODE *la,*lb,*lc=NULL; la=Create(); Output(la); printf(\ int choiceNumber;

char whetherContinue='Y';

while(whetherContinue!='N' && whetherContinue!='n') {

printf(\

printf(\选择你要执行的操作:\\n\printf(\删除\\n\printf(\插入\\n\

printf(\查询的位置\\n\printf(\查询的值\\n\

printf(\表和Lb表合并\\n\

printf(\表和Lb表合成一个新表:\\n\printf(\输入你要执行的操作: \scanf(\getchar();

printf(\switch(choiceNumber) {

case 1: {

int deletePosition;

printf(\输入你要删除的位置:\\n\ scanf(\ getchar();

Delete(la,deletePosition);Output(la); break; } case 2: {

int insertPosition,insertValue;

printf(\输入你要插入的位置和值:\\n\

scanf(\ getchar();

Insert(la,insertPosition,insertValue);Output(la);break; } case 3: {

int selectPosition;

printf(\输入你要查询的位置:\\n\ scanf(\ getchar();

printf(\ break; } case 4: {

int selectValue;

printf(\输入你要查询的值:\\n\ scanf(\

getchar();

printf(\ }

case 5:{printf(\ lb=Create(); Union(la,lb);

Output(la);break;} case 6: {

printf(\ lb=Create();

SortedUnion(lc,lb);

printf(\ Output(lc);break; }

default:printf(\ }

printf(\ scanf(\ getchar(); }

return 0; }

三、二叉树的递归与非递归

1．树型结构是一种非常重要的非线性结构。树在客观世界是广泛存在的，在计算机领域里也得到了广泛的应用。在编译程序里，也可用树来表示源程序的语法结构，在数据库系统中，数形结构也是信息的重要组织形式。 2．节点的有限集合（N大于等于0）。在一棵非空数里： （1）、有且仅有一个特定的根节点； （2）、当N大于1时，其余结点可分为M（M大于0）个互不相交的子集，

其中每一个集合又是一棵树，并且称为根的子树。树的定义是以递归形式给出的。

3．二叉树是另一种树形结构。它的特点是每个结点最多有两棵子树，并且，二叉树的子树有左右之分，其次序不能颠倒。 4．二叉树的结点存储结果示意图如下：

二叉树的存储（以五个结点为例）： B 实验内容： NIL D NIL A NIL 左指针域 A 数据域 E NIL NIL 右指针域 C NIL 1、 如下二叉树： B C 为了便于在建立二叉树的时候递归的返回，在其先序遍历序列中要加入‘#’号表示结束。 D E F 例如，上面的二叉树的先序遍历的序列为： A B D # G # ##CE##F## G 已知以下二叉树的存储结构类型，

typedef struct node { int data;

stuuct node *lchild, *rchild; } bitree;

InitiatTree() {root=NULL;}//初始建立二叉树为空

void CreateBTree(char* a); //根据存于字符数组a的二叉树广义表建立对应的二叉树存储结构

void TraverseBTree(bitree *root); //按任一种遍历（分别用递归和非递归）次序输出二叉树中的所有结点

int BTreeDepth(bitree *root);//求二叉树的深度

int BTreeCount(bitree *root);//求二叉树中所有结点数

int BTreeLeafCount(bitree *root);//求二叉树中所有叶子结点数

void PrintBTree(bitree *root);//按照二叉树的一种表示方法（广义表）输出整个二叉树 main()

{ bitree *root; //定义二叉树

int n,leaf;//定义二叉树的所有节点数和叶子节点数 int h;//定义二叉树的深度 ……… ……… ……… }

源程序代码：

#include #include

struct BiTree//二叉树的存储结构类型

{

char data;

struct BiTree* lChild; struct BiTree* rChild; };

struct NODE{

struct BiTree* BiNode; int flag; };

BiTree* CreateBiTree()//二叉树建立对应的二叉树存储结构 {

BiTree *T; char ch;

scanf(\if(ch=='#') T=NULL; else{

T=(BiTree *)malloc(sizeof(BiTree)); T->data=ch;