in-order для дерева 4 степени построенного на списке дочерних узлов, массиве структур 3 поля

[Audax_Rogerus]

Как сделать симметричный обход дерева 4-ой степени (С/С++), постороенного на списке дочерних узлов, массиве структур, 3 поля?

Структура, насколько я понял выглядит так (не уверен):

struct TreeNode
{
char key[3];
TreeNode* RightSib;
TreeNode* LeftChild;
};

[ViktorR]

У меня только одна мысль: Т.А. Павловская, Программирование на ЯВУ, Паскаль (С++) есть оба варианта книг.
В книге про Паскаль (есть в списке литературы, в соответствующем разделе) есть пример кода для работы с бинарным деревом: создание, обход, вставка, удаление, ...
Если этого нет в книжке про С++, то думаю, что алгоритм можно вытащить из версии для Паскаля.

[Audax_Rogerus]

Сообщение от ViktorR

У меня только одна мысль: Т.А. Павловская, Программирование на ЯВУ, Паскаль (С++) есть оба варианта книг.
В книге про Паскаль (есть в списке литературы, в соответствующем разделе) есть пример кода для работы с бинарным деревом: создание, обход, вставка, удаление, ...
Если этого нет в книжке про С++, то думаю, что алгоритм можно вытащить из версии для Паскаля.

Не все так просто... У меня не бинарное дерево, да и наворотов куча просто.

[BDA]

struct TreeNode
{
    char key;
    TreeNode* children[4];
};

Скорее так выглядит структура узла. Хотя для чего еще одно поле в структуре, не могу придумать. Ну, пусть, например, для родителя.

struct TreeNode
{
    char key;
    TreeNode* parent;
    TreeNode* children[4];
};

А обход, предположу, children[0], children[1], key, children[2], children[3].

[Audax_Rogerus]

Скорее так выглядит структура узла. Хотя для чего еще одно поле в структуре, не могу придумать. Ну, пусть, например, для родителя.

struct TreeNode
{
    char key;
    TreeNode* parent;
    TreeNode* children[4];
};

А обход, предположу, children[0], children[1], key, children[2], children[3].

Это массив дочерних узлов... а нужен список

[BDA]

struct TreeNode;

struct TreeNodeList
{
    TreeNode* node;
    TreeNodeList* next;
};

struct TreeNode
{
    char key;
    TreeNode* parent;
    TreeNodeList* children;
};

Ну вот будет список.

[Audax_Rogerus]

Сообщение от BDA

Tree

Сообщение от BDA

struct TreeNode;

struct TreeNodeList
{
    TreeNode* node;
    TreeNodeList* next;
};

struct TreeNode
{
    char key;
    TreeNode* parent;
    TreeNodeList* children;
};

Ну вот будет список.

Хорошо! А как будет выглядит in-order именно в коде?

[BDA]

Примерно:

TreeNodeList* tmp = tnode->children;
int count = 0;
while (tmp && count < 2) {
    go(tmp->node);
    tmp = tmp->next;
    ++count;
}
print(tnode->key);
while (tmp && count < 4) {
    go(tmp->node);
    tmp = tmp->next;
    ++count;
}

[Audax_Rogerus]

void PrintTree(TreeNode* Root)
{
	if (Root == nullptr)
	{
		return;
	}
	else
	{
		cout << Root->key << endl;
		PrintTree(Root->Children->Node);
		PrintTree(Root->Children->pNext->Node);
		PrintTree(Root->Children->pNext->pNext->Node);
		PrintTree(Root->Children->pNext->pNext->pNext->Node);
	}
}

Такой вариант может быть или он неверен?

[BDA]

Такой код реализует pre-order, а не in-order. Так "обойти" список можно только если в нем есть TreeNodeList для отсутствующих детей тоже (Node = nullptr).