（验证性实验）实现二叉树的各种基本运算的算法 编写一个程序btree.cpp， 实现二叉树基本运算，并在此基础上设计一个程序exp5-1.cpp，完成如下功能。由图所示的二叉树创建对应的二叉链存储结构b，叉树的括号表示串为“A(B(D,E(H(J,K(L,M(,N))))),C(,I)))”输出二叉树b输出‘H’结点的左、右孩子结点值输出二叉树b的高度释放二叉树b
代码如下
btree
//二叉树的基本运算算法#include <stdio.h>#include <malloc.h>#define MaxSize 100typedef char ElemType;typedef struct node {ElemType data;//数据元素struct node *lchild;//指向左孩子节点struct node *rchild;//指向右孩子节点} BTNode;void CreateBTree(BTNode * &b,char *str)//创建二叉树{BTNode *St[MaxSize],*p=NULL;int top=-1,k,j=0; char ch;b=NULL;//建立的二叉树初始时为空ch=str[j];while (ch!=' ') //str未扫描完时循环{ 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) //*p为二叉树的根节点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); //空树的高度为0 else {lchildh=BTHeight(b->lchild);//求左子树的高度为lchildhrchildh=BTHeight(b->rchild);//求右子树的高度为rchildhreturn (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(")");//有孩子节点时才输出)}}}
exp5-1.cpp
#include "btree.cpp" main(){BTNode *b;int height;printf("(1)二叉树创建n");CreateBTree(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I))");//二叉树创建printf("(2)输出二叉树n"); DispBTree(b); printf("n");printf("(3)H结点的左孩子结点值:%cn",LchildNode(FindNode(b,'H'))->data);printf("H结点的右孩子结点值:%cn",RchildNode(FindNode(b,'H'))->data); height=BTHeight(b); printf("(4)二叉树b的高度 %dn",height); printf("(5)释放二叉树bn"); DestroyBTree(b);}