二叉树的一些算法<未完>

求二叉树中距离最远的2个节点的距离

本文中二叉树结构定义为:

1
2
3
4
5
6
本文中二叉树结构定义为:
struct Node {
 Node* left;
 Node* right;
 int data;
};

定义:空二叉树的高度为-1,只有根节点的二叉树高度为0,根节点在0层,深度为0。

两个节点的距离为两个节点间最短路径的长度。

求两节点的最远距离,实际就是求二叉树的直径。假设相距最远的两个节点分别为A、B,它们的最近共同父节点(允许一个节点是其自身的父节点)为C,则A到B的距离 = A到C的距离 + B到C的距离

节点A、B分别在C的左右子树下(假设节点C的左右两子树均包括节点C),不妨假设A在C的左子树上,由假设“A到B的距离最大”,先固定B点不动(即B到C的距离不变),根据上面的公式,可得A到C的距离最大,即点A是C左子树下距离C最远的点,即:

A到C的距离 = C的左子树的高度

同理,   B到C的距离 = C的右子树的高度

   因此,本问题可以转化为:“二叉树每个节点的左右子树高度和的最大值”。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
static int tree_height(const Node* root, int& max_distance)
{
 const int left_height = root->left ? tree_height(root->left,  max_distance) + 1 : 0;
 const int right_height = root->right ? tree_height(root->right, max_distance)  + 1 : 0;
 const int distance = left_height + right_height;
 if (max_distance < distance) max_distance = distance;
 return (left_height > right_height ? left_height : right_height);
}
  
int tree_diameter(const Node* root)
{
 int max_distance = 0;
 if (root) tree_height(root, max_distance);
 return max_distance;
}

  

判断二叉树是否平衡二叉树

根据平衡二叉树的定义:每个结点的左右子树的高度差小等于1,只须在计算二叉树高度时,同时判断左右子树的高度差即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
static int tree_height(const Node* root, bool& balanced)
{
 const int left_height = root->left ? tree_height(root->left, balanced) + 1 : 0;
 if (!balanced) return 0;
  
 const int right_height = root->right ? tree_height(root->right, balanced) + 1 : 0;
 if (!balanced) return 0;
  
 const int diff = left_height - right_height;
 if (diff < -1 || diff > 1) balanced = false;
 return (left_height > right_height ? left_height : right_height);
}
  
bool is_balanced_tree(const Node* root)
{
 bool balanced = true;
 if (root) tree_height(root, balanced);
 return balanced;
}

  

 

 

 


==============================================================================
本文转自被遗忘的博客园博客,原文链接:http://www.cnblogs.com/rollenholt/archive/2012/05/12/2497299.html,如需转载请自行联系原作者

上一篇:Azure实践系列 2:Azure AD中的用户管理


下一篇:nagios监控流量脚本