posts - 15, comments - 10, trackbacks - 0, articles - 0

将排序二叉树转换成双向链表

Posted on 2014-01-03 00:41 whspecial 阅读(3598) 评论(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函数返回的是头节点
This is the core function to convert Tree to list. This function follows
  steps 1 and 2 of the above algorithm */
node* bintree2listUtil(node* root)
{
    // Base case
    if (root == NULL)
        return root;
 
    // Convert the left subtree and link to root
    if (root->left != NULL)
    {
        // Convert the left subtree
        node* left = bintree2listUtil(root->left);
 
        // Find inorder predecessor. After this loop, left
        // will point to the inorder predecessor
        for (; left->right!=NULL; left=left->right);
 
        // Make root as next of the predecessor
        left->right = root;
 
        // Make predecssor as previous of root
        root->left = left;
    }
 
    // Convert the right subtree and link to root
    if (root->right!=NULL)
    {
        // Convert the right subtree
        node* right = bintree2listUtil(root->right);
 
        // Find inorder successor. After this loop, right
        // will point to the inorder successor
        for (; right->left!=NULL; right = right->left);
 
        // Make root as previous of successor
        right->left = root;
 
        // Make successor as next of root
        root->right = right;
    }
 
    return root;
}
 
// The main function that first calls bintree2listUtil(), then follows step 3
//  of the above algorithm
node* bintree2list(node *root)
{
    // Base case
    if (root == NULL)
        return root;
 
    // Convert to DLL using bintree2listUtil()
    root = bintree2listUtil(root);
 
    // bintree2listUtil() returns root node of the converted
    // DLL.  We need pointer to the leftmost node which is
    // head of the constructed DLL, so move to the leftmost node
    while (root->left != NULL)
        root = root->left;
 
    return (root);

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理