Распечатайте двоичное дерево красивым способом

Question

Распечатайте двоичное дерево красивым способом

Просто интересно, могу ли я получить несколько советов по печати красивого бинарного дерева в виде:

Прямо сейчас то, что это печатает, является:

Я знаю, что мой пример переворачивается с того, что я сейчас печатаю, и это не имеет значения, если я печатаю из корня вниз, как сейчас печатает. Любые советы очень важны для моего полного вопроса:

Как мне изменить мои отпечатки, чтобы дерево выглядело как дерево?

    //Binary Search Tree Program

#include <iostream>
#include <cstdlib>
#include <queue>
using namespace std;

int i = 0;

class BinarySearchTree
{
private:
struct tree_node
{
tree_node* left;
tree_node* right;
int data;
};
tree_node* root;

public:
BinarySearchTree()
{
root = NULL;
}

bool isEmpty() const { return root==NULL; }
void print_inorder();
void inorder(tree_node*);
void print_preorder();
void preorder(tree_node*);
void print_postorder();
void postorder(tree_node*);
void insert(int);
void remove(int);
};

// Smaller elements go left
// larger elements go right
void BinarySearchTree::insert(int d)
{
tree_node* t = new tree_node;
tree_node* parent;
t->data = d;
t->left = NULL;
t->right = NULL;
parent = NULL;

// is this a new tree?
if(isEmpty()) root = t;
else
{
//Note: ALL insertions are as leaf nodes
tree_node* curr;
curr = root;
// Find the Node's parent
while(curr)
{
parent = curr;
if(t->data > curr->data) curr = curr->right;
else curr = curr->left;
}

if(t->data < parent->data)
{
parent->left = t;
}
else
{
parent->right = t;
}
}
}

void BinarySearchTree::remove(int d)
{
//Locate the element
bool found = false;
if(isEmpty())
{
cout<<" This Tree is empty! "<<endl;
return;
}

tree_node* curr;
tree_node* parent;
curr = root;

while(curr != NULL)
{
if(curr->data == d)
{
found = true;
break;
}
else
{
parent = curr;
if(d>curr->data) curr = curr->right;
else curr = curr->left;
}
}
if(!found)
{
cout<<" Data not found! "<<endl;
return;
}// 3 cases :
// 1. We're removing a leaf node
// 2. We're removing a node with a single child
// 3. we're removing a node with 2 children

// Node with single child
if((curr->left == NULL && curr->right != NULL) || (curr->left != NULL && curr->right == NULL))
{
if(curr->left == NULL && curr->right != NULL)
{
if(parent->left == curr)
{
parent->left = curr->right;
delete curr;
}
else
{
parent->right = curr->left;
delete curr;
}
}
return;
}

//We're looking at a leaf node
if( curr->left == NULL && curr->right == NULL)
{
if(parent->left == curr)
{
parent->left = NULL;
}
else
{
parent->right = NULL;
}
delete curr;
return;
}//Node with 2 children
// replace node with smallest value in right subtree
if (curr->left != NULL && curr->right != NULL)
{
tree_node* chkr;
chkr = curr->right;
if((chkr->left == NULL) && (chkr->right == NULL))
{
curr = chkr;
delete chkr;
curr->right = NULL;
}
else // right child has children
{
//if the node's right child has a left child
// Move all the way down left to locate smallest element

if((curr->right)->left != NULL)
{
tree_node* lcurr;
tree_node* lcurrp;
lcurrp = curr->right;
lcurr = (curr->right)->left;
while(lcurr->left != NULL)
{
lcurrp = lcurr;
lcurr = lcurr->left;
}
curr->data = lcurr->data;
delete lcurr;
lcurrp->left = NULL;
}
else
{
tree_node* tmp;
tmp = curr->right;
curr->data = tmp->data;
curr->right = tmp->right;
delete tmp;
}

}
return;
}

}
void BinarySearchTree::print_postorder()
{
postorder(root);
}

void BinarySearchTree::postorder(tree_node* p)
{
if(p != NULL)
{
if(p->left) postorder(p->left);
if(p->right) postorder(p->right);
cout<<"     "<<p->data<<"\n ";
}
else return;
}

int main()
{
BinarySearchTree b;
int ch,tmp,tmp1;
while(1)
{
cout<<endl<<endl;
cout<<" Binary Search Tree Operations "<<endl;
cout<<" ----------------------------- "<<endl;
cout<<" 1. Insertion/Creation "<<endl;
cout<<" 2. Printing "<<endl;
cout<<" 3. Removal "<<endl;
cout<<" 4. Exit "<<endl;
cout<<" Enter your choice : ";
cin>>ch;
switch(ch)
{
case 1 : cout<<" Enter Number to be inserted : ";
cin>>tmp;
b.insert(tmp);
i++;
break;
case 2 : cout<<endl;
cout<<" Printing "<<endl;
cout<<" --------------------"<<endl;
b.print_postorder();
break;
case 3 : cout<<" Enter data to be deleted : ";
cin>>tmp1;
b.remove(tmp1);
break;
case 4:
return 0;

}
}
}

21

c++

Решение

Другие решения

void btree::postorder(node* p, int indent)
{
if(p != NULL) {
if(p->right) {
postorder(p->right, indent+4);
}
if (indent) {
std::cout << std::setw(indent) << ' ';
}
if (p->right) std::cout<<" /\n" << std::setw(indent) << ' ';
std::cout<< p->key_value << "\n ";
if(p->left) {
std::cout << std::setw(indent) << ' ' <<" \\\n";
postorder(p->left, indent+4);
}
}
}

С этим деревом:

btree *mytree = new btree();
mytree->insert(2);
mytree->insert(1);
mytree->insert(3);
mytree->insert(7);
mytree->insert(10);
mytree->insert(2);
mytree->insert(5);
mytree->insert(8);
mytree->insert(6);
mytree->insert(4);
mytree->postorder(mytree->root);

Приведет к такому результату:

введите описание изображения здесь

16

Этого никогда не будет достаточно, если только кто-нибудь не вернётся назад, чтобы откалибровать вывод на дисплей. Но с помощью эвристики можно эффективно генерировать достаточно двоичных деревьев: учитывая высоту дерева, можно догадаться, какова ожидаемая ширина и множество узлов на разных глубинах.
Для этого нужно несколько штук, поэтому давайте начнем с функций более высокого уровня, чтобы обеспечить контекст.

Красивая функция печати:

   // create a pretty vertical tree
void postorder(Node *p)
{
int height = getHeight(p) * 2;
for (int i = 0 ; i < height; i ++) {
printRow(p, height, i);
}
}

Приведенный выше код прост. Основная логика в функции printRow. Давайте углубимся в это.

void printRow(const Node *p, const int height, int depth)
{
vector<int> vec;
getLine(p, depth, vec);
cout << setw((height - depth)*2); // scale setw with depth
bool toggle = true; // start with left
if (vec.size() > 1) {
for (int v : vec) {
if (v != placeholder) {
if (toggle)
cout << "/" << "   ";
else
cout << "\\" << "   ";
}
toggle = !toggle;
}
cout << endl;
cout << setw((height - depth)*2);
}
for (int v : vec) {
if (v != placeholder)
cout << v << "   ";
}
cout << endl;
}

getLine () делает то, что вы ожидаете: он сохраняет все узлы с заданной равной глубиной в vec. Вот код для этого:

void getLine(const Node *root, int depth, vector<int>& vals)
{
if (depth <= 0 && root != nullptr) {
vals.push_back(root->val);
return;
}
if (root->left != nullptr)
getLine(root->left, depth-1, vals);
else if (depth-1 <= 0)
vals.push_back(placeholder);
if (root->right != nullptr)
getLine(root->right, depth-1, vals);
else if (depth-1 <= 0)
vals.push_back(placeholder);
}

Теперь вернемся к printRow (). Для каждой строки мы устанавливаем ширину потока на основе того, насколько глубоко мы находимся в двоичном дереве. Это форматирование будет хорошим, потому что, как правило, чем глубже вы идете, тем больше ширина нужна. Обычно я говорю, потому что на вырожденных деревьях это не выглядело бы так красиво. Пока дерево грубо сбалансировано и мало (< 20 штук), должно получиться нормально.
Заполнитель необходим для правильного выравнивания символов ‘/’ и ‘\’. Поэтому, когда строка получается с помощью getLine (), мы вставляем заполнитель, если на указанной глубине нет ни одного узла. Заполнитель может быть установлен как угодно (1<<31) например. Очевидно, что это не надежно, потому что заполнитель может быть допустимым значением узла. Если кодер получил «спанк» и имеет дело только с десятичными числами, можно изменить код так, чтобы он генерировал строки с десятичным преобразованием через getLine (), и использовал заполнитель, такой как «_». (К сожалению, я не такой кодер: P)

Результат для следующих элементов, вставленных в порядке: 8, 12, 4, 2, 5, 15:

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

5

    //Binary tree (pretty print):
//                        ________________________50______________________
//            ____________30                                  ____________70__________
//      ______20____                                          60                ______90
//      10          15                                                          80// prettyPrint
public static void prettyPrint(BTNode node) {
// get height first
int height = heightRecursive(node);

// perform  level order traversal
Queue<BTNode> queue = new LinkedList<BTNode>();

int level = 0;
final int SPACE = 6;
int nodePrintLocation = 0;

// special node for pushing when a node has no left or right child (assumption, say this node is a node with value Integer.MIN_VALUE)
BTNode special = new BTNode(Integer.MIN_VALUE);

queue.add(node);
queue.add(null);    // end of level 0
while(! queue.isEmpty()) {
node = queue.remove();

if (node == null) {
if (!queue.isEmpty()) {
queue.add(null);
}

// start of new level
System.out.println();
level++;
} else {
nodePrintLocation = ((int) Math.pow(2, height - level)) * SPACE;

System.out.print(getPrintLine(node, nodePrintLocation));

if (level < height) {
// only go till last level
queue.add((node.left != null) ? node.left : special);
queue.add((node.right != null) ? node.right : special);
}
}
}
}
public void prettyPrint() {
System.out.println("\nBinary tree (pretty print):");
prettyPrint(root);
}
private static String getPrintLine(BTNode node, int spaces) {
StringBuilder sb = new StringBuilder();

if (node.data == Integer.MIN_VALUE) {
// for child nodes, print spaces
for (int i = 0; i < 2 * spaces; i++) {
sb.append(" ");
}

return sb.toString();
}

int i = 0;
int to = spaces/2;

for (; i < to; i++) {
sb.append(' ');
}
to += spaces/2;
char ch = ' ';
if (node.left != null) {
ch = '_';
}
for (; i < to; i++) {
sb.append(ch);
}

String value = Integer.toString(node.data);
sb.append(value);

to += spaces/2;
ch = ' ';
if (node.right != null) {
ch = '_';
}
for (i += value.length(); i < to; i++) {
sb.append(ch);
}

to += spaces/2;
for (; i < to; i++) {
sb.append(' ');
}

return sb.toString();
}

private static int heightRecursive(BTNode  node) {
if (node == null) {
// empty tree
return -1;
}

if (node.left == null && node.right == null) {
// leaf node
return 0;
}

return 1 + Math.max(heightRecursive(node.left), heightRecursive(node.right));
}

5

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

Вы можете посмотреть на точка руководство для получения дополнительной информации о синтаксисе и т. д.

4

#include <stdio.h>
#include <stdlib.h>

struct Node
{
struct Node *left,*right;
int val;
} *root=NULL;

int rec[1000006];
void addNode(int,struct Node*);
void printTree(struct Node* curr,int depth)
{
int i;
if(curr==NULL)return;
printf("\t");
for(i=0;i<depth;i++)
if(i==depth-1)
printf("%s\u2014\u2014\u2014",rec[depth-1]?"\u0371":"\u221F");
else
printf("%s   ",rec[i]?"\u23B8":"  ");
printf("%d\n",curr->val);
rec[depth]=1;
printTree(curr->left,depth+1);
rec[depth]=0;
printTree(curr->right,depth+1);
}
int main()
{
root=(struct Node*)malloc(sizeof(struct Node));
root->val=50;
//addNode(50,root);
addNode(75,root);    addNode(25,root);
addNode(15,root);    addNode(30,root);
addNode(100,root);    addNode(60,root);
addNode(27,root);    addNode(31,root);
addNode(101,root);    addNode(99,root);
addNode(5,root);    addNode(61,root);
addNode(55,root);    addNode(20,root);
addNode(0,root);    addNode(21,root);
//deleteNode(5,root);

printTree(root,0);
return 0;
}

void addNode(int v,struct Node* traveller)
{
struct Node *newEle=(struct Node*)malloc(sizeof(struct Node));
newEle->val=v;
for(;;)
{
if(v<traveller->val)
{
if(traveller->left==NULL){traveller->left=newEle;return;}
traveller=traveller->left;
}
else if(v>traveller->val)
{
if(traveller->right==NULL){traveller->right=newEle;return;}
traveller=traveller->right;
}
else
{
printf("%d Input Value is already present in the Tree !!!\n",v);
return;
}
}
}

Надеюсь, ты находишь это довольно …

Выход:

50
ͱ———25
⎸   ͱ———15
⎸   ⎸   ͱ———5
⎸   ⎸   ⎸   ͱ———0
⎸   ⎸   ∟———20
⎸   ⎸        ∟———21
⎸   ∟———30
⎸        ͱ———27
⎸        ∟———31
∟———75
ͱ———60
⎸   ͱ———55
⎸   ∟———61
∟———100
ͱ———99
∟———101

3

Вот небольшой пример печати кучи на основе массива в виде дерева. Для больших чисел нужно немного подстроиться под алгоритм. Я просто сделал сетку на бумаге и выяснил, какой индекс пространства будет выглядеть для каждого узла, а затем заметил, что существует определенное количество пространства для каждого узла, основанное на количестве мест в родительском элементе и уровне рекурсии, а также на том, как высокое дерево. Это решение выходит за рамки простой печати в порядке следования и удовлетворяет требованию «красоты».

#include <iostream>
#include <vector>

static const int g_TerminationNodeValue = -999;

class HeapJ
{
public:
HeapJ(int* pHeapArray, int numElements)
{
m_pHeapPointer = pHeapArray;
m_numElements = numElements;

m_treeHeight = GetTreeHeight(1);
}

void Print()
{
m_printVec.clear();

int initialIndex = 0;
for(int i=1; i<m_treeHeight; ++i)
{
int powerOfTwo = 1;
for(int j=0; j<i; ++j)
{
powerOfTwo *= 2;
}

initialIndex += powerOfTwo - (i-1);
}

DoPrintHeap(1,0,initialIndex);

for(size_t i=0; i<m_printVec.size(); ++i)
{
std::cout << m_printVec[i] << '\n' << '\n';
}
}

private:
int* m_pHeapPointer;
int m_numElements;
int m_treeHeight;
std::vector<std::string> m_printVec;

int GetTreeHeight(int index)
{
const int value = m_pHeapPointer[index-1];

if(value == g_TerminationNodeValue)
{
return -1;
}

const int childIndexLeft = 2*index;
const int childIndexRight = childIndexLeft+1;

int valLeft = 0;
int valRight = 0;

if(childIndexLeft <= m_numElements)
{
valLeft = GetTreeHeight(childIndexLeft);
}

if(childIndexRight <= m_numElements)
{
valRight = GetTreeHeight(childIndexRight);
}

return std::max(valLeft,valRight)+1;
}

void DoPrintHeap(int index, size_t recursionLevel, int numIndents)
{
const int value = m_pHeapPointer[index-1];

if(value == g_TerminationNodeValue)
{
return;
}

if(m_printVec.size() == recursionLevel)
{
m_printVec.push_back(std::string(""));
}

const int numLoops = numIndents - (int)m_printVec[recursionLevel].size();
for(int i=0; i<numLoops; ++i)
{
m_printVec[recursionLevel].append(" ");
}

m_printVec[recursionLevel].append(std::to_string(value));

const int childIndexLeft = 2*index;
const int childIndexRight = childIndexLeft+1;

const int exponent = m_treeHeight-(recursionLevel+1);
int twoToPower = 1;
for(int i=0; i<exponent; ++i)
{
twoToPower *= 2;
}
const int recursionAdjust = twoToPower-(exponent-1);

if(childIndexLeft <= m_numElements)
{
DoPrintHeap(childIndexLeft, recursionLevel+1, numIndents-recursionAdjust);
}

if(childIndexRight <= m_numElements)
{
DoPrintHeap(childIndexRight, recursionLevel+1, numIndents+recursionAdjust);
}
}
};

const int g_heapArraySample_Size = 14;
int g_heapArraySample[g_heapArraySample_Size] = {16,14,10,8,7,9,3,2,4,1,g_TerminationNodeValue,g_TerminationNodeValue,g_TerminationNodeValue,0};

int main()
{
HeapJ myHeap(g_heapArraySample,g_heapArraySample_Size);
myHeap.Print();

return 0;
}

/* output looks like this:

16

14          10

8     7     9     3

2   4 1           0

*/

2

Сделайте обход в порядке, спускаясь к детям, прежде чем перейти к братьям и сестрам. На каждом уровне, то есть когда вы спускаетесь к ребенку, увеличивайте отступ. После каждого выведенного узла выведите новую строку.

Какой-то псевдокод. Вызов Print с корнем вашего дерева.

void PrintNode(int indent, Node* node)
{
while (--indent >= 0)
std::cout << " ";
std::cout << node->value() << "\n";
}

void PrintNodeChildren(int indent, Node* node)
{
for (int child = 0; child < node->ChildCount(); ++child)
{
Node* childNode = node->GetChild(child);
PrintNode(indent, childNode);
PrintNodeChildren(indent + 1, childNode);
}
}

void Print(Node* root)
{
int indent = 0;
PrintNode(indent, root);
PrintNodeChildren(indent + 1, root);
}

1

Источник

Accepted Answer

Чтобы рекурсивно распечатывать дерево, вам нужно передать два аргумента вашей функции печати:

Узел дерева для печати, и
Уровень отступа

Например, вы можете сделать это:

void BinarySearchTree::postorder(tree_node* p, int indent=0)
{
if(p != NULL) {
if(p->left) postorder(p->left, indent+4);
if(p->right) postorder(p->right, indent+4);
if (indent) {
std::cout << std::setw(indent) << ' ';
}
cout<< p->data << "\n ";
}
}

Первоначальный вызов должен быть postorder(root);

Если вы хотите напечатать дерево с корнем вверху, переместите cout к вершине if,

13