Преобразование "А(B(CD)и электронная(ФГ))" в дерево


Это было на самом деле спросили в интервью. Я сделал это в лучшем виде, я мог бы и хотел бы оптимизировать, если есть хоть один шанс сделать это.

Входные данные:

a(b(cd)e(fg)) 

Вывод должен быть:

                            a
                           / \
                          b   e
                         / \ / \
                        c  d f  g

Мой текущий код:

#include<stdio.h>
#include<malloc.h>
#include<string.h>

struct node
{
    char x;
    struct node *left;
    struct node *right;
}*root;

char a[30];
int i=0,n;

void tre(struct node * p) //function that I am using to convert the string to a tree
{
        if(a[i]=='(')
        {
            i++;
            struct node *temp=malloc(sizeof(struct node));
            temp->x=a[i];
            temp->left=temp->right=NULL;
            i++;
            if(p->left==NULL)
            {
                p->left=temp;
                tre(p->left);
            }
            if(a[i]!='('&&a[i]!=')')
            {
                struct node *tempp=malloc(sizeof(struct node));
                tempp->x=a[i];
                i++;
                p->right=tempp;
                tre(p->right);
            }
        }
        else
        if(a[i]==')')
        {
            i++;
        }

}    

void inorder(struct node *p)//inorder traversal of the tree made
{    
    if(p!=NULL)
    {
        inorder(p->left);
        printf("%c ",p->x);
        inorder(p->right);
    }
}

main()
{
    printf("Enter the string : ");
    scanf("%s",a);
    struct node *temp=malloc(sizeof(struct node));
    temp->x=a[i];
    temp->left=temp->right=NULL;
    i++;
    root=temp;
    tre(root);
    inorder(root);
}


244
5
c
задан 10 декабря 2011 в 10:12 Источник Поделиться
Комментарии
2 ответа

Если об этом спрашивали в интервью, тогда как человек, задавая вопрос, я ожидал бы вам задать пару вопросов о формате ввода. У нас здесь на простом примере, относительно понятно, но есть некоторые субтитры, которые выходят в этой форме, что нам нужно выделить из входного формата.


  • Как представлены нулевые ветки?

  • Как узлы со значением ')' или '(' представлено.

  • Если мы откроем '(' будут всегда два узла до ')'

Моя первая проблема будет эти глобальные переменные:

char a[30];
int i=0,n;

Глобальных переменных делает код труднее изменять и поддерживать в долгосрочной перспективе и следует избегать в большинстве случаев. Передавать их в качестве параметров и вещи стали гораздо более гибкими.

Второй момент-это объявлять каждую переменную на отдельной строке (это гораздо более читабельным). И попробовать и сделать имена более осмысленным а,я,н не имеют никакого значения, так что я понятия не имею, что вы собираетесь использовать их для.

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

typedef struct node
{
char x;
struct node *left;
struct node *right;
} Node;

void tre(struct node * p) //function that I am using to convert the string to a tree

Если мы строим дерево, я бы нормально ожидать, что возвращаемое значение дерева мы строим. Не способ заполнения дерева. Поэтому я бы ожидал, что сигнатура функции выглядит так:

Node* tre(char const* input)  // potentially more parameters to deal with position.

Я считаю, что логика в ВЫ основных функций очень трудно следовать. Вы, кажется, только узлы, если есть открытая скобка ' ( ' , что не представляется правильным. Вы ничего не делаете, когда есть рядом бандажа? Вы проверить, если левый на текущий узел является нулем, но не прямо на текущем узле. Я ожидаю, что код будет изначально более симметрично. Тот факт, что он не делает это тяжелее, чтобы следовать.

В качестве интервьюера вещи, я бы посмотрел на:


  • Проверка ошибок:

  • Двоичный код, дерево симметрично. Обратите внимание, что ниже.
    Делать левую и правую ветви должны выглядеть одинаково.

  • функция, которая анализирует входной сигнал должен работать на одном узле:
    Ты, кажется, работаешь на один узел и часть следующего.

Я написал код и минута выглядит так:
(Теперь, что я написал выглядит так же, как Уинстон)

Node* parseTree(char const* data, size_t* pos)
{
if (data[(*pos)] == '\0')
{ // Appropriate error msg
exit(1);
}

// Allocate the tree here. (initialize all members)
Node* result = malloc(sizeof(Node));
result->value = data[(*pos)++];
result->left = NULL;
result->right = NULL;

// Now check for sub branches.
if (data[(*pos)] == '(')
{
// Move past the '('
(*pos)++;

result->left = parseTree(data, pos);
result->right = parseTree(data, pos);

if ((*pos) != ')')
{ // Appropriate error msg
exit(1);
}
// Move past the ')'
(*pos)++;
}
// Done.
return result;
}
Node* buildTree(char const* data)
{
if (data == NULL)
{ // Appropriate error msg
exit(1);
}
size_t pos = 0;
return parseTree(data, &pos);
}

Идеальный в порядке обхода дерева.

Но он не распечатывает, что на выходе должно быть:

                        a
/ \
b e
/ \ / \
c d f g

Для печати этого вам понадобится несколько вещей:


  • Глубины дерева.

  • Максимальная ширина (связанные с максимальная глубина)

  • Широтой первый способ печати на дереве.

Примечание: Если я делаю интервью, я бы спросил об этом, чтобы убедиться, что вы могли бы сделать широту первый обход дерева. Который включает используя цикл, а не рекурсия.

2
ответ дан 11 декабря 2011 в 10:12 Источник Поделиться

void tre(struct node * p) //function that I am using to convert the string to a tree
{
if(a[i]=='(')
{

Я рекомендую не использовать такие короткие имена переменных

            i++;
struct node *temp=malloc(sizeof(struct node));
temp->x=a[i];
temp->left=temp->right=NULL;

Вы в принципе повторяете эти три линии в три раза. Если вы вместо этого в начале Тре вы можете избежать дублирования.

            i++;
if(p->left==NULL)

Учитывая то, как ваш код структурирован, не п->слева всегда будет null? Значение, переданное в тре всегда свеже созданный узел

            {
p->left=temp;
tre(p->left);
}
if(a[i]!='('&&a[i]!=')')

Зачем вам нужно, чтобы проверить это? Не будет ли это означать неверный ввод? Если так, возможно вы должны как-то сообщать об ошибке.

            {
struct node *tempp=malloc(sizeof(struct node));
tempp->x=a[i];
i++;
p->right=tempp;
tre(p->right);
}

}
else
if(a[i]==')')
{
i++;
}

Опять же, в какой ситуации это будет называться?

}    

Как мне приблизиться к этой функции

stuct node * tre()
{
struct node * node = malloc(sizeof(struct node));
node->x = a[i++];
if(a[i] == '(')
{
node->left = tre();
node->right = tre();
assert(a[i++] == ')');
}
else
{
node->left = node->right = NULL;
}
return node;
}

Если я что-то упускаю, ваш пример вывода и код не совпадают. Поэтому я не собираюсь комментировать это.

2
ответ дан 10 декабря 2011 в 11:12 Источник Поделиться