二叉树中叶子节点的统计和树高问题
1、已知二叉树以二叉链表进行存储，其中结点的数据域为data，编写算法，统计二叉树中叶子结点值等于x的结点数目。
typedef struct BTNode
{
int data;
struct BTNode *lchild ; //左孩子指针
struct BTNode *rchild; // 右孩子指针
} BTNode;//二叉链表的结构
int num = 0;//用于统计有多少个结点的值与x的值相等
int CountLeaf (BTNode *P, int& num, int x)
{
if ( P )
{
if (( P->lchild == NULL)&& ( P->rchild == NULL) && ( P->data == x))
num++; // 对叶子结点计数
if (( !P->lchild) && ( !P->rchild))
{
CountLeaf( P->lchild, num, x);
CountLeaf( P->rchild, num, x);
}
}
return num;
}
2、已知一棵二叉链表方式存储的二叉树，编写算法计算二叉树的高度。
typedef struct BTNode
{
int data;
struct BTNode *lchild ; //左孩子指针
struct BTNode *rchild; // 右孩子指针
} BTNode;//二叉链表的结构
int TreeHeight(BTNode *root)
{
if (root == NULL)
{
return 1; //如果是只有根节点，高度记为1
}
else
{ //否则递归计算其左右孩子的高度然后在加上根节点的层数1
return 1+max(TreeHeight(root->lchild),TreeHeight(root->rchild));
}
}
总结
以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，谢谢大家对小牛知识库的支持。如果你想了解更多相关内容请查看下面相关链接
-
统计二叉树的叶结点个数 根据带虚结点的先序序列建立二叉树，计算其叶子结点的数目后输出。 输入格式: 测试数据有多组，处理到文件尾。每组测试数据在一行中输入一个字符串（不含空格且长度不超过80），表示二叉树的先序遍历序列，其中字符*表示虚结点（对应的子树为空）。 输出格式: 对于每组测试，输出所建立的二叉树的叶子结点数目。输出格式为：“leaf:num”，其中num 为二叉树的叶结点个数。 输入样例
-
问题查找具有n个节点的完整二叉树中的叶节点数。 我为上述问题编写了一个递归程序，每当我到达一个没有子节点的节点时，遍历树并增加叶节点的数量。但由于这棵树是一棵完整的二叉树，我认为这会使问题变得更容易，但我不知道如何解决。它是否可以简化为紧凑形式（类似于公式）。
-
这是一个相当简单的问题，我注意到当我表示一棵树时，无论我用哪种方式(后排序，按顺序，前排序)树叶总是以相同的顺序出现，从左到右。 我只是想知道为什么，这是有原因的吗？ 我刚开始研究它们，就想到了这个。 编辑： 我有一棵这样的树: 叶节点为：D、E和F 预购顺序为：A、B、D、C、E、F 顺序是：D，B，A，E，C，F 后序是:D，B，E，F，C，A 叶子节点总是从左到右出现，不管我选择哪个顺序，问
-
class Node(object): def __init__(self, data, left=None, right=None): self.data = data self.left = left self.right = right tree = Node(1, Node(3, Node(7, Node(0)), Node(6)), Node(2, Node
-
所以，我想做的是检查一个完整的二叉树叶子中的 int 是否比它的父叶大，并以此为标准让它与它的父叶不断改变位置，一直到根。问题是，当它必须与根进行比较和更改位置时，它会塞格福;如果我在那之前让循环停止，它工作得很好（我认为）。我在这里错过了一些明显的东西吗？ 添加新叶子时，将发生以下情况。我省略了叶子实际添加到树中的部分，因为它工作正常并且很长。指针 p 指向循环开始之前插入的最后一个叶。根的父亲
-
如何计算二叉树中最小级别所有叶节点的总和。如果不存在树，则应返回-1。 例子： 对于上述二叉树，返回100（40 60） （图片来源：Geeksforgeks）