//两种算法实现计算二叉树叶子节点的个数
//二叉树叶子节点个数算法之非递归算法和递归算法
#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");
}
#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语言版
二叉树叶子结点个数计算
设二叉树采用链式存储结构,试设计一个算法计算一棵给定二叉树中叶子结点的数目
二叉树中叶子结点个数算法
二叉树叶子结点个数计算
数据结构二叉树遍历叶子结点及深度
二叉树的建立并求出叶子节点数目