二叉树存储结构及实现

一、目的

掌握二叉树的概念及实现方式熟悉二叉树的存储结构及运算

二、内容

编写一个程序btree.cpp，实现二叉树的基本运算，并在此基础上设计一个程序exp7-1.cpp，完成如下功能： （1） 由如图7.1所示的二叉树创建对应的二叉链 存储结构b，该二叉树的括号表示串为“A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,G(,I)))”； （2） 输出二叉树b； （3） 输出‘H’结点的左、右孩子结点值； （4） 输出二叉树b的高度； （5） 释放二叉树。编写一个程序exp7-2.cpp，实现二叉树的先序遍历、中序遍历和后序遍历的递归和非递归算法，以及层次遍历的算法。并对如图7.1所示的二叉树b给出求解结果。

三、源代码

实现二叉树各种基本运算的方法 #include<stdio.h> #include<malloc.h> #define MaxSize 100 typedef char ElemType; typedef struct node { ElemType data; struct node *lchild; struct node *rchild; }BTNode; void CreateBTree(BTNode *&b,char *str) { BTNode *St[MaxSize],*p; int top=-1,k,j=0;char ch; b=NULL; ch=str[j]; while(ch!='\0') { switch(ch) { case '(':top++;St[top]=p;k=1;break; case ')':top--;break; case ',':k=2;break; default:p=(BTNode *)malloc(sizeof(BTNode)); p->data=ch;p->lchild=p->rchild=NULL; if(b==NULL) b=p; else { switch(k) { case 1:St[top]->lchild=p;break; case 2:St[top]->rchild=p;break; } } } j++;ch=str[j]; } } void DestroyBTree(BTNode *&b) { if(b!=NULL) { DestroyBTree(b->lchild); DestroyBTree(b->rchild); free(b); } } BTNode *FindNode(BTNode *b,ElemType x) { BTNode *p; if(b==NULL) return NULL; else if(b->data==x) return b; else { p=FindNode(b->lchild,x); if(p!=NULL) return p; else return FindNode(b->rchild,x); } } BTNode *LchildNode(BTNode *p) { return p->lchild; } BTNode *RchildNode(BTNode *p) { return p->rchild; } int BTHeight(BTNode *b) { int lchildh,rchildh; if(b==NULL)return(0); else { lchildh=BTHeight(b->lchild); rchildh=BTHeight(b->rchild); return (lchildh>rchildh)?(lchildh+1):(rchildh+1); } } void DispBTree(BTNode *b) { if(b!=NULL) { printf("%c",b->data); if(b->lchild!=NULL||b->rchild!=NULL) { printf("("); DispBTree(b->lchild); if(b->rchild!=NULL)printf(","); DispBTree(b->rchild); printf(")"); } } } int main() { BTNode *b,*p,*lp,*rp; printf("二叉树的基本运算如下：\n"); printf("（1）创建二叉树\n"); CreateBTree(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,G(,I)))"); printf("（2）输出二叉树：");DispBTree(b);printf("\n"); printf("（3）H结点："); p=FindNode(b,'H'); if(p!=NULL) { lp=LchildNode(p); if(lp!=NULL)printf("左孩子为%c",lp->data); else printf("无左孩子"); rp=RchildNode(p); if(rp!=NULL)printf("右孩子为%C",rp->data); else printf(""); } printf("\n"); printf("（4）二叉树b的高度：%d\n",BTHeight(b)); printf("（5）释放二叉树b\n"); DestroyBTree(b); return 1; } 实现二叉树各种遍历算法 #include<stdio.h> #include<malloc.h> #define MaxSize 100 typedef char ElemType; typedef struct node { ElemType data; struct node *lchild; struct node *rchild; }BTNode; void CreateBTree(BTNode *&b,char *str) { BTNode *St[MaxSize],*p; int top=-1,k,j=0;char ch; b=NULL; ch=str[j]; while(ch!='\0') { switch(ch) { case '(':top++;St[top]=p;k=1;break; case ')':top--;break; case ',':k=2;break; default:p=(BTNode *)malloc(sizeof(BTNode)); p->data=ch;p->lchild=p->rchild=NULL; if(b==NULL) b=p; else { switch(k) { case 1:St[top]->lchild=p;break; case 2:St[top]->rchild=p;break; } } } j++;ch=str[j]; } } void DestroyBTree(BTNode *&b) { if(b!=NULL) { DestroyBTree(b->lchild); DestroyBTree(b->rchild); free(b); } } BTNode *FindNode(BTNode *b,ElemType x) { BTNode *p; if(b==NULL) return NULL; else if(b->data==x) return b; else { p=FindNode(b->lchild,x); if(p!=NULL) return p; else return FindNode(b->rchild,x); } } BTNode *LchildNode(BTNode *p) { return p->lchild; } BTNode *RchildNode(BTNode *p) { return p->rchild; } int BTHeight(BTNode *b) { int lchildh,rchildh; if(b==NULL)return(0); else { lchildh=BTHeight(b->lchild); rchildh=BTHeight(b->rchild); return (lchildh>rchildh)?(lchildh+1):(rchildh+1); } } void DispBTree(BTNode *b) { if(b!=NULL) { printf("%c",b->data); if(b->lchild!=NULL||b->rchild!=NULL) { printf("("); DispBTree(b->lchild); if(b->rchild!=NULL)printf(","); DispBTree(b->rchild); printf(")"); } } } void PreOrder(BTNode *b) { if(b!=NULL) { printf("%C",b->data); PreOrder(b->lchild); PreOrder(b->rchild); } } void PreOrder1(BTNode *b) { BTNode *St[MaxSize],*p; int top=-1; if(b!=NULL) { top++; St[top]=b; while(top>-1) { p=St[top]; top--; printf("%C",p->data); if(p->rchild!=NULL) { top++; St[top]=p->rchild; } if(p->lchild!=NULL) { top++; St[top]=p->lchild; } } printf("\n"); } } void InOrder(BTNode *b) { if(b!=NULL) { InOrder(b->lchild); printf("%c",b->data); InOrder(b->rchild); } } void InOrder1(BTNode *b) { BTNode *St[MaxSize],*p; int top=-1; if(b!=NULL) { p=b; while(top>-1||p!=NULL) { while(p!=NULL) { top++; St[top]=p; p=p->lchild; } if(top>-1) { p=St[top]; top--; printf("%c",p->data); p=p->rchild; } } printf("\n"); } } void PostOrder(BTNode *b) { if(b!=NULL) { PostOrder(b->lchild); PostOrder(b->rchild); printf("%c",b->data); } } void PostOrder1(BTNode *b) { BTNode *St[MaxSize]; BTNode *p; int top=-1; bool flag; if(b!=NULL) { do { while(b!=NULL) { top++; St[top]=b; b=b->lchild; } p=NULL; flag=true; while(top!=-1&&flag) { b=St[top]; if(b->rchild==p) { printf("%c",b->data); top--; p=b; } else { b=b->rchild; flag=false; } } }while(top!=-1); printf("\n"); } } void TravLevel(BTNode *b) { BTNode *Qu[MaxSize]; int front,rear; front=rear=0; if(b!=NULL)printf("%c",b->data); rear++; Qu[rear]=b; while(rear!=front) { front=(front+1)%MaxSize; b=Qu[front]; if(b->lchild!=NULL) { printf("%c",b->lchild->data); rear=(rear+1)%MaxSize; Qu[rear]=b->lchild; } if(b->rchild!=NULL) { printf("%c",b->rchild->data); rear=(rear+1)%MaxSize; Qu[rear]=b->rchild; } } printf("\n"); } int main() { BTNode *b; CreateBTree(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))"); printf("二叉树b：");DispBTree(b);printf("\n"); printf("层次遍历序列："); TravLevel(b); printf("先序遍历序列：\n"); printf(" 递归算法：");PreOrder(b);printf("\n"); printf(" 非递归算法：");PreOrder1(b); printf("中序遍历序列：\n"); printf(" 递归算法：");InOrder(b);printf("\n"); printf(" 非递归算法：");InOrder1(b); printf("后序遍历序列：\n"); printf(" 递归算法：");PostOrder(b);printf("\n"); printf(" 非递归算法：");PostOrder1(b); DestroyBTree(b); return 1; }

备注： 有问题可以评论，看到后我会尽力及时回复的，谢谢！