数据结构（c语言版）程海英-上机5

《数据结构（c语言版）程海英-上机5》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、上机5二叉树的操作1•问题描述采用二叉链表存储二叉树，并对二叉树进行如下操作：建立一棵二叉树；遍历二叉树；求二叉树的深度（高度）；输出二叉树所有结点及个数；输出二叉树的所有叶子结点及个数；删除左、右子树；输出二叉树；查找结点等。2•数据结构设计二叉链表的每个结点都有一个数据域和两个指针域，一个指针指向左子树，另一个指针指向右子树。描述为：〃数据域〃左指针域，右指针域typedefstructnode{chardata;structnode*lchild,*rchild;JBTNode;3•函数说明二叉树的基本操作：voidcreat

2、ebitree(BTNode*&T)voidPreOrder(BTNode*p)voidInOrder(BTNode*p)voidPostOrder(BTNode*p)voidDispLeaf(BTNOde*p)intBiTreeDepth(BTNode*p)intCountLeaf(BTNode*p)intCount(BTNode*p)〃构建二叉树〃先序访问操作〃中序访问操作〃后序访问操作〃输出一棵二叉树的所有叶子结点〃求二叉树的高度〃二叉树屮所有叶子结点个数〃二叉树中所有结点个数BTNode*SearchNode(BTNOde^

3、p,charx)〃查找结点BTNode^DeleteLeft(BTNode*p)〃删除左子树BTNode^DeleteRight(BTNode*p)〃删除右子树4•编码实现#include#include#include#includetypedefstructnode{chardata;〃数据域structnode引child,Schild;〃左指针域，右指针域}BTNode;voidcreatebitree(BTNode*&T){charch;sc

4、anf("%c”，&ch);讦(ch二二'')T=NULL;else{T=newBTNode;T->data=ch;createbitree(T->lchild);createbitree(T->rchild);〃按先序访问操作voidPreOrder(BTNode*p){if(p!二NULL){printf("%c”,p->data);PreOrder(p->lchild);//按先序遍历左子树PreOrder(p->rchild);〃按先序遍历右了树〃按中序访问操作voidInOrder(BTNode*p){if(p!二NULL

5、){//按中序遍历左子树〃按中序遍历右了树〃按后序访问操作〃按后序遍历左子树〃按后序遍历右了树InOrder(p->lchild);printf(“％c”,p->data);InOrder(p->rchild);}}voidPostOrder(BTNode*p){讦(p!=NULL){Postorder(p->lchild);Postorder(p->rchild);printf(“％c”，p->data);}}voidDispLeaf(BTNOde*p){if(p!二NULL){if(p->lchild=NULL&&p->rchi

6、ld==NULL)printf(u%c,>,p->data);else{DispLeaf(p->lchild);DispLeaf(p->rchild);}}intBiTreeDepth(BTNode*p){intldep,rdep;讦(p==NULL)return0;〃空树的高度为0else{ldep=BiTreeDepth(p->lchild);//求左了树的高度为ldeprdep=BiTreeDepth(p->rchild);//求右子树的高度为rdepif(ldep>rdep)returnldep+1;elsereturnrd

7、ep+1;}}intCountLeaf(BTNode*p){〃二叉树中所有叶子结点个数intm;if(p=NULL)m=0;elseif(p->lchild==NULL&&p->rchild==NULL)m=l;elsem=CountLeaf(p->lchild)+CountLeaf(p->rchild);returnm;}intCount(BTNode*p){〃二叉树中所有结点个数intm,n;if(!p)return0;if(!p->Ichild&&!p・>rchild)return1;else{m=Count(p->lchil

8、d);n=Count(p->rchild);return(m+n+1);}}BTNode*SearchNode(BTNOde*p,charx){BTNode*b;if(p二二NULL)returnNULL;〃查找失败elseif(p-