数据结构求二叉树中叶子结点的个数及二叉树的高度-

发布时间：来源：文档文库

小中大

字号：

手机查看

实验题目：求二叉树中叶子结点的个数及二叉树的高度
一、实验目的
(1 已知一棵二叉树，求该二叉树中叶子结点的个数及二叉树的高度。 (2 进一步理解二叉链表存储结构二、实验内容
(1采用二叉链表作存储结构；
(2设计递归算法求叶子结点的个数。 (3设计非递归算法求叶子结点的个数。 (4求二叉树的高度。

三、设计与编码 1、基本思想
求二叉树中叶子结点的个数，即求二叉树的所有结点中左、右子树均为空的结点个数之和。因此可以将此问题转化为遍历问题，在遍历中“访问一个结点”时判断该结点是不是叶子，若是则将计数器累加。算法如下：

求二叉树叶子结点个数算法
void CountLeaf(BiNode *root, int &count
//前序遍历根指针为root的二叉树以计算叶子数count，假定count的初值为0；
{ if (root!=NULL { if (root->lchild==NULL && root->rchild = =NULL
count++; //若root所指的结点是叶子，则计数器加1;
CountLeaf(root->lchild, count; //累计左子树上的叶子数； CountLeaf(root->rchild, count; //累计右子树上的叶子数； } } 非递归算法求叶子结点的个数可参考实验书P215。求二叉树的高度可以在层序遍历函数中实现。 2、编码
#include using namespace std; int count=0; struct BiNode { char data; BiNode *lchild,*rchild; }; class BiTree { public: BiTree(; ~BiTree(; void CountLeaf(BiNode *root;
int BiTreeDepth(BiNode *root;

BiNode *getroot({return root;} private: BiNode *root; BiNode *Creat(; void Release(BiNode *root; } ; BiTree::BiTree( { root=Creat(;
} BiNode *BiTree::Creat( {
BiNode *root; char ch; cin>>ch; if(ch=='#' return NULL; else
{ root=new BiNode; root->data=ch; root->lchild=Creat(; root->rchild=Creat(; } return root; } BiTree::~BiTree ( { Release(root; } void BiTree::Release (BiNode *root { if(root!=NULL { Release(root->lchild ; Release(root->rchild ; delete root; } } void BiTree::CountLeaf(BiNode *root { if(root!=NULL
{ if(root->lchild==NULL&&root->rchild==NULL
count++;

cout<data<<" "; CountLeaf(root->lchild; CountLeaf(root->rchild; } } int BiTree::BiTreeDepth(BiNode *root { if(root==NULL return 0; else { int dep1=BiTreeDepth(root->lchild; int dep2=BiTreeDepth(root->rchild; if(dep1>dep2 return dep1+1; else return dep2+1; } }
void main( { cout << "请依次输入创建一棵二叉树的结点数据: " << endl; BiTree B; cout<<"---前序遍历---"< B.CountLeaf(B.getroot(; cout< cout<<"该二叉树的叶子结点数为:"; cout< cout<<"该二叉树的高度为:"; cout< cout<}
四、调试与运行
1、调试时遇到的主要问题及解决高度不会写
经过老师的讲解再加上一些材料解决了
2、运行结果（输入及输出，可以截取运行窗体的界面）

五、实验心得

本文来源：https://www.2haoxitong.net/k/doc/bb7a616858fafab069dc026f.html