分别编写算法求二叉树中的结点数和二叉树中叶子结点个数。 typedef struct BiNode{ TElemType data; struct BiNode *lchild,*rchild; //左右孩子指针 }BiTNode,*BiTree; int NodeCount(BiTree T)//结点数 { } int CountLeaf(BiTree T)//叶子结点个数 { }
时间: 2024-03-26 20:42:05 浏览: 43
求二叉树中的结点数可以使用递归的方式,首先判断根节点是否为空,如果为空则返回0,否则递归计算左子树和右子树的结点数量,加上根节点自身的数量,即可得到整棵树的结点数。算法如下:
```
int NodeCount(BiTree T)//结点数
{
if(T == NULL) return 0;//空树返回0
else return NodeCount(T->lchild) + NodeCount(T->rchild) + 1;//递归计算左右子树和根节点的结点数量
}
```
求二叉树中叶子结点个数也可以使用递归的方式,同样需要判断根节点是否为空,如果为空则返回0,如果根节点没有左右孩子节点,则根节点是叶子节点,返回1,否则递归计算左子树和右子树的叶子节点个数,加起来即可。算法如下:
```
int CountLeaf(BiTree T)//叶子结点个数
{
if(T == NULL) return 0;//空树返回0
else if(T->lchild == NULL && T->rchild == NULL) return 1;//叶子节点返回1
else return CountLeaf(T->lchild) + CountLeaf(T->rchild);//递归计算左右子树的叶子节点个数
}
```
相关问题
二叉树的结构类型定义如下,设计算法,统计二叉树的叶子结点数目。 typedef struct BiTNode{ ElemType data; struct BiTNode * lchild, *rchild; }BiTNode ,*BiTree;
统计二叉树的叶子结点数目可以通过递归的方式实现,具体的算法如下:
1. 如果二叉树为空,则叶子结点数目为0;
2. 如果二叉树只有一个根节点,则叶子结点数目为1;
3. 否则,递归计算二叉树的左子树和右子树的叶子结点数目,然后将其相加,即为二叉树的叶子结点数目。
下面是具体的实现:
```python
def count_leaves(tree):
if tree is None:
return 0
elif tree.lchild is None and tree.rchild is None:
return 1
else:
return count_leaves(tree.lchild) + count_leaves(tree.rchild)
```
其中,`tree` 表示二叉树的根节点,`count_leaves` 函数返回二叉树的叶子结点数目。
1、二叉树结点中添加父指针parent,请给二叉树bt填写父指针。 typedef struct BiTNode2{ TElemType data; Struct BiTNode2 *lchild , *rchild; Struct BiTNode2 *parent; } BiTNode2 , *BiTree2; 递归算法编制,void createParent(BiTree2 &bt)
好的,以下是给二叉树节点添加父指针parent的代码实现:
```c
typedef struct BiTNode2{
TElemType data;
struct BiTNode2 *lchild, *rchild;
struct BiTNode2 *parent;
} BiTNode2, *BiTree2;
// 递归算法,设置二叉树节点的父指针
void createParent(BiTree2 &bt, BiTree2 parent) {
if (bt == NULL) {
return;
}
bt->parent = parent; // 设置当前节点的父指针
createParent(bt->lchild, bt); // 递归设置左子树的父指针,将当前节点作为父节点传递给左子树
createParent(bt->rchild, bt); // 递归设置右子树的父指针,将当前节点作为父节点传递给右子树
}
```
以上代码通过递归遍历二叉树,将当前节点的父节点作为参数传递给左右子树,在遍历的过程中设置每个节点的父指针。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)