Le problème avec lequel j'ai des problèmes est le suivant.

Chaque nœud est représenté par deux bits x1 et x2. Si le nœud a un enfant gauche, x1 vaut 1. Sinon, x1 vaut 0. De même pour le cas d'un enfant droit, x2 peut être 1 ou 0. Avec cette règle, nous pouvons représenter un arbre binaire sous une séquence de bits formé par un parcours de précommande. Par exemple, à partir de "11010011001000", nous pouvons construire l'arbre suivant. Ecrivez une fonction récursive qui peut prendre une certaine séquence de bits donnée par un parcours de précommande et construire un arbre binaire.

entrez la description de l'image ici

Maintenant, j'ai obtenu des informations à partir d'une question similaire, Construire un arbre avec pré- traversée d'ordre donné, mais cela semble si différent car dans ce cas, vous devez considérer à la fois x1 et x2 pour un seul nœud ... J'y réfléchis depuis des heures mais je ne peux pas trouver un bon logique utilisant la récursivité. Toute aide serait appréciée. Merci!

1
Zack D 28 nov. 2017 à 14:51

3 réponses

Meilleure réponse

Une solution pourrait être simplement de parcourir votre arbre dans preorder tout en lisant votre séquence (deux valeurs et en les supprimant) et en ajoutant node si nécessaire.

Étant donné que vous avez ceci Node:

class Node {
    int value;
    public Node left;
    public Node right;
}

Vous pouvez créer un arbre comme celui-ci:

private static void createTree(Node root) {

    if(string.isEmpty() || root == null) {
        return;
    }

    if(string.charAt(0) == '1') {
        root.left = new Node();
    }

    if(string.charAt(1) == '1') {
        root.right = new Node();
    }
    string = string.substring(2);
    createTree(root.left);
    createTree(root.right);

}

Où string est juste une variable globale: static String string = "11010011001000";

Vous pouvez appeler la méthode comme ceci:

Node root = new Node();
createTree(root);

root sera la racine réelle de votre arbre.

1
Schidu Luca 28 nov. 2017 à 13:31

Votre question ressemble à celle-ci: http://www.geeksforgeeks.org/construct -un-arbre-spécial-de-traversée-de-précommande /

J'ai légèrement modifié le code donné pour répondre aux exigences spécifiques de votre cas. J'ai négligé l'ordre donné des nœuds (lettres) dans votre question et je me suis juste concentré sur la structure de l'arbre. La complexité temporelle est O(N) comme prévu. Tout semble clair donc je n'ai pas donné plus d'informations. Si vous avez des questions, n'hésitez pas à laisser un commentaire.

public class BinaryTree {
    class Node {
        char data;
        Node left, right;

        Node(char item) {
            data = item;
            left = right = null;
        }
    }

    class Index {
        int index = 0;
    }

    Node root;
    Index i = new Index();

    Node constructTreeUtil(String bitSequence, Index index_ptr, int n, Node temp) {
        int index = index_ptr.index; 

        String bits = bitSequence.substring(index * 2, index * 2 + 2);

        if (index == n)
            return null;

        temp = new Node((char) (index + 65));
        (index_ptr.index)++;

        if (bits.charAt(0) == '1')
            temp.left = constructTreeUtil(bitSequence, index_ptr, n, temp.left);

        if (bits.charAt(1) == '1')
            temp.right = constructTreeUtil(bitSequence, index_ptr, n, temp.right);

        return temp;
    }

    Node constructTree(String bitSequence, int n, Node node) {
        int index = 0;
        return constructTreeUtil(bitSequence, i, n, node);
    }

    public static void inorder(Node node) {
        if (node == null) return;
        System.out.println(node.data + "=> ");

        if (node.left != null)
          System.out.println("Left node: " + node.left.data);

        if (node.right != null)
          System.out.println("Right node: " + node.right.data);

        System.out.println();
        inorder(node.left);
        inorder(node.right);
    }

    public static void main(String args[]) {
        BinaryTree tree = new BinaryTree();

        // Bit sequence
        String bitSequence = "11010011001000";

        // Number of nodes
        int n = bitSequence.length() / 2;

        // Tree construction
        Node node = tree.constructTree(bitSequence, n, tree.root);

        // Print tree nodes inorder
        inorder(node);
    }
}
0
Dorukhan Arslan 28 nov. 2017 à 12:49

Avant d'atteindre 50 points de réputation, je mets ce déni de responsabilité dans la première ligne de mes réponses:

Je veux plutôt faire une brève réponse en commentaire, mais je n'ai pas assez de réputation, donc je fais une réponse complète, j'espère que mes réponses mal formées aideront encore.


DFS est parfait pour cette tâche - C'est essentiellement ce que fait la traversée de pré-commande:

def DFS(node):
    if(node == NULL) return
    sequence += notNull(node.l)
    sequence += notNull(node.r)
    DFS(node.l)
    DFS(node.r)

^^^ C'est ainsi que votre séquence est construite.

Heureusement, l'inverse est assez simple:

def inverseDFS(node):
    if(node == NULL) return
    node.l = new Node() if(readBuffer(sequence) == '1') else NULL
    node.r = new Node() if(readBuffer(sequence) == '1') else NULL
    inverseDFS(node.l)
    inverseDFS(node.r)

^^^ Seules les lignes 2 et 3 sont modifiées, maintenant au lieu de déterminer le caractère suivant de la séquence par l'existence de child, nous pouvons déterminer l'existence de child en fonction du prochain caractère lu, car il s'agit d'une relation siff.

Voici un code C ++ plus sophistiqué, et oui, je sais que mon style de codage peut en dégoûter d'autres.

/* Author haleyk10198 */
/* FOR ACM-ICPC WF*/
#include <bits/stdc++.h>

using namespace std;

struct Node{
    static int nodeCnt;
    int id;
    Node *l, *r;
    Node(){
        l = r = nullptr;
        this->id = nodeCnt++;
    }
    friend ostream& operator<<(ostream&, const Node);
}*root = new Node();

ostream& operator<<(ostream &out, const Node node){
    cout << "Node id: " << node.id
          << " | left child is " << (node.l? node.l->id: -1)
          << " | right child is " << (node.r? node.r->id: -1) << endl;
}

int Node::nodeCnt, strStreamPos = 0;
string str;

void dfs(Node *node){
    if(not node)
        return;

    if(str[strStreamPos++] == '1')
        node->l = new Node();
    if(str[strStreamPos++] == '1')
        node->r = new Node();

    cout << *node << endl;

    dfs(node->l);
    dfs(node->r);   
}

int main(){

    cin >> str;

    dfs(root);

    return 0;
}
2
haleyk 28 nov. 2017 à 12:56
47530911