数据结构与算法问题分析及源代码之二叉树

1 题目

编写一个程序，实现二叉树的各种运算，并在此基础上设计一个主程序完成如下功能（b为如图示的一棵二叉树）： 输出二叉树b;

输出‘H’节点的左、 右孩子结点值; 输出二叉树b的深度; 输出二叉树b的结点个数;

输出二叉树b的叶子结点个数。

2 目标

熟悉二叉树的定义及其基本操作的实现 3 设计思想

二叉树的每个结点都有指向其左右孩子的指针，对二叉树的表示可以有很多方法，这里采用中序的带括号表示法，以字符串形式读入输出。建立存储结构的时候，从根结点开始，赋值定义其左右指针，由于二叉树的每个结点操作类似，因此可以采用递归的方法。 4 算法描述

（1）输入建立二叉树：读入字符串，根据括号表示法的规则，a（b,c）的括号中左右元素表示结点的左右子树结点，若结点是树（括号中还有括号），则再调用改操作，直至结点全部读入。

（2）输出二叉树：从根结点开始，打印根结点数据，如果结点的左右孩子指针不为空，就打印左括号，并按先左后右的次序调用此操作，最后输出右括号完成括号表示。

（3）输出二叉树的深度：从根结点开始，如果左或右孩子不是树的话返回深度加一，否则继续调用此操作，直到完全返回(返回深度是左、右深度中的最大值)。

（4）输出二叉树叶子结点数：从根结点开始，用ln和r n分别表示结点左右叶子结点数，函数返回叶子结点数之和，递归调用该函数，直到左右指针指空。 （5）输出二叉树结点数：结点数即是叶子数加一。 5 程序结构图

主程序main 初始化CreateBTNode(BTNode *&b , char *str) 返回data域为x的结点指针FindNode(BTNode *b , ElemType x) 返回*p结点的左孩子结点指针LchildNode(BTNode *p) 返回*p结点的右孩子结点指针RchildNode(BTNode *p) 求二叉树b的深度BTNodeDepth(BTNode *b) 以括号标示法输出二叉树DispBTNode(BTNode *b) 求二叉树b的结点个数Nodes(BTNode *b) 求二叉树b的叶子结点个数LeafNodes(BTNode *b)

6 源程序

typedef struct node{ char data;

struct node *lchild; struct node *rchild; }*Bitree;

Bitree bt;

void CreateBitree(Bitree &bt,char *str){ Bitree St[100],p=NULL;//100个结点的二叉树 int top=-1,k,j=0; char ch; bt=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 = (struct node*)malloc(sizeof(struct node)); p->data=ch;p->lchild=p->rchild=NULL; if (bt==NULL)//是根结点 bt=p;

else//是叶子结点

{ switch(k) {

case 1:St[top]->lchild=p;break; case 2:St[top]->rchild=p;break; } } } j++;

ch=str[j]; } }

void DispBTNode(Bitree bt) {

Bitree p;

if(bt==NULL) return ; else {

printf(\"%c\",bt->data);

if(bt->lchild!=NULL||bt->rchild!=NULL) {

printf(\"(\");

DispBTNode(bt->lchild); if(bt->rchild!=NULL) printf(\);

DispBTNode(bt->rchild); printf(\")\"); } } }

int BtNodeDepth(Bitree bt) {

int lh,rh; if(bt==NULL) return 0; else {

lh=BtNodeDepth(bt->lchild); rh=BtNodeDepth(bt->rchild); return (lh>rh?lh:rh)+1; } }

int NodeNum(Bitree bt) {

int ln,rn;

if(bt==NULL) return 0; else {

ln=NodeNum(bt->lchild); rn=NodeNum(bt->rchild); return ln+rn+1; } }

int LeafNodeNum(Bitree bt) {

int ln,rn; if(bt==NULL) return 0;

else if(bt->lchild==NULL&&bt->rchild==NULL) return 1; else {

ln=LeafNodeNum(bt->lchild); rn=LeafNodeNum(bt->rchild); return ln+rn; } }

#include #include #include \"bintree.h\" void main() {

int m,length; Bitree p; char e;

char choice;

printf(\"请选择(输入退出)\\n1 创建二叉树b\\n2 打印二叉树b(中续括号表示法)\\n3 二叉树b的长度\\n4 二叉树b的结点数\\n5 二叉树b的叶子数\\n\"); while(choice!='0') {

// system(\"cls\");

scanf(\"%c\",&choice); switch (choice) {

case '1':

CreateBitree(bt,\"A(B(D,E(H(J,K(L,M(,N))),)),C(F,G(,I)))\"); break;

case '2':

DispBTNode(bt); printf(\"\\n\"); break; case '3':

printf(\"二叉树b的长度为:%d\\n\",BtNodeDepth(bt)); break; case '4':

printf(\"二叉树结点数为:%d\\n\",NodeNum(bt)); break; case '5':

printf(\"二叉树叶子结点数为:%d\\n\",LeafNodeNum(bt)); break; case '0':

return; }

getchar(); } }