Создавать и печатать элементы двоичного дерева (несбалансированное двоичное дерево) слева направо и снизу вверх
Пожалуйста, дайте мне знать, как добиться следующего:
У меня есть двоичное дерево, которое является несбалансированным, с левым и правым поддеревьями. Я должен напечатать значения узлов этого несбалансированного двоичного дерева в последовательности
(i) слева направо, (ii) снизу вверх и (iii) также структура данных, которая будет использоваться, а также управление ее памятью или распределение памяти.
Сначала я подумал, что это будет проходить по уровню-порядку, ставить элементы в очередь, а затем распечатывать и снимать очередь с очереди.
Ваша помощь с примером кода, псевдокода, алгоритма высоко ценится.
С уважением
2 ответа
Вот пример несбалансированного двоичного дерева с использованием C++. Данные, передаваемые в каждом узле, представляют собой простое целочисленное значение (вместе с данными управления левого и правого дочерних указателей и глубиной для уровня узла).
Надеемся, что это показывает, как вставка посещает узлы в дереве, пока не найдет подходящее место для вставки нового узла в дерево.
Левое поддерево содержит значения, которые меньше текущего узла. Таким образом, если текущий узел содержит значение 9, то левое поддерево этого узла состоит из узлов, значение которых меньше 9.
Правое поддерево содержит значение, которое больше текущего узла. Таким образом, если текущий узел содержит значение 9, тогда правое поддерево этого узла состоит из узлов, значение которых больше 9.
При посещении каждого узла, если вы хотите найти значение, которое больше, чем значение текущего узла, просмотрите правое поддерево. Если вы хотите найти значение, которое меньше значения текущего узла, просмотрите левое поддерево.
// tree_data.cpp : Defines the entry point for the console application.
//
// VS2005 standard include for precompiled headers, etc.
#include "stdafx.h"
// C++ iostream header for standard output in namespace std::
#include <iostream>
// An unbalanced, ordered binary tree
// Left subtree are items less than the node value.
// Right subtree are items greater than the node value.
// The items are in order from left most leaf to the right most leaf
// however the left and right subtrees may be unbalanced meaning not the same
// depth depending on the order of inserts. In other words if there are
// a large number of consecutive inserts with decreasing values the
// result will be a tree whose root is the first value inserted with a
// long left tree of decreasing values and no right hand tree at all.
struct TreeNode {
TreeNode *pLeft; // node that is less than the current node
TreeNode *pRight; // node that is greater than the current node
int iValue; // value for this node
int iDepth; // depth of this node in the tree, number of levels
};
typedef TreeNode *TreeHead;
const TreeHead emptyTree = 0;
// Since we use new to allocate tree nodes, the InsertNode () function could
// conceivably throw a memory allocation exception.
void InsertNode (int iValue, TreeHead &pTree)
{
TreeNode TreeHeadInit = {emptyTree, emptyTree, iValue, 0};
if (pTree == emptyTree) {
// initialize the tree with this first item and return
pTree = new TreeNode;
*pTree = TreeHeadInit;
return;
}
// Tree is not empty so lets find the place to put this new item to
// be inserted. We traverse the tree until we find the correct empty
// spot in the tree and then we put it there. If we come across the
// value already in the tree then we do nothing and just return.
TreeHead pTreeStruct = pTree;
while (pTreeStruct != emptyTree) {
// remember the depth of the current node as it will become the parent
// node if we reach the outer most leaf and need to add a new node.
TreeHeadInit.iDepth = pTreeStruct->iDepth;
if (pTreeStruct->iValue == iValue) {
// since we have found a node with the value specified then we
// are done and we do nothing.
return; // do nothing
} else if (pTreeStruct->iValue < iValue) {
if (pTreeStruct->pRight == emptyTree) {
// we have reached the place where we need to add a new node to
// extend the right tree with this greater value than the current
// node contains. allocate the node then break to initialize it.
pTreeStruct = pTreeStruct->pRight = new TreeNode;
break;
}
// the value to insert is greater than this node so we
// traverse to the right where values greater than the
// value of the current node are located.
pTreeStruct = pTreeStruct->pRight;
} else {
if (pTreeStruct->pLeft == emptyTree) {
// we have reached the place where we need to add a new node to
// extend the left tree with this greater value than the current
// node contains. allocate the node then break to initialize it.
pTreeStruct = pTreeStruct->pLeft = new TreeNode;
break;
}
// the value to insert is less than this node so we
// traverse to the left where values less than the
// value of the current node are located.
pTreeStruct = pTreeStruct->pLeft;
}
}
// update this new node that has been added to the tree and
// set its depth to be one more than the depth of its parent node.
TreeHeadInit.iDepth++;
*pTreeStruct = TreeHeadInit;
return;
}
// print the tree starting with the lowest value to the highest value.
// for each node we want to print out the left item which is lower than
// the node's value and then the right item which is higher than the
// node's value.
void PrintTreeInOrder (TreeHead pTree)
{
if (pTree != emptyTree) {
PrintTreeInOrder (pTree->pLeft);
std::cout << " value " << pTree->iValue << " depth " << pTree->iDepth << std::endl;
PrintTreeInOrder (pTree->pRight);
}
}
// print the tree from the root element indenting the printed lines to give an
// idea as to a diagram of the tree and how the nodes are sequenced.
void PrintTreeInDepth (TreeHead pTree)
{
if (pTree != emptyTree) {
for (int i = 0; i < pTree->iDepth; i++) std::cout << "|..";
std::cout << " value " << pTree->iValue << " depth " << pTree->iDepth;
if (pTree->pLeft != emptyTree) {
std::cout << " left " << pTree->pLeft->iValue << " ";
} else {
std::cout << " left NULL ";
}
if (pTree->pRight != emptyTree) {
std::cout << " right " << pTree->pRight->iValue << " ";
} else {
std::cout << " right NULL ";
}
std::cout << std::endl;
PrintTreeInDepth (pTree->pLeft);
PrintTreeInDepth (pTree->pRight);
}
}
int _tmain(int argc, _TCHAR* argv[])
{
TreeHead myTree = emptyTree;
// this is the first insert so will be the root of the unbalanced tree
InsertNode (9, myTree);
// now insert several items in decending order
InsertNode (8, myTree);
InsertNode (6, myTree);
InsertNode (5, myTree);
InsertNode (3, myTree);
InsertNode (2, myTree);
// now insert some other nodes haphazardly
InsertNode (12, myTree);
InsertNode (4, myTree);
InsertNode (1, myTree);
InsertNode (22, myTree);
InsertNode (16, myTree);
InsertNode (18, myTree);
InsertNode (17, myTree);
InsertNode (7, myTree);
InsertNode (13, myTree);
InsertNode (14, myTree);
InsertNode (15, myTree);
std::cout << "In order print" << std::endl;
PrintTreeInOrder (myTree);
std::cout << std::endl << std::endl;
std::cout << "Depth diagram from Root using left traversal" << std::endl;
PrintTreeInDepth (myTree);
return 0;
}
Вывод основного, который распечатывает дерево после вставки узлов, выглядит следующим образом. Эти выходные данные сначала показывают обход по порядку, который перечисляет значения узлов в порядке от наименьшего к наибольшему. Следующий вывод дает представление о структуре несбалансированного дерева, показывая, как левое поддерево от корневого элемента длиннее и имеет большее количество уровней, чем правое поддерево. Вы также можете видеть из второго набора выходных данных, какой узел содержит какие значения. Например, узел, значение которого равно 6, имеет в качестве своего левого дочернего узла узел, значение которого равно 5, и имеет в качестве правого дочернего элемента узел, значение которого равно 7.
In order print
value 1 depth 6
value 2 depth 5
value 3 depth 4
value 4 depth 5
value 5 depth 3
value 6 depth 2
value 7 depth 3
value 8 depth 1
value 9 depth 0
value 12 depth 1
value 13 depth 4
value 14 depth 5
value 15 depth 6
value 16 depth 3
value 17 depth 5
value 18 depth 4
value 22 depth 2
Depth diagram from Root using left traversal
value 9 depth 0 left 8 right 12
|.. value 8 depth 1 left 6 right NULL
|..|.. value 6 depth 2 left 5 right 7
|..|..|.. value 5 depth 3 left 3 right NULL
|..|..|..|.. value 3 depth 4 left 2 right 4
|..|..|..|..|.. value 2 depth 5 left 1 right NULL
|..|..|..|..|..|.. value 1 depth 6 left NULL right NULL
|..|..|..|..|.. value 4 depth 5 left NULL right NULL
|..|..|.. value 7 depth 3 left NULL right NULL
|.. value 12 depth 1 left NULL right 22
|..|.. value 22 depth 2 left 16 right NULL
|..|..|.. value 16 depth 3 left 13 right 18
|..|..|..|.. value 13 depth 4 left NULL right 14
|..|..|..|..|.. value 14 depth 5 left NULL right 15
|..|..|..|..|..|.. value 15 depth 6 left NULL right NULL
|..|..|..|.. value 18 depth 4 left 17 right NULL
|..|..|..|..|.. value 17 depth 5 left NULL right NULL
Кажется, вы уже поняли алгоритм. просто имейте в виду, что дерево не сбалансировано, нормальная реализация рекурсии может вызвать Stackru.