參考另外一篇筆記《二叉樹的遍歷-遞歸與非遞歸》 http://www.linuxidc.com/Linux/2014-07/104853.htm。
《劍指Offer》面試題6.
思想：遞歸
代碼：
// 《劍指Offer——名企面試官精講典型編程題》代碼
// 著作權所有者：何海濤
struct BinaryTreeNode
{
int m_nValue;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
};
BinaryTreeNode* ConstructCore(int* startPreorder,int* endPreorder,int* startInorder,int* endInorder);
BinaryTreeNode* Construct(int* preorder,int* inorder,int length)
{
if(preorder== NULL|| inorder== NULL|| length<=0)
return NULL;
returnConstructCore(preorder, preorder+ length-1,
inorder,inorder +length-1);
}
BinaryTreeNode* ConstructCore(int* startPreorder,int* endPreorder,int* startInorder,int* endInorder)
{
// 前序遍歷序列的第一個數字是根結點的值
int rootValue= startPreorder[0];
BinaryTreeNode* root=new BinaryTreeNode();
root->m_nValue= rootValue;
root->m_pLeft= root->m_pRight= NULL;
if(startPreorder== endPreorder)
{
if(startInorder== endInorder&&*startPreorder==*startInorder)
return root;
else
throw std::exception("Invalid input.");
}
// 在中序遍歷中找到根結點的值
int* rootInorder= startInorder;
while(rootInorder<= endInorder&&*rootInorder!= rootValue)
++ rootInorder;
if(rootInorder== endInorder&&*rootInorder!= rootValue)
throw std::exception("Invalid input.");
int leftLength= rootInorder-startInorder;
int* leftPreorderEnd= startPreorder+ leftLength;
if(leftLength>0)
{
//構建左子樹
root->m_pLeft=ConstructCore(startPreorder+1, leftPreorderEnd,
startInorder,rootInorder -1);
}
if(leftLength< endPreorder-startPreorder)
{
//構建右子樹
root->m_pRight=ConstructCore(leftPreorderEnd+1, endPreorder,
rootInorder+1, endInorder);
}
return root;
}
// ====================測試代碼====================
void Test(char* testName,int* preorder,int* inorder,int length)
{
if(testName!= NULL)
printf("%s begins:\n",testName);
printf("The preorder sequence is: ");
for(int i=0; i< length; ++ i)
printf("%d ",preorder[i]);
printf("\n");
printf("The inorder sequence is: ");
for(int i=0; i< length; ++ i)
printf("%d ",inorder[i]);
printf("\n");
try
{
BinaryTreeNode* root= Construct(preorder,inorder, length);
PrintTree(root);
DestroyTree(root);
}
catch(std::exception& exception)
{
printf("Invalid Input.\n");
}
}
二叉樹的常見問題及其解決程序 http://www.linuxidc.com/Linux/2013-04/83661.htm
【遞歸】二叉樹的先序建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75608.htm
在JAVA中實現的二叉樹結構 http://www.linuxidc.com/Linux/2008-12/17690.htm
【非遞歸】二叉樹的建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75607.htm
二叉樹遞歸實現與二重指針 http://www.linuxidc.com/Linux/2013-07/87373.htm
二叉樹先序中序非遞歸算法 http://www.linuxidc.com/Linux/2014-06/102935.htm
思想：通過根節點將序列劃分為左子樹序列和右子樹序列，他們必須滿足的條件是：左子樹序列中的所有值小於根節點，右子樹中所有值大於根節點，然後遞歸判斷左子樹序列和右子樹序列。
代碼：
// BST：BinarySearch Tree，二叉搜索樹
bool VerifySquenceOfBST(int sequence[], int length )
{
if (sequence == NULL || length <=0)
returnfalse ;
int root = sequence[ length -1];
//在二叉搜索樹中左子樹的結點小於根結點
int i =0;
for(; i < length -1;++ i )
{
if ( sequence [ i ]> root )
break ;
}
//在二叉搜索樹中右子樹的結點大於根結點
int j = i ;
for(; j < length -1;++ j )
{
if ( sequence [ j ]< root )
returnfalse ;
}
//判斷左子樹是不是二叉搜索樹
bool left =true ;
if ( i >0)
left = VerifySquenceOfBST( sequence , i );
//判斷右子樹是不是二叉搜索樹
bool right =true ;
if ( i < length -1)
right = VerifySquenceOfBST( sequence + i , length - i -1);
return (left && right ); }
更多詳情見請繼續閱讀下一頁的精彩內容： http://www.linuxidc.com/Linux/2014-07/104854p2.htm
