конструкт и печатные элементы бинарного дерева (несбалансированное бинарное дерево), слева направо и снизу-вверх

Question

пожалуйста, дайте мне знать, как добиться следующего:

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

(I) слева направо, (II) снизу вверх, и (III) также структуру данных, которая будет использоваться & - управление памятью или распределение памяти.

Первоначально я думал, что это будет идти по обходу уровня, en-queue элементов, а затем печатать и де-очередь очереди.

Ваша помощь с примером кода, псевдокодом, алгоритмом высоко ценится.

С уважением

Answer 1

Ниже приведен пример несбалансированного бинарного дерева с использованием 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 

Answer 2

Кажется, вы уже поняли алгоритм. просто имейте в виду, что дерево не сбалансировано, нормальная реализация рекурсии может вызвать StackOverflow.