首页 > > 程序设计 > C/C++ >

平衡二叉树

2018-12-17 10:46:27来源：博客园阅读 ()

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;
};

　　顺便提下函数对象，好像是C++11标准才有的东西，当一个函数重载了函数调用运算符后，

　　这个类产生的对象也称为为函数对象，例如在上面代码的第15行直接通过函数调用运算符调用函数，

　　而无需通过FuncOfTravs.xxxx(....)的方式来调用成员函数，此时类对象FuncOfTravs仿佛就像一个函数一样。

　　传统的C函数只能通过函数传参来携带信息，但是函数对象可以不用通过参数就能携带任意信息，

　　这让我想起了Windows的线程回调函数，当我们使用CreateThread或者更安全的_beginThreadEx时,

　　线程回调函数只能携带一个参数，所以一般都定义一个结构体，将这个结构体变量作为参数传递给线程回调函数，

　　但是个人感觉函数对象携带参数的方式比这些回调函数更优雅些，嗯.......又扯远了。

　　上述的函数调用操作符为我定义成纯虚函数，对于任何自定义的数据类型，只要继承

　　该类模版，并重写函数调用运算符即可实现对自定义节点的遍历。

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有