平衡二叉树 - 技术经验

平衡二叉树

来源：cnblogs　　作者：xhqxhq　　时间：2018/12/17 9:47:30　　对本文有异议

1.平衡二叉树定义:如果一棵树不为空,其任意节点的左子树高度与右子树高度之差不超过1,那么满足这样条件的树就是平衡二叉树

2.平衡二叉树节点定义：

 1 template<typename T>
 2 struct tagNode
 3 {
 4   T                   m_element;     //树节点所存储的元素节点
 5   struct tagNode<T> * m_pLeftNode;   //指向左孩子节点
 6   struct tagNode<T> * m_pRightNode;  //指向右孩子节点
 7   struct tagNode<T> * m_pParentNode; //指向父节点
 8   int                 m_nHeightOfNode;//节点高度
 9   tagNode(T value,
10           tagNode<T> * pLeftNode = nullptr,
11           tagNode<T> *pRightNode = nullptr,
12           tagNode<T> *pParentNode = nullptr);
13 };
14 
15 template<typename T>
16 tagNode<T>::tagNode(T value,
17                     tagNode<T> * pLeftNode,
18                     tagNode<T> *pRightNode,
19                     tagNode<T> *pParentNode):
20 m_element(value),
21 m_pLeftNode(pLeftNode),
22 m_pRightNode(pRightNode),
23 m_pParentNode(pParentNode),
24 m_nHeightOfNode(0)
25 {
26 
27 }
28 
29 
30 template<typename T>
31 using BINNODE = tagNode<T>;
32 
33 template<typename T>
34 using PBINNODE = tagNode<T>*;

　　这里平衡二叉树节点定义使用了模版，这样就可以任意自定义节点，using BINNODE = tagNode<T>则是为节点类型起一个别名，

　　using PBINNODE = tagNode<T>*则使为该节点类型的指针起一个别名，因为该节点类型的定义使用了模版，

　　所以只能用using关键字来起别名，不能使用typedef来起别名，有点扯远了。。。。

3.平衡二叉树的遍历:

　　这里限定左子树比右子树优先遍历，所以一共有三种遍历：先序遍历，中序遍历，后序遍历

　　　　下面将结合图3-1，来解释这三种遍历方式

　　　　先序遍历:访问当前的根节点节点，然后遍历左子树，如果左子树为空则遍历右子树，

　　　　　　　　如果右子树为空，则向上寻找到一个可以继续向右遍历的节点重复该过程，

　　　　　　　　直到所有节点遍历完成

对于上图，先序遍历的结果是：4->2->1->3->9->7->5->8->10->12

　　　　下面分别给出先序遍历的递归实现和非递归实现:

　　　　递归先序遍历:

 1 //************************************************************************
 2 // 函数名称:  CBinTree<T>::PreOrderRecuursiveTraversal
 3 // 函数功能:  先序遍历二叉树(递归实现)
 4 // 所属权限:  public 
 5 // 返回的值:  bool
 6 // 函数参数:  CTraversalFunction<T> & FuncOfTravs:访问节点时使用的函数对象
 7 // 函数参数:  PBINNODE<T> pTravsralPos:遍历位置
 8 // 注意事项: 
 9 //************************************************************************
10 template<typename T>
11 bool CBinTree<T>::PreOrderRecuursiveTraversal(CTraversalFunction<T> & FuncOfTravs, PBINNODE<T> pTravsralPos)
12 {
13     if (pTravsralPos != nullptr)
14     {
15         FuncOfTravs(pTravsralPos);
16         PreOrderRecuursiveTraversal(FuncOfTravs, pTravsralPos->m_pLeftNode);
17         PreOrderRecuursiveTraversal(FuncOfTravs, pTravsralPos->m_pRightNode);
18     }
19     return true;
20 }

　　这里函数第一个参数FuncOfTravs是一个函数对象，其定义如下：

//用于遍历时所用的函数对象,由子类实现函数调用运算符的重载,
//在函数调用运算符中子类实现对节点进行如何操作
template<typename T>
class CTraversalFunction
{
public:
  virtual void operator()(PBINNODE<T> pNode) = 0;
};