十三、左偏樹（Leftist Tree）
樹這個數據結構內容真的很多，上一節所講的二叉堆，其實就是一顆二叉樹，這次講的左偏樹（又叫“左翼堆”），也是樹。
二叉堆是個很不錯的數據結構，因為它非常便于理解，而且僅僅用了一個數組，不會造成額外空間的浪費，但它有個缺點，那就是很難合并兩個二叉堆，對于“合并”，“拆分”這種操作，我覺得最方面的還是依靠指針，改變一下指針的值就可以實現，要是涉及到元素的移動，那就復雜一些了。
左偏樹跟二叉堆比起來，就是一棵真正意義上的樹了，具有左右指針，所以空間開銷上稍微大一點，但卻帶來了便于合并的便利。BTW：寫了很多很多的程序之后，我發覺“空間換時間”始終是個應該考慮的編程方法。:)
左偏左偏，給人感覺就是左子樹的比重比較大了，事實上也差不多，可以這么理解：左邊分量重，那一直往右，就一定能最快地找到可以插入元素的節點了。所以可以這樣下個定義：左偏樹就是對其任意子樹而言，往右到插入點的距離（下面簡稱為“距離”）始終小于等于往左到插入點的距離，當然了，和二叉堆一樣，父節點的值要小于左右子節點的值。
如果節點本身不滿，可插入，那距離就為0，再把空節點的距離記為-1，這樣我們就得出：父節點的距離 = 右子節點距離 + 1，因為右子節點的距離始終是小于等于左子節點距離的。我把距離的值用藍色字體標在上圖中了。
左偏樹并一定平衡，甚至它可以很不平衡，因為它其實也不需要平衡，它只需要像二叉堆那樣的功能，再加上合并方便，現在來看左偏樹的合并算法，如圖：
這種算法其實很適合用遞歸來做，但我還是用了一個循環，其實也差不多。對于左偏樹來說，這個合并操作是最重要最基本的了。為什么？你看哦：Enqueue，我能不能看作是這個左偏樹的root和一個單節點樹的合并？而Dequeue，我能不能看作是把root節點取出來，然后合并root的左右子樹？事實上就是這樣的，我提供的代碼就是這樣干的。
Conclusion：左偏樹比同二叉堆的優點就是方便合并，缺點是編程復雜度略高（也高不去哪），占用空間稍大（其實也大不去哪）。附上代碼，老樣子了，單個文件，直接調試的代碼，零依賴零配置，一看就懂，代碼雖然不算完美，但作為演示和學習，是足夠了。
#include <stdio.h>
// TreeNode
//////////////////////////////////////////////////////////////////////////
struct TreeNode
{
TreeNode(int iVal)
{
m_iData = iVal;
m_iDistance = 0;
m_pLeft = 0;
m_pRight = 0;
}
~TreeNode()
{
}
void SwapLeftRight()
{
TreeNode *pTmp = m_pLeft;
m_pLeft = m_pRight;
m_pRight = pTmp;
}
void UpdateDistance()
{
m_iDistance = GetRightDistance()+1;
}
int GetLeftDistance()
{
return m_pLeft!=0?m_pLeft->m_iDistance:-1;
}
int GetRightDistance()
{
return m_pRight!=0?m_pRight->m_iDistance:-1;
}
int m_iData;
int m_iDistance;
TreeNode* m_pLeft;
TreeNode* m_pRight;
};
// Stack
//////////////////////////////////////////////////////////////////////////
class Stack
{
public:
Stack(int iAmount = 10);
~Stack();
//return 1 means succeeded, 0 means failed.
int Pop(TreeNode* & val);
int Push(TreeNode* val);
int Top(TreeNode* & val);
//iterator
int GetTop(TreeNode* &val);
int GetNext(TreeNode* &val);
private:
TreeNode** m_pData;
int m_iCount;
int m_iAmount;
//iterator
int m_iCurr;
};
Stack::Stack(int iAmount)
{
m_pData = new TreeNode*[iAmount];
m_iCount = 0;
m_iAmount = iAmount;
m_iCurr = 0;
}
Stack::~Stack()
{
delete m_pData;
}
int Stack::Pop(TreeNode* & val)
{
if(m_iCount>0)
{
--m_iCount;
val = m_pData[m_iCount];
return 1;
}
return 0;
}
int Stack::Push(TreeNode* val)
{
if(m_iCount<m_iAmount)
{
m_pData[m_iCount] = val;
++m_iCount;
return 1;
}
return 0;
}
int Stack::Top(TreeNode* & val)
{
if(m_iCount>0 && m_iCount<=m_iAmount)
{
val = m_pData[m_iCount-1];
return 1;
}
return 0;
}
int Stack::GetTop(TreeNode* &val)
{
if(m_iCount>0 && m_iCount<=m_iAmount)
{
val = m_pData[m_iCount-1];
m_iCurr = m_iCount - 1;
return 1;
}
return 0;
}
int Stack::GetNext(TreeNode* &val)
{
if((m_iCurr-1)<(m_iCount-1) && (m_iCurr-1)>=0)
{
--m_iCurr;
val = m_pData[m_iCurr];
return 1;
}
return 0;
}
// LeftistTree
//////////////////////////////////////////////////////////////////////////
class LeftistTree
{
public:
LeftistTree();
~LeftistTree();
//return 0 means failed.
int Dequeue(int& iVal);
int Enqueue(int iVal);
//returns the merged root.
TreeNode* Merge(TreeNode *pT1, TreeNode *pT2);
TreeNode* GetRoot();
#ifdef _DEBUG
void Print(TreeNode* pNode);
#endif
protected:
TreeNode *m_pRoot;
};
LeftistTree::LeftistTree()
{
m_pRoot = NULL;
}
LeftistTree::~LeftistTree()
{
Stack st(40); //2^40 must be enough.
//Postorder traverse the tree to release all nodes.
TreeNode *pNode = m_pRoot;
TreeNode *pTemp;
if(pNode==0)
return;
while (1)
{
if(pNode->m_pLeft!=0)
{
st.Push(pNode);
pTemp = pNode;
pNode = pNode->m_pLeft;
pTemp->m_pLeft = 0;
continue;
}
if(pNode->m_pRight!=0)
{
st.Push(pNode);
pTemp = pNode;
pNode = pNode->m_pRight;
pTemp->m_pRight = 0;
continue;
}
delete pNode;
if(0==st.Pop(pNode))
break;
}
}
int LeftistTree::Dequeue(int& iVal)
{
if(m_pRoot==0)
return 0;
iVal = m_pRoot->m_iData;
TreeNode *pTmp = m_pRoot;
m_pRoot = Merge(m_pRoot->m_pLeft, m_pRoot->m_pRight);
delete pTmp;
return 1;
}
int LeftistTree::Enqueue(int iVal)
{
TreeNode *pNew = new TreeNode(iVal);
m_pRoot = Merge(m_pRoot, pNew);
return 1;
}
TreeNode* LeftistTree::Merge(TreeNode *pT1, TreeNode *pT2)
{
if(pT1==0 && pT2==0)
return 0;
else if(pT1==0) //pT2!=0
return pT2;
else if(pT2==0) //pT1!=0
return pT1;
if(pT1->m_iData > pT2->m_iData)
return Merge(pT2, pT1);
Stack st(40);
TreeNode* pInsPos = pT1;
TreeNode* pToIns = pT2;
TreeNode* pTmp;
st.Push(pInsPos);
//Find a node available for insert.
while(1)
{
if(pInsPos->m_pRight!=NULL)
{
if(pToIns->m_iData < pInsPos->m_pRight->m_iData)
{
pTmp = pInsPos->m_pRight;
pInsPos->m_pRight = pToIns;
pToIns = pTmp;
st.Push(pInsPos);
pInsPos = pInsPos->m_pRight;
}
else
{
st.Push(pInsPos);
pInsPos = pInsPos->m_pRight;
}
}
else
{
st.Push(pInsPos);
//Insert
pInsPos->m_pRight = pToIns;
break;
}
}
TreeNode* pNode;
//Try to update the relative distance and make the tree be still the leftist tree.
while (0!=st.Pop(pNode))
{
if(pNode->GetLeftDistance() < pNode->GetRightDistance())
pNode->SwapLeftRight();
pNode->UpdateDistance();
}
return pT1;
}
TreeNode* LeftistTree::GetRoot()
{
return m_pRoot;
}
#ifdef _DEBUG
void LeftistTree::Print(TreeNode* pNode)
{
if(pNode!=NULL)
{
if(pNode->m_pLeft!=NULL && pNode->m_pRight!=NULL)
{
printf("%d[%d]->(%d, %d)\n", pNode->m_iData, pNode->m_iDistance, pNode->m_pLeft->m_iData, pNode->m_pRight->m_iData);
Print(pNode->m_pLeft);
Print(pNode->m_pRight);
}
else if(pNode->m_pLeft!=NULL)
{
printf("%d[%d]->(%d, x)\n", pNode->m_iData, pNode->m_iDistance, pNode->m_pLeft->m_iData);
Print(pNode->m_pLeft);
}
else if(pNode->m_pRight!=NULL)
{
printf("%d[%d]->(x, %d)\n", pNode->m_iData, pNode->m_iDistance, pNode->m_pRight->m_iData);
Print(pNode->m_pRight);
}
}
}
#endif
int main(int argc, char* argv[])
{
LeftistTree tree;
tree.Enqueue(9);
tree.Enqueue(4);
tree.Enqueue(2);
tree.Enqueue(1);
tree.Enqueue(3);
tree.Enqueue(8);
#ifdef _DEBUG
tree.Print(tree.GetRoot());
#endif
int iVal;
tree.Dequeue(iVal);
printf("\nDequeue value is %d\n", iVal);
tree.Dequeue(iVal);
printf("Dequeue value is %d\n", iVal);
#ifdef _DEBUG
tree.Print(tree.GetRoot());
#endif
return 0;
}
也許你還想問：怎么你寫的代碼都不加個頭啊，用來聲明版權什么的。本人似乎沒這個習慣，那些東西繁瑣得很，而且根據我多年開發經驗，給每個cpp文件加個頭其實是沒有必要的，就好像注釋，不需要的時候也生硬加上，那就是畫蛇添足了。
（未完待續）