我写故我在

I write, therefore I am

Posts Tagged ‘BST’

程序员面试题集001

Posted by ieipi 于 九月 10, 2011

题目

将一颗二叉搜索树变成排序的双向链表,要求只改动指针,不创建新的节点。

思路一

    对于二元查找树(Binary Search Tree),其中序遍历的结果即为排序的结果,只需将此结果用双链表表示即可。根据中序遍历的思想,
对于当前节点而言,其左子树已经成功转换,接下来先将当前节点插入链表尾部,再处理其右子树。

伪代码  

1.若当前节点为空,则处理结束,返回.
2.否则:
    2.1递归处理左子树;
    2.2将当前节点加入链表尾部;
    2.3递归处理右子树;

代码

/*
 * =====================================================================================
 *
 *       Filename:  bst2list.cpp
 *
 *    Description:  convert a BST into a sorted double linked list in place.
 *
 *        Version:  1.0
 *        Created:  2011年08月24日 19时54分33秒
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  XuDingxin (xdxn), xdxn2010@gmail.com
 *        Company:  GUCAS
 *
 * =====================================================================================
 */

#include	<stdlib.h>

#include	<stdio.h>
#include	<iostream>
using namespace std;

struct BSTreeNode
{
    int m_nValue;
    BSTreeNode *m_pLeft;
    BSTreeNode *m_pRight;
};
typedef BSTreeNode DoubleList;
DoubleList *pHead;
DoubleList *pListIndex;

void convertToDoubleList(BSTreeNode *pCurrent);
void addBSTreeNode(BSTreeNode *&pCurrent, int value);

/**
 * @brief add a new node to the current BST.
 *
 * @param pCurrent the root of the current BST.
 * @param value the data element of the new node.
 */
    void
addBSTreeNode (BSTreeNode *&pCurrent, int value  )
{

    if ( NULL == pCurrent ) {
        BSTreeNode *pBSTree = new BSTreeNode();
        pBSTree->m_pLeft = NULL;
        pBSTree->m_pRight = NULL;
        pBSTree->m_nValue = value;
        pCurrent = pBSTree;
    }
    else {
        if ( pCurrent->m_nValue > value ) {
            addBSTreeNode(pCurrent->m_pLeft, value);
        }
        else if(pCurrent->m_nValue < value){
            addBSTreeNode(pCurrent->m_pRight, value);
        }
        else {
            cout << "ignore duplicate node"  << endl;
        }
    }
    return ;
}		/* -----  end of function addBSTreeNode  ----- */

/**
 * @brief traverse the BST in inorder and form the double list accordingly.
 *
 * @param pCurrent the root of the current BST.
 */
    void
ergodicBSTree ( BSTreeNode *pCurrent  )
{
    if(NULL == pCurrent) {
        return;
    }
    if(NULL != pCurrent->m_pLeft){
        ergodicBSTree(pCurrent->m_pLeft);
    }
    convertToDoubleList(pCurrent);
    if(NULL != pCurrent->m_pRight) {
        ergodicBSTree(pCurrent->m_pRight);
    }
    return ;
}		/* -----  end of function ergodicBSTreeeNode  ----- */
/**
 * @brief add the current node into the doulbe list.
 *
 * @param pCurrent. the current node to be converted.
 */
    void
convertToDoubleList (BSTreeNode *pCurrent  )
{
    pCurrent->m_pLeft = pListIndex;
    if(NULL != pListIndex) {
        pListIndex->m_pRight = pCurrent;
    }else {
        pHead = pCurrent;
    }
    pListIndex = pCurrent;
    cout << pCurrent->m_nValue << endl;
    return ;
}		/* -----  end of function converToDoubleList  ----- */
/*
 * ===  FUNCTION  ======================================================================
 *         Name:  main
 *  Description:
 * =====================================================================================
 */
    int
main ( int argc, char *argv[] )
{
    BSTreeNode *pRoot = NULL;
    pHead = NULL;
    pListIndex = NULL;
    addBSTreeNode(pRoot, 10);
    addBSTreeNode(pRoot, 4);
    addBSTreeNode(pRoot, 6);
    addBSTreeNode(pRoot, 8);
    addBSTreeNode(pRoot, 12);
    addBSTreeNode(pRoot, 14);
    addBSTreeNode(pRoot, 15);
    addBSTreeNode(pRoot, 16);
    addBSTreeNode(pRoot, 1);
    addBSTreeNode(pRoot, 18);

    ergodicBSTree(pRoot);

    return EXIT_SUCCESS;
}				/* ----------  end of function main  ---------- */

思路二

上述方法虽然本质上用的是递归,但是硬要跟树的遍历扯上关系,有点含混不清.何不直接用一个纯脆的递归方法呢?

伪代码

BST2Dlist(root):
if root=null
   then return null; #base case:null tree to null list.
   else preList=BST2Dlist(left[root]);
        postList=BST2Dlist(right[root]);
        combine preList, root, and postList to form one double list.

源代码

/*
 * =====================================================================================
 *
 *       Filename:  bst2list-3.cpp
 *
 *    Description:  convert a BST to sorted double list in place.
 *
 *        Version:  1.0
 *        Created:  2011年09月10日 00时41分00秒
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  Xu Dingxin (xdxn), xdxn2010@gmail.com
 *        Company:  GUCAS
 *
 * =====================================================================================
 */

#include        <stdlib.h>

#include        <iostream>
using namespace std;

template <class T>
class Node
{
public:
    T data;
    Node *left;
    Node *right;

    Node(){
        data = 0;
        left = NULL;
        right = NULL;
    }
    Node(T data)
    {
        this->data = data;
        left = NULL;
        right = NULL;
    }
};

/**
 * @brief insert a new element to the BST.
 *
 * @param root reference to root of the BST.
 * @param data data field of the new element.
 *
 * @return
 */
    template <class T>
void TreeInsert(Node<T> *&root, T data)
{
    if(root == NULL){
        root = new Node<T>(data);
    }else{
        if ( data < root->data ) {
            TreeInsert(root->left, data);
        }else{
            TreeInsert(root->right, data);
        }
    }
}

/**
 * @brief traverse the BST in inorder.
 *
 * @param root
 */
template <class T>
    void
InorderTraverse (Node<T> *root)
{

    if ( root == NULL ) {
        return;
    }
    InorderTraverse(root->left);
    cout << root->data << "\t";
    InorderTraverse(root->right);
    return ;
}               /* -----  end of function InorderTraverse  ----- */
/**
 * @brief traverse the BST in preorder.
 *
 * @param root
 */
template <class T>
    void
PreOrderTraverse ( Node<T>* root )
{
    if(root == NULL)
        return;
    cout << root->data << "\t";
    PreOrderTraverse(root->left);
    PreOrderTraverse(root->right);
    return ;
}               /* -----  end of function PreOrderTraverse  ----- */
/**
 * @brief traverse the BST in postorder.
 *
 * @param root
 */
template <class T>
    void
PostOrderTraverse ( Node<T>* root )
{
    if(root == NULL)
        return;
    PostOrderTraverse(root->left);
    PostOrderTraverse(root->right);
    cout << root->data << "\t";
    return ;
}               /* -----  end of function PostOrderTraverse  ----- */
/**
 * @brief convert the BST to a sorted double list.
 *
 * @param root root of BST.
 *
 * @return pointer to the list head.
 */
template <class T>
   Node<T>*
BST2DList ( Node<T>* root )
{
    if(root == NULL)
        return NULL;
    Node<T>* left = BST2DList(root->left);
    Node<T>* right = BST2DList(root->right);

    Node<T>* listHead;
    if(left == NULL) {
        listHead = root;
    }else{
        //append root to the left list.
        listHead = left;
        Node<T>* tmp = listHead;
        while(tmp != NULL && tmp->right != NULL){
            tmp = tmp->right;
        }
        tmp->right = root;
        root->left = tmp;
    }

    if ( right != NULL ) {
        root->right = right;
        right->left = root;
    }
    return listHead;
}               /* -----  end of function BST2DList  ----- */
/**
 * @brief append bNode to aNode.
 *
 * @param aNode
 * @param bNode
 */
template <class T>
    static void
Join ( Node<T>*aNode, Node<T>* bNode )
{
    aNode->right = bNode;
    bNode->left = aNode;
    return ;
}               /* -----  end of function Join  ----- */
/**
 * @brief append bList to aList.
 *
 * @param aList
 * @param bList
 *
 * @return
 */
template <class T>
    static Node<T>*
ListJoin ( Node<T>* aList, Node<T>*bList )
{
    if(aList == NULL)
        return bList;
    if(bList == NULL)
        return aList;

    Node<T>* aLast = aList->left;
    Node<T>* bLast = bList->left;

    //append bList to aLast
    aLast->right = bList;
    bList->left = aLast;

    //link bLast to aList to form a circular list..
    bLast->right = aList;
    aList->left = bLast;
    return aList;
}               /* -----  end of function ListJoin  ----- */
/**
 * @brief convert a BST to a sorted double circular list.
 *
 * @param root
 *
 * @return
 */
template <class T>
    Node<T>*
BST2DCList ( Node<T>* root )
{
    if(root == NULL)
        return NULL;

    char tmp;
    Node<T>* left = BST2DCList(root->left);
    Node<T>* right = BST2DCList(root->right);

    //make the root node length-1 double circular list.
    root->left = root;
    root->right = root;

    //combine the left, root and right sub-list.
    left = ListJoin(left, root);
    left = ListJoin(left, right);
    return left;
}               /* -----  end of function BST2DCList  ----- */
/**
 * @brief print double list.
 *
 * @param list
 */
template <class T>
    void
PrintList ( Node<T>*list )
{
    if(list == NULL)
        return;
    Node<T> *tmp = list;
    while(tmp != NULL) {
        cout << tmp->data << "\t";
        tmp = tmp->right;
    }
    return ;
}               /* -----  end of function PrintList  ----- */
/**
 * @brief print double circular list.
 *
 * @param list
 */
template <class T>
    void
PrintDCList ( Node<T>* list )
{
    if(list == NULL)
        return;
    Node<T>* tmp = list;
    do{
        cout << tmp->data << "\t";
        tmp = tmp->right;
    }while(tmp != list);
    return ;
}               /* -----  end of function PrintDCList  ----- */
/*
 * ===  FUNCTION  ======================================================================
 *         Name:  main
 *  Description:
 * =====================================================================================
 */
    int
main ( int argc, char *argv[] )
{
    Node<int> *root = new Node<int>(10);
    TreeInsert(root, 6);
    TreeInsert(root, 8);
    TreeInsert(root, 4);
    TreeInsert(root, 12);
    TreeInsert(root, 14);
    TreeInsert(root, 16);
    TreeInsert(root, 11);

    InorderTraverse(root);
    cout << endl;
    PreOrderTraverse(root);
    cout << endl;
    PostOrderTraverse(root);
    cout << endl;

    //Node<int>* list = BST2DList(root);
    //cout << "convertion result:" << endl;
    //PrintList(list);
    //cout << endl;

    Node<int>* dclist = BST2DCList(root);
    cout << "convertion result:" << endl;
    PrintDCList(dclist);
    cout << endl;
    return EXIT_SUCCESS;
}                               /* ----------  end of function main  ---------- */


在上述思路二中,提供了两种方法,即转换为普通双链表和带环双链表。
在普通双链表中,每次插入当前链表时需要遍历到链表尾端,耗时O(n);在带环双链表中,可以直接从头结点找到尾结点,耗时为
常数时间。

Reference

1.http://blog.csdn.net/v_JULY_v/article/details/6057286
2.http://cslibrary.stanford.edu/109/TreeListRecursion.html 

Advertisements

Posted in 算法, 技术 | Tagged: , | Leave a Comment »