二叉樹類型筆試面試題大總結（含代碼）

一、二叉樹的遍歷-前序、中序、後序以及層次遍歷（遞歸與非遞歸）

參考另外一篇筆記《二叉樹的遍歷-遞歸與非遞歸》 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