как построить бинарное дерево из обходов по предзаказу и по порядку - PullRequest
Новая
       4

как построить бинарное дерево из обходов по предзаказу и по порядку

7 голосов
/ 06 марта 2011

Я выполняю задание по созданию бинарного дерева из обходов предзаказа и прохождения порядка (символ в каждом узле), и я пытаюсь обернуть свой мозг вокруг того, как построить настоящее дерево.

Вот моя мысльпроцесс для достижения этой цели:

  1. сохранить первую запись в предзаказе как корневой узел
  2. искать в записи для этой записи.
  3. взять символы вслева от корневого узла и сохраните их как массив символов.
  4. возьмите символы справа от корневого узла и сохраните их как массив символов.
  5. создайте новое дерево скорень как родительский элемент и его 2 дочерних элемента являются левым и правым массивами символов.
  6. продолжают рекурсивно работать, пока длина предзаказа не станет 0.

У меня есть шаги 1-4, позаботившиесяиз, но я не слишком уверен, как правильно построить свое дерево, и задавался вопросом, есть ли у кого-нибудь указатели.Спасибо.

Ответы [ 5 ]

5 голосов
/ 07 марта 2011

Выполните рекурсию перед построением нового дерева. Итак, ваш список будет выглядеть так:

  1. Если массивы имеют длину 1, просто верните листовой узел с этим единственным элементом в нем. (Это основа рекурсии.) (O (1))
  2. Сохранить первую запись в массиве предварительного заказа в качестве корневого узла. (O (1))
  3. Поиск в массиве inorder для этой записи. (О (п))
  4. Возьмите символы слева от корневого узла в массиве inorder и сохраните их как массив символов. Возьмите то же количество символов из массива предзаказа (после корня). (O (n) или O (1), когда просто разбрасываем указатели / указатели.)
  5. Возьмите символы справа от корневого узла и сохраните их как массив символов. Возьмите то же количество символов из массива предварительного заказа (после первой части - это должна быть только оставшаяся часть). (O (n) или O (1), когда вы просто бросаете указатели / указатели.)
  6. Рекурсивно сделать дерево из обоих левых массивов символов.
  7. Рекурсивно сделать дерево из обоих правых массивов символов.
  8. Объедините оба дерева с корневым узлом. (O (1).)

Нерекурсивные части могут быть выполнены в целом за O (n), и суммирование их для каждого уровня рекурсии также равно O (n). Таким образом, общее время выполнения зависит от количества уровней рекурсии. Если у вас приблизительно сбалансированное дерево, глубина составляет O (log n), таким образом, мы вообще получаем O (n · log n). Поскольку единственная обязательная медленная часть - это поиск корневого узла в массиве inorder, я думаю, мы могли бы оптимизировать это еще немного, если бы мы знали больше о дереве.

В худшем случае у нас есть один уровень рекурсии для каждого узла в дереве, что приводит к сложности O (n · n).

Пример: Предзаказ ABCDEF, Inorder FEDCBA, Дерево: 

                                   +---+
                                   | A |
                                   ++--+
                                    |
                            +---+   |
                            | B +<--+
                            ++--+
                             |
                     +---+   |
                     | C +<--+
                     ++--+
                      |
              +---+   |
              | D +<--+
              ++--+
               |
       +---+   |
       | E +<--+
       ++--+
        |
+---+   |
| F +<--+
+---+
0 голосов
/ 24 ноября 2016

Вот математический подход к достижению цели очень упрощенным способом:

Используемый язык: Java

`
/ * Алгоритм построения двоичного дерева из заданного Inorder и Preorderобходы.Ниже используется используемая терминология:

i: представляет предоставленный массив порядка

p: представляет предоставленный массив предварительного заказа

beg1: начальный индекс массива порядка

beg2: начальный индекс массива предварительного заказа

end1: конечный индекс массива предварительного заказа

end2: конечный индекс массива предварительного заказа

* /

public staticvoid constructTree (Узел root, int [] i, int [] p, int beg1, int end1, int beg2, int end2)

{

if(beg1==end1 && beg2 == end2)
{
    root.data = i[beg1];
}
else if(beg1<=end1 && beg2<=end2)
{
    root.data = p[beg2];
    int mid = search(i, (int) root.data);
    root.left=new Node();
    root.right=new Node();
    constructTree(root.left, i, p, beg1, mid-1, beg2+1, beg2+mid-beg1);
    System.out.println("Printing root left : " + root.left.data);
    constructTree(root.right, i, p, mid+1, end1, beg2+1+mid-beg1, end2);
    System.out.println("Printing root left : " + root.right.data);
}

}

`

Вам нужно вызвать функцию с помощью следующего кода: 

int[] i ={4,8,7,9,2,5,1,6,19,3,18,10}; //Inorder
int[] p ={1,2,4,7,8,9,5,3,6,19,10,18}; //Preorder
Node root1=new Node();
constructTree(root1, i, p, 0, i.length-1, 0, p.length-1);

Если вам нужно более подробное объяснение кода, пожалуйста, укажите это в комментариях.Я был бы рад помочь:).

0 голосов
/ 05 марта 2013

Я написал пример программы с использованием подхода «разделяй и властвуй» с использованием рекурсии в Java 

import java.util.LinkedList;
import java.util.Queue;

public class BinaryTreeNode {

private char data;
public char getData() {
    return data;
}
public void setData(char data) {
    this.data = data;
}
public BinaryTreeNode getLeft() {
    return left;
}
public void setLeft(BinaryTreeNode left) {
    this.left = left;
}
public BinaryTreeNode getRight() {
    return right;
}
public void setRight(BinaryTreeNode right) {
    this.right = right;
}
private BinaryTreeNode left;
private BinaryTreeNode right;

public static void levelTravesal(BinaryTreeNode node)
{
    Queue queue = new LinkedList();

    if(node == null)
        return;
    queue.offer(node);
    queue.offer(null);
    int level =0;
    while(!queue.isEmpty())
    {
        BinaryTreeNode temp = (BinaryTreeNode) queue.poll();

        if(temp == null)
        {
            System.out.println("Level: "+level);
            if(!queue.isEmpty())
                queue.offer(null);
            level++;
        }else {

        System.out.println(temp.data);

        if(temp.getLeft()!=null)
            queue.offer(temp.getLeft());

        if(temp.getRight()!=null)
            queue.offer(temp.getRight());
        }

    }
}

static int preIndex = 0;

public static void main(String[] args) {

    if(args.length < 2)
    {
        System.out.println("Usage: preorder inorder");
        return;
    }

    char[] preOrderSequence = args[0].toCharArray();
    char[] inOrderSequence = args[1].toCharArray();

    //char[] preOrderSequence = {'A','B','D','E','C','F'};
    //char[] inOrderSequence = "DBEAFC".toCharArray();

    if(preOrderSequence.length != inOrderSequence.length)
    {
        System.out.println("Pre-order and in-order sequences must be of same length");
        return;
    }

    BinaryTreeNode root = buildBinaryTree(preOrderSequence, inOrderSequence, 0, preOrderSequence.length-1);

    System.out.println();
    levelTravesal(root);


}

static BinaryTreeNode buildBinaryTree(char[] preOrder, char[] inOrder, int start, int end)
{
    if(start > end)
        return null;
    BinaryTreeNode rootNode = new BinaryTreeNode();
    rootNode.setData(preOrder[preIndex]);
    preIndex++;
    //System.out.println(rootNode.getData());
    if(start == end)
        return rootNode;
    int dataIndex = search(inOrder, start, end, rootNode.getData());
    if(dataIndex == -1)
        return null;
    //System.out.println("Left Bounds: "+start+" "+(dataIndex-1));
    rootNode.setLeft(buildBinaryTree(preOrder, inOrder, start, dataIndex - 1));
    //System.out.println("Right Bounds: "+(dataIndex+1)+" "+end);
    rootNode.setRight(buildBinaryTree(preOrder, inOrder, dataIndex+1, end));
    return rootNode;
}


static int search(char[] inOrder,int start,int end,char data)
{
    for(int i=start;i<=end;i++)
    {
        if(inOrder[i] == data)
            return i;
    }
    return -1;

}

}
0 голосов
/ 10 января 2013

Вы можете использовать приведенный ниже код, я только что написал для той же проблемы.У меня это работает. 

public class TreeFromInorderAndPreOrder {

public static List<Integer> inOrder = new ArrayList<Integer>();
public static List<Integer> preOrder = new ArrayList<Integer>();

public static void main(String[] args) {

    Node root = new Node();
    root.createRoot(5);
    for(int i = 0 ; i < 9 ; i++){
        if(i != 5){
            root.insert(i);
        }
    }

    inOrder(root);
    preOrder(root);
    for(Integer temp : inOrder){
        System.out.print(temp +  " ");
    }

    System.out.println();
    for(Integer temp : preOrder){
        System.out.print(temp + " ");
    }

    Node node1 = null;
    node1 = reConstructTree(root, (ArrayList<Integer>) inOrder, true);

    System.out.println();
    inOrder(node1);
    for(Integer temp : inOrder){
        System.out.print(temp +  " ");
    }

    System.out.println();

    for(Integer temp : preOrder){
        System.out.print(temp + " ");
    }

}

public static void inOrder(Node node){

    if(node!= null){
        inOrder(node.leftchild);
        inOrder.add(node.key);
        inOrder(node.rightChild);
    }

}

public static void preOrder(Node node){

    if(node != null){
        preOrder.add(node.key);
        preOrder(node.leftchild);
        preOrder(node.rightChild);
    }

}

public static Node reConstructTree(Node root, ArrayList<Integer> inOrder, 
    boolean  isLeft){

    if(preOrder.size() != 0 && inOrder.size() != 0){
        return null;
    }

    Node node = new Node();
    node.createRoot(preOrder.get(0));
    if(root != null && isLeft){
        root.leftchild = node;          
    }else if(root != null && !isLeft){
        root.rightChild = node;
    }
    int indx = inOrder.get(preOrder.get(0));
    preOrder.remove(0);
    List<Integer> leftInorder = getSublist(0, indx);
    reConstructTree(node, (ArrayList<Integer>) leftInorder, true);
    List<Integer> rightInorder = getSublist(indx+1, inOrder.size());
    reConstructTree(node, (ArrayList<Integer>)rightInorder, false);
    return node;

}

public static ArrayList<Integer> getSublist(int start, int end){
    ArrayList<Integer> list = new ArrayList<Integer>();
    for(int i = start ; i < end ; i++){
        list.add(inOrder.get(i));
    }

    return list;
}
}
0 голосов
/ 20 апреля 2011

См. Мой ответ на этот вопрос .Вы строите дерево, добавляя узлы в последовательности предварительного заказа, но используя положение порядка в качестве компаратора.

...