求二叉树中叶子结点的个数
《数据结构》试验报告
课程名称数据结构
设计题目求二叉树中叶子结点的个数
求二叉树中叶子结点的个数试验目的
已知一个二叉树，求该二叉树中叶子结点的个数。
试验内容
1、采用二叉链表作存储结构；
2、设计递归算法求叶子结点的个数；
3、设计非递归算法求叶子结点的个数。
设计编码
编码：//bitree.h
#ifndef BITREE_H
#define BITREE_H
template
struct BiNode{
DataType data;
BiNode
};
template
class BiTree{
public:
BiTree();
void PreOrder(BiNode
void InOrder(BiNode
void PostOrder(BiNode
void LeverOrder(BiNode
BiNode
BiNode
int CountNode(BiNode
void PreOrderPrintLeaf(BiNode
int Depth(BiNode
private:
BiNode
};
#endif
//bitree.cpp
#include"bitree.h"
#include
using namespace std;
template
BiTree
root = Create(root);
}
template
void BiTree
if(bt != NULL){
//1.先访问根结点
cout<
//2.前序遍历左子树
PreOrder(bt->lchild);
//3.前序遍历右子树
PreOrder(bt->rchild);
}
}
template
void BiTree
//1.中序遍历左子树
InOrder(bt->lchild);
//2.访问根结点
cout<
//3.中序遍历右子树
InOrder(bt->rchild);
}
}
template
void BiTree
if(bt != NULL){
//1.后序遍历左子树
PostOrder(bt->lchild);
//2.后序遍历右子树
PostOrder(bt->rchild);
//3.访问根结点
cout<
}
}
template
void BiTree
BiNode
int front = -1, rear = -1;
if(bt != NULL){
Q[++rear] = bt;
while(front != rear){
q = Q[++front];
cout<
if(q->lchild != NULL){
Q[++rear] = q->lchild;
}
if(q->rchild != NULL){
Q[++rear] = q->rchild;
}
}
}
}
template
BiNode
cin>>ch;
if(ch == '#') bt = NULL;
else{
//1.建立根结点
bt = new BiNode
bt->data = ch;
//2.建立左子树
bt->lchild = Create(bt->lchild);
//3.建立右子树
bt->rchild = Create(bt->rchild);
}
return bt;
}
template
BiNode
return root;
}
template
int BiTree
if(bt == NULL) return 0;
else{
CountNode(bt->lchild);
CountNode(bt->rchild);
count++;
return count;
}
}
template
void BiTree
if(bt){//bt != NULL
if(!bt->lchild && !bt->rchild){
//bt->lchild == NULL && bt->rchild == NULL
cout<
}
PreOrderPrintLeaf(bt->lchild);
PreOrderPrintLeaf(bt->rchild);
}
}
template
int BiTree
if(!bt) return 0;//bt == NULL
else{
int dl = Depth(bt->lchild);
int dr = Depth(bt->rchild);
return (dl>dr?dl:dr) + 1;
}
}
//bitree_main.cpp
#include
using namespace std;
#include"bitree.cpp"
int main(){
BiTree
cout<<"前序遍历序列为：";
t.PreOrder(t.GetRoot());
cout< cout<<"中序遍历序列为："; t.InOrder(t.GetRoot()); cout< cout<<"后序遍历序列为："; t.PostOrder(t.GetRoot()); cout< cout<<"层序遍历序列为："; t.LeverOrder(t.GetRoot()); cout< cout<<"结点数为："< cout<<"叶子结点为："; t.PreOrderPrintLeaf(t.GetRoot()); cout< cout<<"深度为："< return 0; } 运行与测试 1、随机进行测试，并对特殊情况进行测试等。 2、运行结果如下： 一、总结与心得 1.实验开始应先理解实验的目的 2.根据实验要实现的内容运用相关的原理 3.先在纸上进行演示理清思路 4.写出伪代码 5.翻译成代码 6.进行调试并修改 7.巩固了和提高了编程的能力，积累了一些编程技巧和经验。 8.在课程设计的过程中更深刻认识到结构设计的重要性，有时在结构中加一个记录一个数字的变量也许会使程序代码更明朗和易于设计。 9.在编写代码过程中需要谨慎细心，避免不必要的错误。 10.在遇到困难时可以向同学或者老师求助，也可以再网上找到帮助。 #include"malloc.h" #define NULL 0 #include"stdio.h" typedef struct node { char data; struct node *lchild,*rchild; }NODE; int count; NODE *crt_bt_pre()/*二叉树先序创建算法*/ { NODE * bt; char ch; printf("\n\t\t\t"); scanf("%c",&ch); getchar(); if(ch==' ') bt=NULL; else { bt=(NODE*)malloc(sizeof(NODE)); bt->data=ch; printf("\n\t\t\t请输入%c结点的左孩子:",bt->data); bt->lchild=crt_bt_pre(); printf("\n\t\t\t请输入%c结点的右孩子:",bt->data); bt->rchild=crt_bt_pre(); } return(bt); } void Preorder(NODE* bt)/*二叉树先序递归遍历算法*/ { if(bt!=NULL) { printf("\n\t\t\t %c",bt->data); Preorder(bt->lchild); Preorder(bt->rchild); } } void Inorder(NODE* bt) { if(bt!=NULL) { Inorder(bt->lchild); printf("\n\t\t\t %c",bt->data); Inorder(bt->rchild); } } void Postorder(NODE* bt) { if(bt!=NULL) { Postorder(bt->lchild); Postorder(bt->rchild); printf("\n\t\t\t %c",bt->data); } } int CountLeaf(NODE *bt)/*求二叉树叶子结点数的递归遍历算法*/ { if(bt==NULL) return 0; if(bt->lchild==NULL&&bt->rchild==NULL) count++; CountLeaf(bt->lchild); CountLeaf(bt->rchild); return(count); } int CountNode (NODE* bt)/*求二叉树结点数的递归遍历算法*/ { if(bt==NULL) return 0; else count++; CountNode(bt->lchild); CountNode(bt->rchild); return(count); } int TreeDepth(NODE* bt)/*求二叉树深度的递归遍历算法*/ { int x,y; if(bt==NULL) 计算二叉树叶子结点 1.程序设计简介 已知一棵二叉树，求该二叉树中叶子结点的个数。 2.基本要求 （1）设计二叉树的二叉链表为存储结构 （2）设计求叶子结点个数的递归算法 （3）输入：一颗二叉树 （4）输出：二叉树中叶子结点的个数 3.实现提示 （1）存储设计 二叉树采用二叉链表为存储结构 (2)算法设计 求二叉树中叶子结点个数，即求二叉树的所有结点中左、右子树均为空的结点个数之和。可以将此问题转化为遍历问题，在遍历中“访问一个结点”时判断该结点是不是叶子，若是则将计数器累加。 4.源程序 #include struct BiNode 行与测试 6.调试感想 非递归算法求叶子结点的个数 #include (root); root=root->lchild; } else { root=(); // cout< 实验叶子结点的计算 姓名：xxx 班级：xxx） 学号：16130xxxxx 时间2017.10.22 1 问题描述 二叉树叶子节点的计算 1.二叉树的创建 2.二叉树的图形显示 3.二叉树叶子节点的计算 2 结构设计 二叉树叶子结点的计算主要是二叉树的创建，在这里选择的存储结构是一个链式存Data lchild rchild struct BTNode{ int data; BTNode*lchild; BTNode*rchild; }; 3 算法设计 在程序正式编写之前我定义了几个功能函数 （1）指针清空函数，预定义一个指针bt 使lchild和rchild的值分别赋予bt并且使其为空 static int clear(BTNode *bt) { if (bt) { clear(bt->lchild ); clear(bt->rchild ); cout<<"释放了指针"< { if(p->lchild==NULL&&p->rchild==NULL)count++; Leaf(p->lchild,count); Leaf(p->rchild,count); } return count; } （2）二叉树的创建 同样是利用递归的方式，输入参数包括指针，左右判断，以及判空条件static int create(BTNode *p,int k ,int end) { BTNode *q; int x; cin>>x; if(x!=end) { q=new BTNode; q->data =x; q->lchild=NULL; q->rchild=NULL; if(k==1)p->lchild=q; if(k==2)p->rchild=q; create(q,1,end); create(q,2,end); } return 0; }; （3）类的构造函数创建树并且输入各结点数值 在这里，采用的时先序遍历法依次输入树中的各结点数值 Step 1:定义新的结构体指针， Step 2:申请动态存储空间； Step 3:输入节点元素，并且指针后移到输入结点的后继结点，end作为结点结束标志； Step 4:重复步骤3，直到输入结束； void BinaryTree::CreateBiTree (int end) { cout<<"请按照先序序列的顺序输入二叉树，-1为空指针域标志："< #include 题目一：统计二叉树中叶子结点的个数 [问题描述] 已知一棵二叉树，求该二叉树中叶子结点的个数。 [基本要求] （1）采用二叉链表作存储结构，存储二叉树； （2）输出前序、中序、后序遍历该二叉树的遍历结果； （3）设计递归算法求叶子结点的个数； （4）设计非递归算法求叶子结点的个数。 [测试数据] [源代码] //tree1.h #ifndef tree1_H #define tree1_H #include void PreOrder() {PreOrder(root);} void InOrder() {InOrder(root);} void PostOrder() {PostOrder(root);} void CountLeaf1() {cout< 求二叉树叶子节点的个数并输出 实验目的： 设二叉树采用链式存储结构，试设计一个算法计算一颗给定二叉树中叶子结点的数目。 实验类容与步骤： （1）建立一颗二叉树； （2）先序遍历输出该二叉树； （3）计算出该二叉树的叶子结点个数； （4）输出叶子结点个数； 实验平台： Windows xp 操作系统，VC 6.0集成环境 实验设计方案： （1）输入扩展先序遍历序列并建立对应的二叉树. 输入#表示输入的二叉树元素为空。输入回车键表示输入结束。 （2）先序输出当前二叉树的叶子节点和叶子节点个数. 源程序代码： #include /* HELLO.C -- Hello, world */ #include "stdio.h" #include "conio.h" #include "malloc.h" /*=============二叉树的二叉链表存储表示===================*/ typedef struct BiTNode {int data; struct BiTNode *lchild,*rchild;/*左右孩子指针*/ }; typedef struct BiTNode chenchen; /*=============构建二叉树======================*/ chenchen *create() {int x; static int z=0; chenchen *p; z=z+1; printf("%3d: ",z); scanf("%3d",&x); if(x!=0) {p=(chenchen*)malloc(sizeof(chenchen)); p->data=x; p->lchild=create(); p->rchild=create();} else p=0; return p; } /*=====构建函数计算叶子节点的个数======*/ int count(chenchen *t){ static int y=0; if(t) {count(t->lchild); count(t->rchild); if(t->lchild==0&&t->rchild==0) {y++;}} return y;} /*============主函数===============*/ main() { chenchen *T ;int c; printf("Input the data:\n"); T=create(); if(T){c=count(T);printf("\nNumber=%d",c);} else{printf("Empty");}printf("\n"); getch(); } 南通大学数据结构实践教程 实验报告册 1.程序设计简介 已知一棵二叉树，求该二叉树中叶子结点的个数。 2.基本要求 （1）设计二叉树的二叉链表为存储结构 （2）设计求叶子结点个数的递归算法 （3）输入：一颗二叉树 （4）输出：二叉树中叶子结点的个数 3.实现提示 （1）存储设计 二叉树采用二叉链表为存储结构 (2)算法设计 求二叉树中叶子结点个数，即求二叉树的所有结点中左、右子 树均为空的结点个数之和。可以将此问题转化为遍历问题，在遍历中“访问一个结点”时判断该结点是不是叶子，若是则将计数器累加。 4.源程序 #include void BiTree::yezi(BiNode *root,int &n); private: BiNode *root; //指向根结点的头指针 BiNode *Creat( ); //有参构造函数调用 void Release(BiNode *root); //析构函数调用}; BiTree::BiTree( ) { root = Creat( ); } BiTree::~BiTree(void) { Release(root); } BiNode* BiTree::Getroot( ) { return root; } #include //两种算法实现计算二叉树叶子节点的个数 //二叉树叶子节点个数算法之非递归算法和递归算法 #include"stdio.h" #include"stdlib.h" #define MAXSIZE 12500 typedef struct BitNode{ char data; struct BitNode *lchild,*rchild; }*BitTree; int w = 0; typedef struct stack{ int top; BitTree MaxSize[MAXSIZE]; }*Stack; void creattree(BitTree *T) { char ch; scanf("%c",&ch); if(ch == '.') *T = NULL; else{ (*T) = (struct BitNode *)malloc(sizeof(struct BitNode)); (*T)->data = ch; creattree(&((*T)->lchild)); creattree(&((*T)->rchild)); } } void PrintTree1(BitTree Boot) { Stack S; S = (Stack)malloc(sizeof(struct stack)); S->top = 0; while(Boot != NULL||S->top != 0) { if(Boot != NULL) { printf("%2c",Boot->data); S->MaxSize[S->top] = Boot; S->top++; Boot = Boot->lchild; } else { Boot = S->MaxSize[S->top-1]; S->top--; if(Boot->rchild == NULL && Boot->lchild == NULL) { w ++; } Boot = Boot->rchild; } } } int leaf(BitTree T) { if(!T) return 0; //空树,无叶子 else if(!(T)->lchild && !(T)->rchild) return 1; else return (leaf(T->lchild) + leaf(T->rchild)); } main() { BitTree T; printf("请先序输入二叉树（‘.’代表空子树）：\n"); creattree(&T); printf("先序输出为："); PrintTree1(T); printf("\n"); printf("%d",w); printf("\n"); w = leaf(T); printf("%d",w); printf("\n"); 二叉树叶子结点个数计算 姓名：许严班级：计122 学号：1213023050 1.问题描述 已知一棵二叉树，求该二叉树中叶子结点的个数。 2.基本要求 （1）设计二叉树的二叉链表存储结构。 （2）设计求叶子结点个数的递归算法。 （3）输入：一棵二叉树。 （4）输出：二叉树中叶子结点的个数。 3.实验提示 （1）存储设计 二叉树采用二叉链表为存储结构。 typedef struct BiTNode{ TElemType data; Struct BiTNode *lchild,*rchild;//左右孩子指针 } BiTNode,*BiTree; （2）算法设计 求二叉树中叶子结点个数，即求二叉树的所有结点中左右字数均为空的结点个数之和。可以将此问题转化为遍历问题，在遍历中“访问一个结点”时判断该结点是不是叶子，若是则将计数器累加。算法如下： Void CountLeaf(BiNode 本人上机实测，数据结构c++ ，可以运行，放心使用 #include } int PostOrderTraverse(BiTree T){ if(T){ PostOrderTraverse(T->Lchild); PostOrderTraverse(T->Rchild); cout< 1二叉树采用链表存储结构，实现建立、遍历（先序、中序、后序）、求结点总数、叶子数、度为1.2的结点数。 前几天写的，输入二叉树的广义表形式，建立二叉树的链式存储。输出的是中序。有注释。例如输入：a(b,c(d,e(f)),g,h(i)) #include n++; h->rc=creat(a); return h; } if(a[n]==')') //a[n]为右括弧返回h { n++; return h; } else return h; } void print(tree *h) //二叉树中序输出{ if(h!=NULL) { print(h->lc); printf("%c",h->data); print(h->rc); } } int high(char a[]) //判断树的高度{ int i=0,max=0,p=0; while(a[i]!=0) { if(a[i]=='(')求二叉树的深度叶子结点数总结点数()
二叉树叶子结点个数计算
实验报告二叉树求叶子结点数目(内容清晰)
设二叉树采用链式存储结构,试设计一个算法计算一棵给定二叉树中叶子结点的数目
二叉树中叶子结点的个数
8.求二叉树叶子节点的个数并输出
二叉树计算叶子节点的算法(数据结构)C语言版
二叉树叶子结点个数计算
设二叉树采用链式存储结构,试设计一个算法计算一棵给定二叉树中叶子结点的数目
二叉树中叶子结点个数算法
二叉树叶子结点个数计算
数据结构二叉树遍历叶子结点及深度
二叉树的建立并求出叶子节点数目
- 二叉树中叶子结点的个数
- 设二叉树采用链式存储结构,试设计一个算法计算一棵给定二叉树中叶子结点的数目
- 求二叉树的深度叶子结点数总结点数()
- 二叉树叶子结点个数计算
- 8.求二叉树叶子节点的个数并输出
- 数据结构二叉树遍历叶子结点及深度
- 2. 输出二叉树中的叶子结点
- 实验报告二叉树求叶子结点数目
- 二叉树叶子结点数和高度
- 二叉树的遍历以及叶子节点个数的计算
- 将二叉树的所有叶子结点从左向右链接成单链表的算法
- 设二叉树采用链式存储结构,试设计一个算法计算一棵给定的二叉树中叶子节点的数目
- 二叉树叶子结点个数计算
- 实验报告二叉树求叶子结点数目(内容清晰)
- 第四组 统计二叉树的叶子结点的个数
- 二叉树叶子结点个数计算
- 设二叉树采用链式存储结构,试设计一个算法计算一棵给定二叉树中叶子结点的数目
- 二叉树叶子结点个数
- 二叉树中叶子结点个数算法
- 二叉树叶子结点个数计算
- 石药集团欧意药业有限公司财务报表
- 张某某与石家庄制药集团欧意药业有限公司、石家庄制药集团华盛制药有限公司、石药集团中奇制药技术(石家庄
- 石药集团参观感想
- 东北大学21年1月考试《土木工程定额与预算》考核作业(最新答案)
- 土木工程定额及预算-试卷E
- 土木工程概预算---精品模板
- 土木概预算重点(整理版)
- 建筑工程定额与预算(土木工程本科)
- 工程概预算
- 简述定额法的适用范围及优缺点
- 土木工程造价知识点汇总
- 关于工程清单计价与预算定额计价的区别分析
- 土木工程预算定额表
- 2018房屋建筑与装饰工程预算定额
- 简述定额法的适用范围及优缺点
- 2017年中国银行校园招聘网申简历填写指导及注意事项
- 网申流程及需要注意的问题
- 四大求职全攻略：简历、网申、笔试、面试指导
- 网申自我评价范文
- 海马课堂博士申请