二叉树算法思想

Ⅰ 求二叉树高度的原理、算法是什么，越详细越好，C语言，谢谢

首先分析二叉树的深度（高度）和它的左、右子树深度之间的关系。从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由此，需先分别求得左、右子树的深度，算法中“访问结点”的操作为：求得左、右子树深度的最大值，然后加
1
。
int
Depth
(BiTree
T
){
//
返回二叉树的深度
if
(
!T
)
depthval
=
0;
else
{
depthLeft
=
Depth(
T->lchild
);
depthRight=
Depth(
T->rchild
);
depthval
=
1
+
(depthLeft
>
depthRight
?
depthLeft
:
depthRight);
}
return
depthval;
}

Ⅱ 最优二叉树算法基本概念

最优二叉树，也被称为哈夫曼树，是一种特殊的二叉树结构，其目标是在一组带权的叶节点中，构建出具有最小带权路径长度的树。带权路径长度，是对二叉树路径长度概念的扩展，它指的是从根节点到所有叶节点的路径长度之和，每个路径长度与对应节点的权值相乘。记为：WPL = Wk·Lk，其中Wk表示第k个叶节点的权值，Lk是其路径长度。

举个例子，如图所示的二叉树，其带权路径长度WPL计算为2×2+4×2+5×2+3×2=28。对于一组特定的叶节点，例如权值为1，3，5，7，可以构建出多种不同形态的带权二叉树，每种树的带权路径长度都会有所不同。如图中的5种二叉树，它们的带权路径长度分别是：

• (a) WPL = 1×2+3×2+5×2+7×2 = 32


• (b) WPL = 1×3+3×3+5×2+7×1 = 29


• (c) WPL = 1×2+3×3+5×3+7×1 = 33


• (d) WPL = 7×3+5×3+3×2+1×1 = 43


• (e) WPL = 7×1+5×2+3×3+1×3 = 29

最优二叉树算法的任务就是，在给定的带权叶节点集合中，找出这样一个二叉树，它的带权路径长度是最小的，即它是最优的二叉树。这样的算法在数据压缩、编码等领域中有着广泛应用。

Ⅲ 二叉树算法是什么

二叉树是每个节点最多有两个子树的有序树。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用于实现二叉查找树和二叉堆。

性质

1、在二叉树中，第i层的结点总数不超过2^(i-1)。

2、深度为h的二叉树最多有2^h-1个结点（h>=1)，最少有h个结点。

3、对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1。