平衡二叉樹_ZenDei技術網路在線

1.平衡二叉樹定義:如果一棵樹不為空,其任意節點的左子樹高度與右子樹高度之差不超過1,那麼滿足這樣條件的樹就是平衡二叉樹 2.平衡二叉樹節點定義：這裡平衡二叉樹節點定義使用了模版，這樣就可以任意自定義節點，using BINNODE = tagNode<T>則是為節點類型起一個別名， using ...

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

　　下麵手工建立一顆二叉樹(現在還不是平衡二叉樹，僅僅是顆二叉樹):

 1  CBinTree<int> binTree;
 2   BINNODE<int> node1(1);
 3   BINNODE<int> node2(2);
 4   BINNODE<int> node3(3);
 5   BINNODE<int> node4(4);
 6   BINNODE<int> node5(5);
 7   BINNODE<int> node6(6);
 8   BINNODE<int> node7(7);
 9   BINNODE<int> node8(8);
10   BINNODE<int> node9(9);
11   BINNODE<int> node10(10);
12   BINNODE<int> node11(11);
13   BINNODE<int> node12(12);
14 
15   node1.m_pLeftNode = &node2;
16   node1.m_pRightNode = &node5;
17   node2.m_pLeftNode = &node3;
18   node2.m_pRightNode = &node4;
19   node3.m_pLeftNode = &node10;
20   node3.m_pRightNode = &node11;
21   node11.m_pLeftNode = &node12;
22   node4.m_pRightNode = &node6;
23   node5.m_pLeftNode = &node7;
24   node5.m_pRightNode = &node9;
25   node7.m_pRightNode = &node8;

View Code

　　上述代碼建立的二叉樹大概長這個樣子:

　　現在用上面的遞歸先序遍歷遍歷這個樹，訪問節點時輸出每個節點值，

　　所以我繼承一下類模版CTraversalFunction並實現函數調用運算符：

 1 class MyTraversalFunc :public CTraversalFunction<int>
 2 {
 3   virtual void operator()(PBINNODE<int>  pNode);
 4 };
 5 
 6 
 7 void MyTraversalFunc::operator()(PBINNODE<int>  pNode)
 8 {
 9   std::cout << pNode->m_element <<" ";
10 }

View Code

　　然後用下麵代碼測試下遞歸先序遍歷:

1   binTree.m_pRoot = &node1;
2   MyTraversalFunc funcObj;
3   binTree.PreOrderRecuursiveTraversal(funcObj, binTree.m_pRoot);

View Code

　　結果：

　　順便提下函數對象，好像是C++11標準才有的東西，當一個函數重載了函數調用運算符後，

　　這個類產生的對象也稱為為函數對象，例如在上面代碼的第15行直接通過函數調用運算符調用函數，

　　而無需通過FuncOfTravs.xxxx(....)的方式來調用成員函數，此時類對象FuncOfTravs仿佛就像一個函數一樣。

　　傳統的C函數只能通過函數傳參來攜帶信息，但是函數對象可以不用通過參數就能攜帶任意信息，

　　這讓我想起了Windows的線程回調函數，當我們使用CreateThread或者更安全的_beginThreadEx時,

　　線程回調函數只能攜帶一個參數，所以一般都定義一個結構體，將這個結構體變數作為參數傳遞給線程回調函數，

　　但是個人感覺函數對象攜帶參數的方式比這些回調函數更優雅些，嗯.......又扯遠了。

　　上述的函數調用操作符為我定義成純虛函數，對於任何自定義的數據類型，只要繼承

　　該類模版，並實現虛函數調用運算符即可實現對自定義節點的遍歷。

遞歸遍歷看起來代碼比較簡潔，但是每執行一次遞歸調用對線程棧都會消耗一點，

　　程式運行時每個線程的棧空間的大小都是固定的，例如，在我的VS中:項目屬性->鏈接器->系統，頁面如下

　　預設情況下棧保留大小為1MB，也可以設置為我們想要的大小。

　　如果遞歸比較深，耗盡了當前的線程棧，那麼程式會被終止。

　　其實，我們也可以使用數據結構中的棧，棧中節點從堆中分配，

　　用迴圈來模擬遞歸調用，也能實現想要的功能，下麵給出先序

　　遍歷的非遞歸調用代碼：

 1 //************************************************************************
 2 // 函數名稱:  PreOrderTraversal
 3 // 函數功能:  先序遍歷二叉樹(非遞歸實現)
 4 // 所屬許可權:  public 
 5 // 返回的值:  bool
 6 // 函數參數:  CTraversalFunction<T> & FuncOfTravs:訪問節點時使用的函數對象
 7 // 函數參數:  PBINNODE<T> pTravsralPos:遍歷位置
 8 // 註意事項: 
 9 //************************************************************************
10 template<typename T>
11 bool CBinTree<T>::PreOrderTraversal(CTraversalFunction<T> & FuncOfTravs, 
12                                     PBINNODE<T> pTravsralPos)
13 {
14     std::stack<PBINNODE<T>> tmpStack;
15     tmpStack.push(pTravsralPos);
16     PBINNODE<T> pCurrNode = nullptr;
17     while (!tmpStack.empty())
18     {
19         pCurrNode = tmpStack.top();
20         tmpStack.pop();
21         FuncOfTravs(pCurrNode);
22 
23         //在遍歷過程中先將以pCurrNode為根節點的右孩子節點指針入棧，
24         //在將其左孩子指針入棧,這樣的入棧順序可以達到先根遍歷的目的
25         if (pCurrNode->m_pRightNode != nullptr)
26         {
27             //當前已經訪問節點的右孩子存在則入棧
28             tmpStack.push(pCurrNode->m_pRightNode);
29         }
30         
31         if (pCurrNode->m_pLeftNode != nullptr)
32         {
33           tmpStack.push(pCurrNode->m_pLeftNode);
34         }
35     }
36     return true;
37 }

View Code

　　運行結果：

　　運行結果與遞歸實現的先序遍歷相同，為了模擬遞歸調用這裡用到迴圈，

　　先將根節點入棧，在迴圈中先將根節點出棧並訪問，先序遍歷是先訪問

　　根節點，然後訪問左子樹，在右子樹，而數據結構中的棧是先入後出的，

　　所以入棧時要先將右孩子入棧，在入棧左孩子，這樣出棧時是先出左孩

　　子，在出右孩子，就能實現先序遍歷。

　　先寫到這，睡覺。