Posted on 2014-01-03 00:41
whspecial 閱讀(3637)
評論(0) 編輯 收藏 引用 所屬分類:
算法&&數據結構
將排序二叉樹轉化成雙向鏈表，應該是一道很常見的面試題目，網上的實現比較多，有用遞歸也有用中序遍歷法的。看到一位外國友人的實現，還是比較清晰的，思路如下：
1，如果左子樹不為null，處理左子樹
1.a）遞歸轉化左子樹為雙向鏈表；
1.b）找出根結點的前驅節點（是左子樹的最右的節點）
1.c）將上一步找出的節點和根結點連接起來
2，如果右子樹不為null，處理右子樹（和上面的很類似）
1.a）遞歸轉化右子樹為雙向鏈表；
1.b）找出根結點的后繼節點（是右子樹的最左的節點）
1.c）將上一步找出的節點和根結點連接起來
3，找到最左邊的節點并返回
附上國外友人的鏈接：http://www.geeksforgeeks.org/in-place-convert-a-given-binary-tree-to-doubly-linked-list/
下面是代碼實現：
bintree2listUtil函數返回的node＊ 是root節點，bintree2list函數返回的是頭節點
node* bintree2listUtil(node* root)
{
if (root == NULL)
return root;
if (root->left != NULL)
{
node* left = bintree2listUtil(root->left);
for (; left->right!=NULL; left=left->right);
left->right = root;
root->left = left;
}
if (root->right!=NULL)
{
node* right = bintree2listUtil(root->right);
for (; right->left!=NULL; right = right->left);
right->left = root;
root->right = right;
}
return root;
}
node* bintree2list(node *root)
{
if (root == NULL)
return root;
root = bintree2listUtil(root);
while (root->left != NULL)
root = root->left;
return (root);