欢迎来到天天文库
浏览记录
ID:35504786
大小:60.79 KB
页数:5页
时间:2019-03-25
《数据结构(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-
此文档下载收益归作者所有