二叉查找法在单链表中的应用[j]

我正试图将二叉搜索树扁平化为单链表。

二叉搜索树:

      6
    /   
   4     8
  /      
 1  5     11
         / 
       10

扁平单链表:

1 -> 4 -> 5 -> 6 -> 8 -> 10 -> 11

由于某种原因，我似乎弄不明白这个。

我有一个树节点结构:

typedef stuct node {
    int key;
    struct node *left;
    struct node *right;
} Node;

我有一个函数来创建和分配内存到树节点:

Node* newNode (int key) {
    Node *new = malloc (sizeof(Node));
    new->left = NULL;
    new->right = NULL;
    new->key = key;
    return new;
}

我有一个结构体的列表节点:

typedef struct list {
    int key;
    struct list* next;
} List;

我有一个函数来创建列表节点:

List* newListNode (int key) {
    List *new = malloc(sizeof(List));
    new->key = key;
    new->next = NULL;
    return new;
}

我有工作函数来创建二叉搜索树，插入值，等等，但现在我需要创建一个函数来将树平铺成一个列表。

List* flattenToLL(Node* root) {
    ...
}

我似乎不知道如何把它扁平化成一个单链表。我看到很多其他的线程和网站讨论将二叉搜索树转换为双链表或循环链表，但没有一个是关于将值复制到单链表中的。如果有人能提供建议，我如何才能做到这一点，我将非常感激。这是一个家庭作业，所以如果你也能提供一个小的解释来帮助我学习，那就太好了。

这是相对简单的递归:

检查左侧节点;如果那里有东西，将左侧扁平化为list #1
检查右侧节点;如果那里有东西，把右边平到list #2
用当前节点
按顺序#1 -> #3 -> #2连接列表
返回连接的列表作为结果

下面是你如何编写它的代码:

List* flattenToLL(Node* root) {
    List *list1 = (root->left) ? flattenToLL(root->left) : NULL;
    List *list2 = (root->right) ? flattenToLL(root->right) : NULL;
    List *list3 = newNode(root->key);
    // The "middle" list3 cannot be NULL; append list2 to list3
    list3->next = list2; // If list2 is NULL, it's OK
    if (!list1) return list3; // Nothing to prepend
    List *last = list1;
    while (last->next) last=last->next; // Go to the end of list1
    last->next = list3; // Append list3+list2 to the end of list1
    return list1;
}

您需要按顺序遍历，将每个元素依次添加到列表中。

伪代码是:

def traverse (node, list):
    if node == NULL: return       # Ignore empty subtrees.
    traverse (node.left, list)    # Do left subtree first.
    list.append (node.data)       # Then current node.
    traverse (node.right, list)   # Then right subtree.
list = new List()                 # Create empty list.
traverse (root, list)             # Collapse tree to list.

就是这样，很简单。步骤1，处理左子树。步骤2，添加数据。步骤3，处理右子树。

唯一"聪明"的地方是正确处理空子树，使代码简洁。

请记住，如果指向最后一个元素(tail)的指针没有被缓存到某个地方，那么为了获得最大的效率，对链表进行追加操作可能是一个相对昂贵的操作。这将需要找到每个添加元素的尾部，这将把你的平坦化算法变成一个O(n²)。

由于在链表的开头插入元素几乎总是O(1)(由于必须维护一个head指针)，因此通常做反向序遍历更有效:

def traverse (node, list):
    if node == NULL: return       # Ignore empty subtrees.
    traverse (node.right, list)   # Do right subtree first.
    list.insert (node.data)       # Then current node at list start.
    traverse (node.left, list)    # Then left subtree.

使平坦化操作保持在O(n)

Why dont you do inorder traversal and add values to list in a way.  
public List<Integer> inorderToList(TreeNode<Integer> node, List<Integer> list) {
        if(node == null) {
            return list;
        } 
        if (node != null) {
            list = inorderToList(node.getLeft(), list);
            list.add(node.getValue());
            list = inorderToList(node.getRight(), list);
        }
        return list;
    }

下面是Java代码，如果有人感兴趣的话:

public static Node bTreeToLinkedList(TreeNode root) {
    Node list1 = root.getLeftChild() != null ? bTreeToLinkedList(root.getLeftChild()) : null;
    Node list2 = root.getRightChild() != null ? bTreeToLinkedList(root.getRightChild()) : null;
    Node list3 = ll.new Node((int) root.getData());
    list3.setNext(list2);
    if (list1 == null)
        return list3;
    Node last = list1;
    while (last.getNext() != null)
        last = last.getNext();
    last.setNext(list3);
    return list1;
}

我们可以使用递归，为树中的每个级别构建一个链表，并将该列表添加到列表向量中。使用这种解决方案，我们需要跟踪我们所在的关卡，所以如果我们已经有一个关卡的链表，并且我们访问了一个已访问过的关卡上的节点，那么我们就可以添加到该列表中。

我没有为我自己的节点类添加任何代码，因为它与问题无关没有内存清理被演示，但是一个更好的解决方案是使用boost::shared_ptr来处理清理。

void generateLists(vector<list<node*>* >*& lists, node* root, int level)
{
    //base case
    if(root == NULL)
        return;
    //if we have don't have a linked list at this level so create this
    if((int)lists->size() == level)
    {
        list<node*>* ls = new list<node*>();
        ls->push_back(root);
        lists->push_back(ls);
    }
    else
    {
        //re-use existing list
        list<node*>* ls = lists->at(level);
        if(ls != NULL)
            ls->push_back(root);
    }
    //in order traversal
    generateLists(lists, root->left, level+1);
    generateLists(lists, root->right, level+1);
}
int main(void)
{
    //create a test binary tree
    node root(6);
    node n2(3);
    node n3(9);
    node n4(2);
    node n5(5);
    node n6(8);
    node n7(9);
    root.left = &n2;
    root.right = &n3;
    n2.left = &n4;
    n2.right=&n5;
    n3.left=&n6;
    n3.right=&n7;
    //will hold a vector of lists for each level in the tree
    vector<list<node*>* >* lists = new vector<list<node*>* >();
    int level=0;
    generateLists(lists, &root, level);
    vector<list<node*>* >::iterator it;
    //convert each level in the tree to a single linked list
    list<node*> flattened;
    for(it = lists->begin(); it != lists->end(); it++)
    {
        list<node*>* linkedList = (*it);
        list<node*>::iterator itNode;
        for(itNode = linkedList->begin(); itNode != linkedList->end(); itNode++)
            flattened.push_back(*itNode);
    }
    //output the tree as a linked list
    list<node*>::iterator itNode;
    for(itNode = flattened.begin(); itNode != flattened.end(); itNode++)
        cerr<<(*itNode)->val<<" ";
}

这里也有非递归的解决方案。

给你O(n)的时间复杂度和O(1)的空间复杂度。使用递归解决方案，如果您将其应用于大节点集的自己的输出，您可能会得到堆栈溢出。

 private static BSTNode head;
 private static BSTNode tail;
 public static void inorderTraversal(BSTNode node) {
        if(node.left != null) {
            inorderTraversal(node.left);
        }
        System.out.print(node.data + " ");
        constructLinkedList(node.data);
        if(node.right != null) {
            inorderTraversal(node.right);
        }
    }
public static void constructLinkedList(int data) {
        if(head == null) {
            head = new BSTNode(data);
            head.left = null;
            tail = head;
        } else {
            BSTNode node = new BSTNode(data);
            tail.right = node;
            tail.left = null;
            tail = node;
        }
   }
   public static void linkedListToString() {
        BSTNode curr = head;
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        while(curr.right != null) {
            sb.append(curr.data).append("->");
            curr = curr.right;
        }
        if(curr.right == null)
            sb.append(curr.data).append("->NULL");
        sb.append("]");
        System.out.print(sb.toString());
   }

相关内容

最新更新

热门标签：