關(guān)于二叉樹(shù)的操作，全在這了

1 前序遍歷，中序遍歷，后序遍歷；

1.1 前序遍歷

對(duì)于當(dāng)前結(jié)點(diǎn)，先輸出該結(jié)點(diǎn)，然后輸出它的左孩子，最后輸出它的右孩子。以上圖為例，遞歸的過(guò)程如下：

輸出 1，接著左孩子；

輸出 2，接著左孩子；

輸出 4，左孩子為空，再接著右孩子；

輸出 6，左孩子為空，再接著右孩子；

輸出 7，左右孩子都為空，此時(shí) 2 的左子樹(shù)全部輸出，2 的右子樹(shù)為空，此時(shí) 1 的左子樹(shù)全部輸出，接著 1 的右子樹(shù)；

輸出 3，接著左孩子；

輸出 5，左右孩子為空，此時(shí) 3 的左子樹(shù)全部輸出，3 的右子樹(shù)為空，至此 1 的右子樹(shù)全部輸出，結(jié)束。

而非遞歸版本只是利用 stack 模擬上述過(guò)程而已，遞歸的過(guò)程也就是出入棧的過(guò)程。

/*前序遍歷遞歸版*/
voidPreOrderRec(Node*node)
{
if(node==nullptr)
return;
cout<data<left);//然后輸出左孩子
PreOrderRec(node->right);//最后輸出右孩子
}

/*前序遍歷非遞歸版*/
voidPreOrderNonRec(Node*node)
{
if(node==nullptr)
return;

stackS;
cout<data<left;

while(!S.empty()||node)
{
while(node)
{
cout<data<left;//然后輸出左孩子
}//while結(jié)束意味著左孩子已經(jīng)全部輸出

node=S.top()->right;//最后輸出右孩子
S.pop();
}
}

1.2 中序遍歷

對(duì)于當(dāng)前結(jié)點(diǎn)，先輸出它的左孩子，然后輸出該結(jié)點(diǎn)，最后輸出它的右孩子。以（1.1）圖為例：

1-->2-->4，4 的左孩子為空，輸出 4，接著右孩子；

6 的左孩子為空，輸出 6，接著右孩子；

7 的左孩子為空，輸出 7，右孩子也為空，此時(shí) 2 的左子樹(shù)全部輸出，輸出 2，2 的右孩子為空，此時(shí) 1 的左子樹(shù)全部輸出，輸出 1，接著 1 的右孩子；

3-->5，5 左孩子為空，輸出 5，右孩子也為空，此時(shí) 3 的左子樹(shù)全部輸出，而 3 的右孩子為空，至此 1 的右子樹(shù)全部輸出，結(jié)束。

/*中序遍歷遞歸版*/
voidInOrderRec(Node*node)
{
if(node==nullptr)
return;

InOrderRec(node->left);//先輸出左孩子
cout<data<right);//最后輸出右孩子
}

/*前序遍歷非遞歸版*/
voidInOrderNonRec(Node*node)
{
if(node==nullptr)
return;

stackS;
S.push(node);
node=node->left;

while(!S.empty()||node)
{
while(node)
{
S.push(node);
node=node->left;
}//while結(jié)束意味著左孩子為空

cout<data<right;//左孩子全部輸出，當(dāng)前結(jié)點(diǎn)也輸出后，最后輸出右孩子
S.pop();
}
}

1.3 后序遍歷

對(duì)于當(dāng)前結(jié)點(diǎn)，先輸出它的左孩子，然后輸出它的右孩子，最后輸出該結(jié)點(diǎn)。依舊以（1.1）圖為例：

1->2->4->6->7，7 無(wú)左孩子，也無(wú)右孩子，輸出 7，此時(shí) 6 無(wú)左孩子，而 6 的右子樹(shù)也全部輸出，輸出 6，此時(shí) 4 無(wú)左子樹(shù)，而 4 的右子樹(shù)已全部輸出，接著輸出 4，此時(shí) 2 的左子樹(shù)全部輸出，且 2 無(wú)右子樹(shù)，輸出 2，此時(shí) 1 的左子樹(shù)全部輸出，接著轉(zhuǎn)向右子樹(shù)；

3->5，5 無(wú)左孩子，也無(wú)右孩子，輸出 5，此時(shí) 3 的左子樹(shù)全部輸出，且 3 無(wú)右孩子，輸出 3，此時(shí) 1 的右子樹(shù)全部輸出，輸出 1，結(jié)束。

非遞歸版本中，對(duì)于一個(gè)結(jié)點(diǎn)，如果我們要輸出它，只有它既沒(méi)有左孩子也沒(méi)有右孩子或者它有孩子但是它的孩子已經(jīng)被輸出（由此設(shè)置 pre 變量）。若非上述兩種情況，則將該結(jié)點(diǎn)的右孩子和左孩子依次入棧，這樣就保證了每次取棧頂元素的時(shí)候,先依次遍歷左子樹(shù)和右子樹(shù)。

/*后序遍歷遞歸版*/
voidPostOrderRec(Node*node)
{
if(node==nullptr)
return;

PostOrderRec(node->left);//先輸出左孩子
PostOrderRec(node->right);//然后輸出右孩子
cout<data<S;
S.push(node);

while(!S.empty())
{
node=S.top();

if((!node->left&&!node->right)||//第一個(gè)輸出的必是無(wú)左右孩子的葉子結(jié)點(diǎn)，只要第一個(gè)結(jié)點(diǎn)輸出，
(pre &&(pre == node->left || pre == node->right)))//以后的 pre 就不會(huì)是空。此處的判斷語(yǔ)句加入一個(gè) pre，只是用來(lái)
{//確保可以正確輸出第一個(gè)結(jié)點(diǎn)。
cout<data<right)
S.push(node->right);//先進(jìn)右孩子，再進(jìn)左孩子，取出來(lái)的才是左孩子
if(node->left)
S.push(node->left);
}
}
}

2 層次遍歷

voidLevelOrder(Node*node)
{
Node*p=node;
queueQ;//隊(duì)列
Q.push(p);

while(!Q.empty())
{
p=Q.front();
cout<data<left)
Q.push(p->left);//注意順序，先進(jìn)左孩子
if(p->right)
Q.push(p->right);
}
}

3 求樹(shù)的結(jié)點(diǎn)數(shù)

intCountNodes(Node*node)
{
if(node==nullptr)
return0;

returnCountNodes(node->left)+CountNodes(node->right)+1;
}

4 求樹(shù)的葉子數(shù)

intCountLeaves(Node*node)
{
if(node==nullptr)
return0;

if(!node->left&&!node->right)
return1;

returnCountLeaves(node->left)+CountLeaves(node->right);
}

5 求樹(shù)的深度

intGetDepth(Node*node)
{
if(node==nullptr)
return0;

intleft_depth=GetDepth(node->left)+1;
intright_depth=GetDepth(node->right)+1;

returnleft_depth>right_depth?left_depth:right_depth;
}

6 求二叉樹(shù)第k層的結(jié)點(diǎn)個(gè)數(shù)

intGetKLevel(Node*node,intk)
{
if(node==nullptr)
return0;

if(k==1)
return1;

returnGetKLevel(node->left,k-1)+GetKLevel(node->right,k-1);
}

7 判斷兩棵二叉樹(shù)是否結(jié)構(gòu)相同

不考慮數(shù)據(jù)內(nèi)容。結(jié)構(gòu)相同意味著對(duì)應(yīng)的左子樹(shù)和對(duì)應(yīng)的右子樹(shù)都結(jié)構(gòu)相同。

boolStructureCmp(Node*node1,Node*node2)
{
if(node1==nullptr&&node2==nullptr)
returntrue;
elseif(node1==nullptr||node2==nullptr)
returnfalse;

returnStructureCmp(node1->left,node2->left)&&Str1uctureCmp(node1->right,node2->right);
}

8 求二叉樹(shù)的鏡像

對(duì)于每個(gè)結(jié)點(diǎn)，我們交換它的左右孩子即可。

voidMirror(Node*node)
{
if(node==nullptr)
return;

Node*temp=node->left;
node->left=node->right;
node->right=temp;

Mirror(node->left);
Mirror(node->right);
}

9 求兩個(gè)結(jié)點(diǎn)的最低公共祖先結(jié)點(diǎn)

最低公共祖先，即 LCA（Lowest Common Ancestor），見(jiàn)下圖：



結(jié)點(diǎn) 3 和結(jié)點(diǎn) 4 的最近公共祖先是結(jié)點(diǎn) 2，即 LCA(3,4)=2。在此，需要注意到當(dāng)兩個(gè)結(jié)點(diǎn)在同一棵子樹(shù)上的情況，如結(jié)點(diǎn) 3 和結(jié)點(diǎn) 2 的最近公共祖先為 2，即 LCA(3,2)=2。同理 LCA(5,6)=4，LCA(6,10)=1。

Node*FindLCA(Node*node,Node*target1,Node*target2)
{
if(node==nullptr)
returnnullptr;
if(node==target1||node==target2)
returnnode;

Node*left=FindLCA(node->left,target1,target2);
Node*right=FindLCA(node->right,target1,target2);
if(left&&right)//分別在左右子樹(shù)
returnnode;

returnleft?left:right;//都在左子樹(shù)或右子樹(shù)
}

10 求任意兩結(jié)點(diǎn)距離

首先找到兩個(gè)結(jié)點(diǎn)的 LCA，然后分別計(jì)算 LCA 與它們的距離，最后相加即可。

intFindLevel(Node*node,Node*target)
{
if(node==nullptr)
return-1;
if(node==target)
return0;

intlevel=FindLevel(node->left,target);//先在左子樹(shù)找
if(level==-1)
level=FindLevel(node->right,target);//如果左子樹(shù)沒(méi)找到，在右子樹(shù)找

if(level!=-1)//找到了，回溯
returnlevel+1;

return-1;//如果左右子樹(shù)都沒(méi)找到
}

intDistanceNodes(Node*node,Node*target1,Node*target2)
{
Node*lca=FindLCA(node,target1,target2);//找到最低公共祖先結(jié)點(diǎn)
intlevel1=FindLevel(lca,target1);
intlevel2=FindLevel(lca,target2);

returnlevel1+level2;
}

11 找出二叉樹(shù)中某個(gè)結(jié)點(diǎn)的所有祖先結(jié)點(diǎn)

如果給定結(jié)點(diǎn) 5，則其所有祖先結(jié)點(diǎn)為 4,2,1。

boolFindAllAncestors(Node*node,Node*target)
{
if(node==nullptr)
returnfalse;
if(node==target)
returntrue;

if(FindAllAncestors(node->left,target)||FindAllAncestors(node->right,target))//找到了
{
cout<data<

	

	12 不使用遞歸和棧遍歷二叉樹(shù)

	1968 年，高德納（Donald Knuth）提出一個(gè)問(wèn)題：是否存在一個(gè)算法，它不使用棧也不破壞二叉樹(shù)結(jié)構(gòu)，但是可以完成對(duì)二叉樹(shù)的遍歷？隨后 1979 年，James H. Morris 提出了二叉樹(shù)線索化，解決了這個(gè)問(wèn)題。（根據(jù)這個(gè)概念我們又提出了一個(gè)新的數(shù)據(jù)結(jié)構(gòu)，即線索二叉樹(shù)，因線索二叉樹(shù)不是本文要介紹的內(nèi)容，所以有興趣的朋友請(qǐng)移步線索二叉樹(shù)）

	前序，中序，后序遍歷，不管是遞歸版本還是非遞歸版本，都用到了一個(gè)數(shù)據(jù)結(jié)構(gòu)--棧，為何要用棧？那是因?yàn)槠渌姆绞經(jīng)]法記錄當(dāng)前結(jié)點(diǎn)的 parent,而如果在每個(gè)結(jié)點(diǎn)的結(jié)構(gòu)里面加個(gè) parent 分量顯然是不現(xiàn)實(shí)的，而線索化正好解決了這個(gè)問(wèn)題，其含義就是利用結(jié)點(diǎn)的右孩子空指針，指向該結(jié)點(diǎn)在中序序列中的后繼。下面具體來(lái)看看如何使用線索化來(lái)完成對(duì)二叉樹(shù)的遍歷。




	先看前序遍歷，步驟如下：

	如果當(dāng)前結(jié)點(diǎn)的左孩子為空，則輸出當(dāng)前結(jié)點(diǎn)并將其右孩子作為當(dāng)前結(jié)點(diǎn)；

	如果當(dāng)前結(jié)點(diǎn)的左孩子不為空，在當(dāng)前結(jié)點(diǎn)的左子樹(shù)中找到當(dāng)前結(jié)點(diǎn)在中序遍歷下的前驅(qū)結(jié)點(diǎn)；

	2.1如果前驅(qū)結(jié)點(diǎn)的右孩子為空，將它的右孩子設(shè)置為當(dāng)前結(jié)點(diǎn)，輸出當(dāng)前結(jié)點(diǎn)并把當(dāng)前結(jié)點(diǎn)更新為當(dāng)前結(jié)點(diǎn)的左孩子；

	2.2如果前驅(qū)結(jié)點(diǎn)的右孩子為當(dāng)前結(jié)點(diǎn)，將它的右孩子重新設(shè)為空，當(dāng)前結(jié)點(diǎn)更新為當(dāng)前結(jié)點(diǎn)的右孩子；

	重復(fù)以上步驟 1 和 2，直到當(dāng)前結(jié)點(diǎn)為空。

	
/*前序遍歷*/
voidPreOrderMorris(Node*root)
{
Node*cur=root;
Node*pre=nullptr;

while(cur)
{
if(cur->left==nullptr)//步驟1
{
cout<data<right;
}
else
{
pre=cur->left;
while(pre->right&&pre->right!=cur)//步驟2，找到cur的前驅(qū)結(jié)點(diǎn)
pre=pre->right;

if(pre->right==nullptr)//步驟2.1，cur未被訪問(wèn)，將cur結(jié)點(diǎn)作為其前驅(qū)結(jié)點(diǎn)的右孩子
{
cout<data<right=cur;
cur=cur->left;
}
else//步驟2.2，cur已被訪問(wèn)，恢復(fù)樹(shù)的原有結(jié)構(gòu)，更改right指針
{
pre->right=nullptr;
cur=cur->right;
}
}
}
}

再來(lái)看中序遍歷，和前序遍歷相比只改動(dòng)一句代碼，步驟如下：

	

	如果當(dāng)前結(jié)點(diǎn)的左孩子為空，則輸出當(dāng)前結(jié)點(diǎn)并將其右孩子作為當(dāng)前結(jié)點(diǎn)；

	如果當(dāng)前結(jié)點(diǎn)的左孩子不為空，在當(dāng)前結(jié)點(diǎn)的左子樹(shù)中找到當(dāng)前結(jié)點(diǎn)在中序遍歷下的前驅(qū)結(jié)點(diǎn)；

	2.1. 如果前驅(qū)結(jié)點(diǎn)的右孩子為空，將它的右孩子設(shè)置為當(dāng)前結(jié)點(diǎn)，當(dāng)前結(jié)點(diǎn)更新為當(dāng)前結(jié)點(diǎn)的左孩子；

	2.2. 如果前驅(qū)結(jié)點(diǎn)的右孩子為當(dāng)前結(jié)點(diǎn)，將它的右孩子重新設(shè)為空，輸出當(dāng)前結(jié)點(diǎn)，當(dāng)前結(jié)點(diǎn)更新為當(dāng)前結(jié)點(diǎn)的右孩子；

	重復(fù)以上步驟 1 和 2，直到當(dāng)前結(jié)點(diǎn)為空。

	
/*中序遍歷*/
voidInOrderMorris(Node*root)
{
Node*cur=root;
Node*pre=nullptr;

while(cur)
{
if(cur->left==nullptr)//（1）
{
cout<data<right;
}
else
{
pre=cur->left;
while(pre->right&&pre->right!=cur)//（2），找到cur的前驅(qū)結(jié)點(diǎn)
pre=pre->right;

if(pre->right==nullptr)//（2.1），cur未被訪問(wèn)，將cur結(jié)點(diǎn)作為其前驅(qū)結(jié)點(diǎn)的右孩子
{
pre->right=cur;
cur=cur->left;
}
else//（2.2），cur已被訪問(wèn)，恢復(fù)樹(shù)的原有結(jié)構(gòu)，更改right指針
{
cout<data<right=nullptr;
cur=cur->right;
}
}
}
}


	

	最后看下后序遍歷，后序遍歷有點(diǎn)復(fù)雜，需要建立一個(gè)虛假根結(jié)點(diǎn) dummy，令其左孩子是 root。并且還需要一個(gè)子過(guò)程，就是倒序輸出某兩個(gè)結(jié)點(diǎn)之間路徑上的各個(gè)結(jié)點(diǎn)。

	


	步驟如下：

	如果當(dāng)前結(jié)點(diǎn)的左孩子為空，則將其右孩子作為當(dāng)前結(jié)點(diǎn)；

	如果當(dāng)前結(jié)點(diǎn)的左孩子不為空，在當(dāng)前結(jié)點(diǎn)的左子樹(shù)中找到當(dāng)前結(jié)點(diǎn)在中序遍歷下的前驅(qū)結(jié)點(diǎn)；

	2.1. 如果前驅(qū)結(jié)點(diǎn)的右孩子為空，將它的右孩子設(shè)置為當(dāng)前結(jié)點(diǎn)，當(dāng)前結(jié)點(diǎn)更新為當(dāng)前結(jié)點(diǎn)的左孩子；

	2.2. 如果前驅(qū)結(jié)點(diǎn)的右孩子為當(dāng)前結(jié)點(diǎn)，將它的右孩子重新設(shè)為空，倒序輸出從當(dāng)前結(jié)點(diǎn)的左孩子到該前驅(qū)結(jié)點(diǎn)這條路徑上的所有結(jié)點(diǎn)，當(dāng)前結(jié)點(diǎn)更新為當(dāng)前結(jié)點(diǎn)的右孩子；

	重復(fù)以上步驟 1 和 2，直到當(dāng)前結(jié)點(diǎn)為空。

	
structNode
{
intdata;
Node*left;
Node*right;
Node(intdata_,Node*left_,Node*right_)
{
data=data_;
left=left_;
right=right_;
}
};

voidReversePrint(Node*from,Node*to)
{
if(from==to)
{
cout<data<right,to);
cout<data<left==nullptr)//步驟1
cur=cur->right;
else
{
pre=cur->left;
while(pre->right&&pre->right!=cur)//步驟2，找到cur的前驅(qū)結(jié)點(diǎn)
pre=pre->right;

if(pre->right==nullptr)//步驟2.1，cur未被訪問(wèn)，將cur結(jié)點(diǎn)作為其前驅(qū)結(jié)點(diǎn)的右孩子
{
pre->right=cur;
cur=cur->left;
}
else//步驟2.2，cur已被訪問(wèn)，恢復(fù)樹(shù)的原有結(jié)構(gòu)，更改right指針
{
pre->right=nullptr;
ReversePrint(cur->left,pre);
cur=cur->right;
}
}
}
}


	

	dummy 用的非常巧妙，建議讀者配合上面的圖模擬下算法流程。

	13 二叉樹(shù)前序中序推后序

				方式
			

				序列
		

				前序
			

				[1 2 4 7 3 5 8 9 6]
		

				中序
			

				[4 7 2 1 8 5 9 3 6]
		

				后序
			

				[7 4 2 8 9 5 6 3 1]
		

	以上面圖表為例，步驟如下：

	根據(jù)前序可知根結(jié)點(diǎn)為1；

	根據(jù)中序可知 4 7 2 為根結(jié)點(diǎn) 1 的左子樹(shù)和 8 5 9 3 6 為根結(jié)點(diǎn) 1 的右子樹(shù)；

	遞歸實(shí)現(xiàn)，把 4 7 2 當(dāng)做新的一棵樹(shù)和 8 5 9 3 6 也當(dāng)做新的一棵樹(shù)；

	在遞歸的過(guò)程中輸出后序。

	
/*前序遍歷和中序遍歷結(jié)果以長(zhǎng)度為n的數(shù)組存儲(chǔ)，pos1為前序數(shù)組下標(biāo)，pos2為后序下標(biāo)*/

intpre_order_arry[n];
intin_order_arry[n];

voidPrintPostOrder(intpos1,intpos2,intn)
{
if(n==1)
{
cout<

	

	當(dāng)然我們也可以根據(jù)前序和中序構(gòu)造出二叉樹(shù)，進(jìn)而求出后序。

	
/*該函數(shù)返回二叉樹(shù)的根結(jié)點(diǎn)*/
Node*Create(intpos1,intpos2,intn)
{
Node*p=nullptr;

for(inti=0;ileft=Create(pos1+1,pos2,i);
p->right=Create(pos1+i+1,pos2+i+1,n-i-1);
returnp;
}
}

returnp;
}


	

	14 判斷二叉樹(shù)是不是完全二叉樹(shù)

	若設(shè)二叉樹(shù)的深度為 h，除第 h 層外，其它各層 (1～h-1) 的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，第 h 層所有的結(jié)點(diǎn)都連續(xù)集中在最左邊，這就是完全二叉樹(shù)（Complete Binary Tree）。如下圖：



	首先若一個(gè)結(jié)點(diǎn)只有右孩子，肯定不是完全二叉樹(shù)；其次若只有左孩子或沒(méi)有孩子，那么接下來(lái)的所有結(jié)點(diǎn)肯定都沒(méi)有孩子，否則就不是完全二叉樹(shù)，因此設(shè)置 flag 標(biāo)記變量。

	
boolIsCBT(Node*node)
{
boolflag=false;
queueQ;
Q.push(node);

while(!Q.empty())
{
Node*p=Q.front();
Q.pop();

if(flag)
{
if(p->left||p->right)
returnfalse;
}
else
{
if(p->left&&p->right)
{
Q.push(p->left);
Q.push(p->right);
}
elseif(p->right)//只有右結(jié)點(diǎn)
returnfalse;
elseif(p->left)//只有左結(jié)點(diǎn)
{
Q.push(p->left);
flag=true;
}
else//沒(méi)有結(jié)點(diǎn)
flag=true;
}
}

returntrue;
}


	

	15 判斷是否是二叉查找樹(shù)的后序遍歷結(jié)果

	在后續(xù)遍歷得到的序列中，最后一個(gè)元素為樹(shù)的根結(jié)點(diǎn)。從頭開(kāi)始掃描這個(gè)序列，比根結(jié)點(diǎn)小的元素都應(yīng)該位于序列的左半部分；從第一個(gè)大于跟結(jié)點(diǎn)開(kāi)始到跟結(jié)點(diǎn)前面的一個(gè)元素為止，所有元素都應(yīng)該大于跟結(jié)點(diǎn)，因?yàn)檫@部分元素對(duì)應(yīng)的是樹(shù)的右子樹(shù)。

	根據(jù)這樣的劃分，把序列劃分為左右兩部分，我們遞歸地確認(rèn)序列的左、右兩部分是不是都是二元查找樹(shù)。

	
intarray[n];//長(zhǎng)度為n的序列，注意begin和end遵循的是左閉右閉原則

boolIsSequenceOfBST(intbegin,intend)
{
if(end-begin<=?0)
????????return?true;

????int?root_data?=?array[end];??//?數(shù)組尾元素為根結(jié)點(diǎn)

????int?i?=?begin;
????for?(;?array[i]?

	

	16 給定一個(gè)二叉查找樹(shù)中的結(jié)點(diǎn)（存在一個(gè)指向父親結(jié)點(diǎn)的指針），找出在中序遍歷下它的后繼和前驅(qū)

	一棵二叉查找樹(shù)的中序遍歷序列，正好是升序序列。假如根結(jié)點(diǎn)的父結(jié)點(diǎn)為 nullptr，則：

	如果當(dāng)前結(jié)點(diǎn)有右孩子，則后繼結(jié)點(diǎn)為這個(gè)右孩子的最左孩子；

	如果當(dāng)前結(jié)點(diǎn)沒(méi)有右孩子；

	2.1. 當(dāng)前結(jié)點(diǎn)為根結(jié)點(diǎn)，返回 nullptr；

	2.2. 當(dāng)前結(jié)點(diǎn)只是個(gè)普通結(jié)點(diǎn)，也就是存在父結(jié)點(diǎn)；

	2.2.1. 當(dāng)前結(jié)點(diǎn)是父親結(jié)點(diǎn)的左孩子，則父親結(jié)點(diǎn)就是后繼結(jié)點(diǎn)；

	2.2.2. 當(dāng)前結(jié)點(diǎn)是父親結(jié)點(diǎn)的右孩子，沿著父親結(jié)點(diǎn)往上走，直到 n-1 代祖先是 n 代祖先的左孩子，則后繼為 n 代祖先或遍歷到根結(jié)點(diǎn)也沒(méi)找到符合的，則當(dāng)前結(jié)點(diǎn)就是中序遍歷的最后一個(gè)結(jié)點(diǎn)，返回 nullptr。

	
/*求后繼結(jié)點(diǎn)*/
Node*Increment(Node*node)
{
if(node->right)//步驟1
{
node=node->right;
while(node->left)
node=node->left;
returnnode;
}
else//步驟2
{
if(node->parent==nullptr)//步驟2.1
returnnullptr;
Node*p=node->parent;//步驟2.2
if(p->left==node)//步驟2.2.1
returnp;
else//步驟2.2.2
{
while(p->right==node)
{
node=p;
p=p->parent;
if(p==nullptr)
returnnullptr;
}
returnp;
}
}
}


	

	仔細(xì)觀察上述代碼，總覺(jué)得有點(diǎn)啰嗦。比如，過(guò)多的 return，步驟 2 的層次太多。綜合考慮所有情況，改進(jìn)代碼如下：

	
Node*Increment(Node*node)
{
if(node->right)
{
node=node->right;
while(node->left)
node=node->left;
}
else
{
Node*p=node->parent;
while(p&&p->right==node)
{
node=p;
p=p->parent;
}
node=p;
}

returnnode;
}


	

	上述的代碼是基于結(jié)點(diǎn)有 parent 指針的，若題意要求沒(méi)有 parent 呢？網(wǎng)上也有人給出了答案，個(gè)人覺(jué)得沒(méi)有什么價(jià)值，有興趣的朋友可以到這里查看。

	而求前驅(qū)結(jié)點(diǎn)的話，只需把上述代碼的 left 與 right 互調(diào)即可，很簡(jiǎn)單。

	17 二分查找樹(shù)轉(zhuǎn)化為排序的循環(huán)雙鏈表

	二分查找樹(shù)的中序遍歷即為升序排列，問(wèn)題就在于如何在遍歷的時(shí)候更改指針的指向。一種簡(jiǎn)單的方法時(shí)，遍歷二分查找樹(shù)，將遍歷的結(jié)果放在一個(gè)數(shù)組中，之后再把該數(shù)組轉(zhuǎn)化為雙鏈表。如果題目要求只能使用 O(1)O(1) 內(nèi)存，則只能在遍歷的同時(shí)構(gòu)建雙鏈表，即進(jìn)行指針的替換。

	我們需要用遞歸的方法來(lái)解決，假定每個(gè)遞歸調(diào)用都會(huì)返回構(gòu)建好的雙鏈表，可把問(wèn)題分解為左右兩個(gè)子樹(shù)。由于左右子樹(shù)都已經(jīng)是有序的，當(dāng)前結(jié)點(diǎn)作為中間的一個(gè)結(jié)點(diǎn)，把左右子樹(shù)得到的鏈表連接起來(lái)即可。

	
/*合并兩個(gè)a,b兩個(gè)循環(huán)雙向鏈表*/
Node*Append(Node*a,Node*b)
{
if(a==nullptr)returnb;
if(b==nullptr)returna;

//分別得到兩個(gè)鏈表的最后一個(gè)元素
Node*a_last=a->left;
Node*b_last=b->left;

//將兩個(gè)鏈表頭尾相連
a_last->right=b;
b->left=a_last;

a->left=b_last;
b_last->right=a;

returna;
}

/*遞歸的解決二叉樹(shù)轉(zhuǎn)換為雙鏈表*/
Node*TreeToList(Node*node)
{
if(node==nullptr)returnnullptr;

//遞歸解決子樹(shù)
Node*left_list=TreeToList(node->left);
Node*right_list=TreeToList(node->right);

//把根結(jié)點(diǎn)轉(zhuǎn)換為一個(gè)結(jié)點(diǎn)的雙鏈表，方便后面的鏈表合并
node->left=node;
node->right=node;

//合并之后即為升序排列
left_list=Append(left_list,node);
left_list=Append(left_list,right_list);

returnleft_list;
}


	

	18 有序鏈表轉(zhuǎn)化為平衡的二分查找樹(shù)（Binary Search Tree）

	我們可以采用自頂向下的方法。先找到中間結(jié)點(diǎn)作為根結(jié)點(diǎn)，然后遞歸左右兩部分。所以我們需要先找到中間結(jié)點(diǎn)，對(duì)于單鏈表來(lái)說(shuō)，必須要遍歷一邊，可以使用快慢指針加快查找速度。

	
structTreeNode
{
intdata;
TreeNode*left;
TreeNode*right;
TreeNode(intdata_){data=data_;left=right=nullptr;}
};

structListNode
{
intdata;
ListNode*next;
ListNode(intdata_){data=data_;next=nullptr;}
};

TreeNode*SortedListToBST(ListNode*list_node)
{
if(!list_node)returnnullptr;
if(!list_node->next)return(newTreeNode(list_node->data));

//用快慢指針找到中間結(jié)點(diǎn)
ListNode*pre_slow=nullptr;//記錄慢指針的前一個(gè)結(jié)點(diǎn)
ListNode*slow=list_node;//慢指針
ListNode*fast=list_node;//快指針
while(fast&&fast->next)
{
pre_slow=slow;
slow=slow->next;
fast=fast->next->next;
}
TreeNode*mid=newTreeNode(slow->data);

//分別遞歸左右兩部分
if(pre_slow)
{
pre_slow->next=nullptr;
mid->left=SortedListToBST(list_node);
}
mid->right=SortedListToBST(slow->next);

returnmid;
}


	

	由 f(n)=2f(frac n2)+frac n2f(n)=2f(2n)+2n 得，所以上述算法的時(shí)間復(fù)雜度為 O(nlogn)O(nlogn)。

	不妨換個(gè)思路，采用自底向上的方法：

	
TreeNode*SortedListToBSTRec(ListNode*&list,intstart,intend)
{
if(start>end)returnnullptr;

intmid=start+(end-start)/2;
TreeNode*left_child=SortedListToBSTRec(list,start,mid-1);//注意此處傳入的是引用
TreeNode*parent=newTreeNode(list->data);
parent->left=left_child;
list=list->next;
parent->right=SortedListToBSTRec(list,mid+1,end);
returnparent;
}

TreeNode*SortedListToBST(ListNode*node)
{
intn=0;
ListNode*p=node;
while(p)
{
n++;
p=p->next;
}

returnSortedListToBSTRec(node,0,n-1);
}


	

	如此，時(shí)間復(fù)雜度降為 O(n)O(n)。

	19 判斷是否是二叉查找樹(shù)

	我們假定二叉樹(shù)沒(méi)有重復(fù)元素，即對(duì)于每個(gè)結(jié)點(diǎn)，其左右孩子都是嚴(yán)格的小于和大于。

	下面給出兩個(gè)方法：

	方法 1：

	
boolIsBST(Node*node,intmin,intmax)
{
if(node==nullptr)
returntrue;
if(node->data<=?min?||?node->data>=max)
returnfalse;

returnIsBST(node->left,min,node->data)&&IsBST(node->right,node->data,max);
}

IsBST(node,INT_MIN,INT_MAX);


	

	方法 2：

	利用二叉查找樹(shù)中序遍歷時(shí)元素遞增來(lái)判斷。

	
boolIsBST(Node*node)
{
staticintpre=INT_MIN;

if(node==nullptr)
returntrue;

if(!IsBST(node->left))
returnfalse;

if(node->datadata;

returnIsBST(node->right);
}

	

	





	審核編輯：劉清