数据结构各个上机实验题及答案范例

#define MAX_TREE_SIZE 100 #include <string.h> #include <malloc.h> #include <iostream.h> #include <conio.h> //getch() #include <stdlib.h> #include <stdio.h> #define NULL 0 #define ERROR 1 #define OK -1 typedef struct BiTNode { char data; struct BiTNode *lchild,*rchild;//左右孩子指针 }BiTNode,*BiTree; BiTree bt; int n=0,t=0; /////下面是函数的原型声明 char CreateBiTree(BiTree &T);//构造二叉链表表示的二叉树T char PreOrderTraverse(BiTree T);//先序遍历二叉树T char InOrderTraverse(BiTree T);//中序遍历二叉树T char PostOrderTraverse(BiTree T);//后序遍历二叉树T int Depth(BiTree T);//求二叉链表表示的二叉树T的深度 int leaf(BiTree T) ; int onedegree(BiTree T); /////函数定义//////////////////////////// char CreateBiTree(BiTree &T) { char ch; scanf("%c",&ch); if(ch==' ')T=NULL; else { if(!(T=(BiTNode *)malloc(sizeof(BiTNode)))) return ERROR; T->data=ch;//生成根节点 CreateBiTree(T->lchild);//构造左子树 CreateBiTree(T->rchild);//构造右子树 } return OK; }//CreateBiTree char PreOrderTraverse(BiTree T) { if(T) { printf("%c\n",T->data); PreOrderTraverse(T->lchild); PreOrderTraverse(T->rchild); } return OK; }//PreOrderTraverse char InOrderTraverse(BiTree T) { if(T) { InOrderTraverse(T->lchild); printf("%c\n",T->data); InOrderTraverse(T->rchild); } return OK; }//InOrderTraverse char PostOrderTraverse(BiTree T) { if(T) { PostOrderTraverse(T->lchild); PostOrderTraverse(T->rchild); printf("%c\n",T->data); } return OK; }//PostOrderTraverse int leaf(BiTree T) { if (T) { if(T->lchild==NULL&&T->rchild==NULL) n=n+1; leaf(T->lchild); leaf(T->rchild); } return n; }//leaf int onedegree(BiTree T) { if (T) { if((T->lchild==NULL&&T->rchild!=NULL)||(T->lchild!=NULL&&T->rchild==NULL)) t=t+1; onedegree(T->lchild); onedegree(T->rchild); } return t; }//onedegree int Depth(BiTree T) { int nl,nr; if(T==NULL) return 0; else { nl=Depth(T->lchild); nr=Depth(T->rchild); return ((nl>nr?nl:nr)+1); } }//Depth ////////主函数/////////// void main() { int n1=0,n2=0; CreateBiTree(bt); cout<<"先序"<<" "; PreOrderTraverse(bt); cout<<endl; cout<<"中序"<<" "; InOrderTraverse(bt); cout<<endl; cout<<"后序"<<" "; PostOrderTraverse(bt); cout<<endl; cout<<"这棵二叉树的叶子结点数为"<<leaf(bt)<<endl; n1=leaf(bt)/2; cout<<"这棵二叉树中度为一的结点数为"<<onedegree(bt)<<endl; n2=onedegree(bt)/2; cout<<"这棵二叉树的结点数为"<<2*n1+n2-1<<endl; cout<<"这棵二叉树的深度为"<<Depth(bt)<<endl; cout<<endl; }