二叉树的链式存储及基本运算

本文是数据结构基础系列(6)：树和二叉树中第9课时二叉树的基本运算及其实现的例程。

单链表算法库算法库采用程序的多文件组织形式，包括两个文件： 　　 　　1.头文件：btree.h，包含定义顺序表数据结构的代码、宏定义、要实现算法的函数的声明；

typedef char ElemType;typedef struct node{ElemType data;node *rchild;//指向右孩子} BTNode;void CreateBTNode(BTNode *&b,char *str);//由str串创建二叉链BTNode *FindNode(BTNode *b,ElemType x);//返回data域为x的节点指针BTNode *LchildNode(BTNode *p); //返回*p节点的左孩子节点指针BTNode *RchildNode(BTNode *p); DispBTNode(BTNode *b);

　　2.源文件：btree.cpp，包含实现各种算法的函数的定义

CreateBTNode(BTNode *&b,char *str)//由str串创建二叉链{BTNode *St[MaxSize],*p=NULL;int top=-1,k,j=0;char ch;b=NULL;//建立的二叉树初始时为空ch=str[j];while (ch!=’\0′) //str未扫描完时循环{switch(ch){case ‘(‘:top++;St[top]=p;k=1;: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];}}BTNode *FindNode(BTNode *b,ElemType x) //返回data域为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;elsereturn FindNode(b->rchild,x);}}BTNode *LchildNode(BTNode *p) //返回*p节点的左孩子节点指针{return p->lchild;}BTNode *RchildNode(BTNode *p) //返回*p节点的右孩子节点指针{return p->rchild;}int BTNodeDepth(BTNode *b) //求二叉树b的深度{int lchilddep,rchilddep;if (b==NULL)return(0);//空树的高度为0else{lchilddep=BTNodeDepth(b->lchild); //求左子树的高度为lchilddeprchilddep=BTNodeDepth(b->rchild); //求右子树的高度为rchilddepreturn (lchilddep>rchilddep)? (lchilddep+1):(rchilddep+1);}}void DispBTNode(BTNode *b) //以括号表示法输出二叉树{if (b!=NULL){printf(“%c”,b->data);if (b->lchild!=NULL || b->rchild!=NULL){printf(“(“);DispBTNode(b->lchild);if (b->rchild!=NULL) printf(“,”);DispBTNode(b->rchild);printf(“)”);}}}void DestroyBTNode(BTNode *&b) //销毁二叉树{if (b!=NULL){DestroyBTNode(b->lchild);DestroyBTNode(b->rchild);free(b);}}

　　3.在建立算法库过程中，，为了完成测试，再同一项目（project）中建立一个源文件(如main.cpp)，编制main函数，完成相关的测试工作。

main(){BTNode *b,*p,*lp,*rp;;printf(” (1)创建二叉树:”);CreateBTNode(b,”A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))”);printf(“\n”);printf(” (2)输出二叉树:”);DispBTNode(b);printf(“\n”);printf(” (3)查找H节点:”);p=FindNode(b,’H’);if (p!=NULL){lp=LchildNode(p);if (lp!=NULL)printf(“左孩子为%c “,lp->data);elseprintf(“无左孩子 “);rp=RchildNode(p);if (rp!=NULL)printf(“右孩子为%c”,rp->data);elseprintf(“无右孩子 “);}elseprintf(” 未找到！”);printf(“\n”);printf(” (4)二叉树b的深度:%d\n”,BTNodeDepth(b));printf(” (5)释放二叉树b\n”);DestroyBTNode(b);return 0;}

注：在main函数中，创建的用于测试的二叉树如下——

一个人去旅行，而且是去故乡的山水间徜徉。