算法思想：
对每个节点来说：
1、如果它没有子节点，那么它就是叶子节点。
2、如果它有子节点，那么它的叶子节点数量 = 左子树叶子节点数量 + 右子树叶子节点数量。
算法代码：
unsigned int getLeafCount(struct node node){
if(node == NULL)
return 0;
if(node->left == NULL && node->right==NULL)
return 1;
else
return getLeafCount(node->left)+
getLeafCount(node->right);
}
时间复杂度：O(n)，空间复杂度：O(n)
---------------------------------------------------
附上一个例子：
#include <stdioh>#include <stdlibh>
/ A binary tree node has data, pointer to left child
and a pointer to right child /
struct node
{
int data;
struct node left;
struct node right;
};
/ Function to get the count of leaf nodes in a binary tree/
unsigned int getLeafCount(struct node node)
{
if(node == NULL)
return 0;
if(node->left == NULL && node->right==NULL)
return 1;
else
return getLeafCount(node->left)+
getLeafCount(node->right);
}
/ Helper function that allocates a new node with the
given data and NULL left and right pointers /
struct node newNode(int data)
{
struct node node = (struct node)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
/Driver program to test above functions/
int main()
{
/create a tree/
struct node root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
/get leaf count of the above created tree/
printf("Leaf count of the tree is %d", getLeafCount(root));
getchar();
return 0;
}
TreeView获取不到选中的子节点的值写了个简单的树形结构，想获取每个节点的值，但是点击父节点使用TreeView的SelectedNode可以获取选中的节点
也在网上查了一些资料，但是，基本上都是通过各种方法使用SelectedNode获取！
方法如下：
新建了一个NM_Click消息响应函数，用
hParent = m_TreeCtrlGetSelectedItem();
m_TreeCtrlGetItemText(hParent);
获取当前选中的文本，但获取的竟然是前一次点击的文本，而非当前点击的文本，请问这是问什么？怎样才能正确获取当前点击的文本？
用OnSelectChanged获得的方法，是有缺陷的，例如两次都点同一个项，那么就不能执行了
解决方法：
DWORD dwpos = GetMessagePos();
TVHITTESTINFO ht = {0};
htptx = GET_X_LPARAM(dwpos);
htpty = GET_Y_LPARAM(dwpos);
::MapWindowPoints(HWND_DESKTOP,pNMHDR->hwndFrom,&htpt,1); //把屏幕坐标转换成控件坐标
TreeView_HitTest(pNMHDR->hwndFrom,&ht); //确定点击的是哪一项
strOpcServerName = m_OpcServerListGetItemText(hthItem);
计算公式：n0=n2+1，n0是叶子节点的个数，n2是度为2的结点的个数。
在数据结构中，树是一种非线性的数据结构，它由节点和边组成，每个节点可以有零个或多个子节点。树的叶子节点是指没有子节点的节点，也可以称作终端节点或者叶节点。
计算叶子节点的个数通常有两种方法：
递归法：从根节点开始遍历整棵树，对于每个节点，如果它没有子节点，那么就将计数器加一，否则就递归遍历它的每个子节点。
非递归法：使用栈或队列等数据结构来遍历整棵树，对于每个节点，如果它没有子节点，那么就将计数器加一，否则就将它的子节点入队或入栈，继续遍历。
需要注意的是，在计算树的叶子节点时，需要排除空树的情况，即树中没有任何节点的情况。
(1)
# # # # #
/ \ / \ / \ / \ / \
# # # # # # # # # #
/ \ / \ / \ / / \ /
# # # # # # # # # #
图一 图二 图三 图四 图五
完全二叉树的定义:
若设二叉树的深度为h，除第h层外，其它各层(1 ～ h-1)的结点数都达到最大个数，
第h层所有的结点都连续集中在最左边，这就是完全二叉树。
图一、二、三、四、五 都是完全二叉树
图一既是满二叉树,也是完全二叉树
(图一)是完全二叉树,有三层,n=3,其总节点数是 2^n-1 = 2^3-1 = 8-1 = 7
最底层的节点都是叶子,而叶子的总数量是 2^(n-1) = 2^(3-1) = 4
(图二)最底层去掉1个叶子,最底层剩下的叶子数量是4-1=3,而次最底层补充了叶子,
补充的叶子数量是1/2=0(去掉小数),没有补充叶子,二叉树的叶子总数量是3+0=3
(图三)最底层去掉2个叶子,最底层剩下的叶子数量是4-2=2,而次最底层补充了叶子,
补充的叶子数量是2/2=1,所以,二叉树的叶子总数量是2+1=3
(图四)最底层去掉3个叶子,最底层剩下的叶子数量是4-3=1,而次最底层补充了叶子,
补充的叶子数量是3/2=1(去掉小数),所以,二叉树的叶子总数量是1+1=2
(图五)最底层去掉4个叶子,最底层剩下的叶子数量是4-4=0,而次最底层补充了叶子,
补充的叶子数量是4/2=2,所以,二叉树的叶子总数量是0+2=2
初步总结:
满二叉树有n层,总节点数是2^n-1,最底层的叶子总数是2^(n-1)
将"满二叉树"去掉一些叶子,改为"完全二叉树",现在,该"完全二叉树"的总节点数是m,
也就是说"被去掉"的叶子总数量是 2^n - 1 - m
最底层的叶子剩下的数量是 2^(n-1) - (2^n-1-m)
次最底层补充了叶子,补充的叶子数量是(2^n-1-m)/2
该"完全二叉树"的叶子总数量 Y = 2^(n-1) - (2^n-1-m) + (2^n-1-m)/2
整理上述Y等式,得到 Y = 2^(n-1) - (2^n)/2 + m/2 + 1/2
进一步整理,Y = 2^(n-1) - 2^(n-1) + m/2 + 1/2
所以,Y = (m+1)/2 ["完全二叉树"的Y公式,Y是叶子总数量,m是总结点数]
初步验证该公式:
图一,"完全二叉树"的总节点数m=7,叶子总数量Y=(m+1)/2=(7+1)/2=4
图二,"完全二叉树"的总节点数m=6,叶子总数量Y=(m+1)/2=(6+1)/2=3 (去掉小数)
图三,"完全二叉树"的总节点数m=5,叶子总数量Y=(m+1)/2=(5+1)/2=3
图四,"完全二叉树"的总节点数m=4,叶子总数量Y=(m+1)/2=(4+1)/2=2 (去掉小数)
图五,"完全二叉树"的总节点数m=3,叶子总数量Y=(m+1)/2=(3+1)/2=2
原题目是"完全二叉树 共有703个节点,求叶子节点数",
答:"完全二叉树"的叶子节点数 Y = (m+1)/2 = (703+1)/2 = 352
(2)其它类似的问题
一颗完全二叉树共有700个节点，则该完全二叉树的叶子节点数为多少？
答: "完全二叉树"的叶子节点数 Y = (m+1)/2 = (700+1)/2 = 350 (去掉小数)
一棵完全二叉树共有599个结点，则该完全二叉树的叶子节点数为多少？
答: "完全二叉树"的叶子节点数 Y = (m+1)/2 = (599+1)/2 = 300
要构建的无限分类的模型 电子产品是最大的分类家用电器 ,数码产品是其子分类可以看到子分类是被父分类包含起来的每个分类都有左右 两个节点编号分别是1、2、3
根据上面的图mysql中建立表和插入数据
CREATE TABLE `product_categories` (
`id` MEDIUMINT( 8 ) NOT NULL AUTO_INCREMENT PRIMARY KEY ,`name` VARCHAR( 20 ) NOT NULL ,
`left_node` MEDIUMINT( 8 ) NOT NULL ,
`right_node` MEDIUMINT( 8 ) NOT NULL
) ENGINE = MYISAM CHARACTER SET utf8 COLLATE utf8_general_ci;INSERT INTO `product_categories` (`id`, `name`, `left_node`, `right_node`) VALUES(1, '电子产品', 1, 20),
(2, '家用电器', 2, 9),
(3, '电视机', 3, 4),
(4, '电冰箱', 5, 6),
(5, '空调', 7, 8),
(6, '数码产品', 10, 19),
(7, '电脑', 11, 18),
(8, '台式电脑', 12, 13),
(9, '笔记本电脑', 14, 15),
(10, '平板电脑', 16, 17);
表结构如下：
下面是PHP的实例代码：
1、获取所有节点
<php
$pdo = new PDO(
'mysql:host=localhost;dbname=test',
'root',
''
);
$pdo->exec("SET NAMES UTF8");
$stmt = $pdo->prepare("SELECT cname FROM product_categories as c, product_categories as pWHERE cleft_node BETWEEN pleft_node AND pright_nodeAND pname='电子产品' ORDER BY cleft_node");$stmt->execute();
$rs=$stmt->fetchAll(PDO::FETCH_ASSOC);
foreach($rs as $v){
echo $v['name']'<br />';
}
输出：
电子产品
家用电器
电视机
电冰箱
空调
数码产品
电脑
台式电脑
笔记本电脑
平板电脑
2、 获取某个父节点以及其所有子节点
<php
$pdo = new PDO(
'mysql:host=localhost;dbname=test',
'root',
''
);
$pdo->exec("SET NAMES UTF8");
$stmt = $pdo->prepare("SELECT cname FROM product_categories as c, product_categories as pWHERE cleft_node BETWEEN pleft_node AND pright_nodeAND pname='数码产品' ORDER BY cleft_node");$stmt->execute();
$rs=$stmt->fetchAll(PDO::FETCH_ASSOC);
foreach($rs as $v){
echo $v['name']'<br />';
}
输出：
数码产品
电脑
台式电脑
笔记本电脑
平板电脑
3、获取所有的叶子节点
<php
$pdo = new PDO(
'mysql:host=localhost;dbname=test',
'root',
''
);
$pdo->exec("SET NAMES UTF8");
$stmt = $pdo->prepare("SELECT name FROM product_categories where right_node-left_node=1");$stmt->execute();
$rs=$stmt->fetchAll(PDO::FETCH_ASSOC);
foreach($rs as $v){
echo $v['name']'<br />';
}
输出:
电视机
电冰箱
空调
台式电脑
笔记本电脑
平板电脑
4、获取某个子节点及其所有父节点
<php
$pdo = new PDO(
'mysql:host=localhost;dbname=test',
'root',
''
);
$pdo->exec("SET NAMES UTF8");
$stmt = $pdo->prepare("SELECT pname FROM product_categories AS c, product_categories AS p WHERE cleft_node BETWEEN pleft_node AND pright_node AND cname = '平板电脑' ORDER BY pleft_node");$stmt->execute();
$rs=$stmt->fetchAll(PDO::FETCH_ASSOC);
foreach($rs as $v){
echo $v['name']'<br />';
}
输出：
电子产品
数码产品
电脑
平板电脑
5、获取所有节点极其所处的层级
<php
$pdo = new PDO(
'mysql:host=localhost;dbname=test',
'root',
''
);
$pdo->exec("SET NAMES UTF8");
$stmt = $pdo->prepare("SELECT cname, (COUNT(pname) - 1) AS level FROM product_categories AS c, product_categories AS p WHERE cleft_node BETWEEN pleft_node AND pright_node GROUP BY cname ORDER BY cleft_node");$stmt->execute();
$rs=$stmt->fetchAll(PDO::FETCH_ASSOC);
var_dump($rs);
echo '<br />';
foreach($rs as $v){
echo $v['name']' level:'$v['level']'<br />';}
输出：
电子产品 level:0
家用电器 level:1
电视机 level:2
电冰箱 level:2
空调 level:2
数码产品 level:2
电脑 level:2
台式电脑 level:3
笔记本电脑 level:3
平板电脑 level:3
6、获取某个节点的层级
<php
$pdo = new PDO(
'mysql:host=localhost;dbname=test',
'root',
''
);
$pdo->exec("SET NAMES UTF8");
$stmt = $pdo->prepare("SELECT cname, (COUNT(pname) - 1) AS level FROM product_categories AS c, product_categories AS p WHERE cleft_node BETWEEN pleft_node AND pright_node and cname='平板电脑' GROUP BY cname ORDER BY cleft_node");$stmt->execute();
$rs=$stmt->fetchAll(PDO::FETCH_ASSOC);
var_dump($rs);
echo '<br />';
foreach($rs as $v){
echo $v['name']' level:'$v['level']'<br />';}
输出：
平板电脑 level:3
7、在某个节点后平行的插入一个节点
<php
$pdo = new PDO(
'mysql:host=localhost;dbname=test',
'root',
''
);
$pdo->exec("SET NAMES UTF8");
function addNode($left_node,$new_node){
global $pdo;
$stmt = $pdo->prepare("SELECT right_node FROM product_categories WHERE name = '$left_node'");$stmt->execute();
$rs=$stmt->fetch(PDO::FETCH_ASSOC);
$right_node=$rs['right_node'];
$pdo->exec("UPDATE product_categories SET right_node = right_node + 2 WHERE right_node > $right_node");$pdo->exec("UPDATE product_categories SET left_node = left_node + 2 WHERE left_node > $right_node");$pdo->exec("INSERT INTO product_categories(name, left_node, right_node) VALUES('$new_node', $right_node + 1, $right_node + 2)");}
addNode('家用电器','办公用品');
完成之后表结构如下：
8、删除某个节点及其所有子节点
<php
$pdo = new PDO(
'mysql:host=localhost;dbname=test',
'root',
''
);
$pdo->exec("SET NAMES UTF8");
function deleteNode($node_name){
global $pdo;
$stmt = $pdo->prepare("SELECT left_node,right_node, right_node - left_node + 1 as width FROM product_categories WHERE name ='$node_name'");$stmt->execute();
$rs=$stmt->fetch(PDO::FETCH_ASSOC);
$left_node=$rs['left_node'];
$right_node=$rs['right_node'];
$width=$rs['width'];
$pdo->exec("DELETE FROM product_categories WHERE left_node BETWEEN $left_node AND $right_node");$pdo->exec("UPDATE product_categories SET right_node = right_node - $width WHERE right_node > $right_node");$pdo->exec("UPDATE product_categories SET left_node = left_node - $width WHERE left_node > $right_node");}
deleteNode('数码产品');
完成之后表结构如下：
可以看到用多叉树的方式构建无限分类,查询的时候是非常简便的但是在插入新的节点和删除节点时就比较麻烦了
先定义一个nodevarnode:TTreeNode;然后你获取你所选中的节点node:=TreeViewSelected;它的父节点的名称就是nodeParentText它的祖父节点的名称就是nodeParentParentText以此类推注意，在访问父节点之前要判断是否存在ifnodeParentnilthenbeginend;
以上就是关于求统计二叉树叶子结点数的递归算法全部的内容，包括:求统计二叉树叶子结点数的递归算法、如何查找Treeview控件的叶子节点、VC6.0中，CTreeCtrl如何得到选择的当前节点的叶子节点的个数啊等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）