c++ - C++绘制控制台中的二叉树问题

我正在做一个需要创建二叉树的任务。我的二进制逻辑正确，但是我对如何以及在何处创建树感到困惑。下面的屏幕快照是我当前的输出，我想将其做成树形，其根在顶部，然后向下。在这一点上，如果更容易进行横向调整，那么我什至会为此解决。

#include <iostream>
#include <string>

using namespace std;

class TreeNode
{
public:
   void insert_node(TreeNode* new_node);
   void print_nodes() const;
   bool find(string value) const;
private:
   string data;
   TreeNode* left;
   TreeNode* right;
friend class BinarySearchTree;
};

class BinarySearchTree
{
public:
   BinarySearchTree();
   void insert(string data);
   void erase(string data);
   int count(string data) const;
   void print() const;
private:
   TreeNode* root;
};

/*
    BinarySearchTree Default constructor
*/

BinarySearchTree::BinarySearchTree()
{
   root = NULL;
}

void BinarySearchTree::print() const
{
   if (root != NULL)
   {
      root->print_nodes();
   }
}

void BinarySearchTree::insert(string data)
{
    // Creates a new node and sets values
   TreeNode* new_node = new TreeNode;
   // Saves data to new_node and pointers to NULL
   new_node->data = data;
   new_node->left = NULL;
   new_node->right = NULL;
   // sets root as node saved above
   if (root == NULL)
   {
       root = new_node;
   }
    /*
        If root has has been set then determine how to link new_node.
        root is the parent node and new_node will be the child of root
    */
   else root->insert_node(new_node);
}

void TreeNode::insert_node(TreeNode* new_node)
{
   // this-> referrs to root node
   if (new_node->data < this->data)
   {
       // Sets left node of root to
      // point to new_node
      if (this->left == NULL)
          {
              this->left = new_node;
          }
      // inserts a new node onto root->left
      else this->left->insert_node(new_node);
   }
   else if (this->data < new_node->data)
   {
      if (this->right == NULL)
          {
              // inserts a new node onto root->right
              this->right = new_node;

           }
      else this->right->insert_node(new_node);
   }
}

int BinarySearchTree::count(string data) const
{
   if (root == NULL) return 0;
   else if (root->find(data)) return 1;
   else return 0;
}

void BinarySearchTree::erase(string data)
{
   // Find node to be removed

   TreeNode* to_be_removed = root;
   TreeNode* parent = NULL;
   bool found = false;
   while (!found && to_be_removed != NULL)
   {
      if (to_be_removed->data < data)
      {
         parent = to_be_removed;
         to_be_removed = to_be_removed->right;
      }
      else if (data < to_be_removed->data)
      {
         parent = to_be_removed;
         to_be_removed = to_be_removed->left;
      }
      else found = true;
   }

   if (!found) return;

   // to_be_removed contains data

   // If one of the children is empty, use the other

   if (to_be_removed->left == NULL || to_be_removed->right == NULL)
   {
      TreeNode* new_child;
      if (to_be_removed->left == NULL)
         new_child = to_be_removed->right;
      else
         new_child = to_be_removed->left;
       if (parent == NULL) // Found in root
         root = new_child;
      else if (parent->left == to_be_removed)
         parent->left = new_child;
      else
         parent->right = new_child;
      return;
   }

   // Neither subtree is empty

   // Find smallest element of the right subtree

   TreeNode* smallest_parent = to_be_removed;
   TreeNode* smallest = to_be_removed->right;
   while (smallest->left != NULL)
   {
      smallest_parent = smallest;
      smallest = smallest->left;
   }

   // smallest contains smallest child in right subtree

   // Move contents, unlink child
   to_be_removed->data = smallest->data;
   if (smallest_parent == to_be_removed)
      smallest_parent->right = smallest->right;
   else
      smallest_parent->left = smallest->right;
}

bool TreeNode::find(string value) const
{
   if (value < data)
   {
      if (left == NULL) return false;
      else return left->find(value);
   }
   else if (data < value)
   {
      if (right == NULL) return false;
      else return right->find(value);
   }
   else
      return true;
}

void TreeNode::print_nodes() const
{

   if (this->right != NULL)
   {
       cout << data << "\n" << "\\" << "\n"  <<  this->right->data << " " << "\n";
       this->right->print_nodes();


        if (this->left != NULL)
        {
            cout <<  data << "\n" << "/" << "\n" << this->left->data << "\n";
            this->left->print_nodes();
        }
   }

}

int main()
{
   BinarySearchTree t;
   t.insert("D");
   t.insert("B");
   t.insert("A");
   t.insert("C");
   t.insert("F");
   t.insert("E");
   t.insert("I");
   t.insert("G");
   t.insert("H");
   t.insert("J");

   t.print();

   cout << "\n \n";

   cout << "\n \n";

   system("pause");
   return 0;
}

最佳答案

有很多方法可以做到这一点。这是一个:

A
|-B
| |-C
| | |-H
| | `-I
| `-D
|   |-F
|   `-G
`-E

这里A有 child B和E.B有C和D.等等...

那么我们如何才能做到这一点呢？这是伪代码:

Let S = {} (an empty global set of integers)

procedure indent(level)
for i in [0..level)
  if i \in S print "| "
  else print "  "

procedure tee(level)
indent(level)
print("|-")
S = S + { level }

procedure ell(level)
indent(level)
print("`-")
S = S - { level }

procedure print(node, level)
if node is null
  print("[null]" with newline) // only prints when 1 child is missing
else
  print(node label with newline)
  if node has any children
    tee(level)
    print(node.left, level + 1)
    ell(level)
    print(node.right, level + 1)

设置跟踪哪些列需要竖线。每个“T形”形状都会开始一个垂直条。每个“ell”形状在同一列中都以一个结束。

该集合可以是 bool(boolean) 数组(字符)，最初通过将其全部设置为零来使其为空。其余的几乎是对C的逐行转换。

我的快速结果是在一个包含31个节点的完整树上。

L0
|-L1
| |-L2
| | |-L3
| | | |-L4
| | | `-L5
| | `-L6
| |   |-L7
| |   `-L8
| `-L9
|   |-L10
|   | |-L11
|   | `-L12
|   `-L13
|     |-L14
|     `-L15
`-L16
  |-L17
  | |-L18
  | | |-L19
  | | `-L20
  | `-L21
  |   |-L22
  |   `-L23
  `-L24
    |-L25
    | |-L26
    | `-L27
    `-L28
      |-L29
      `-L30

对于普通读者来说，值得指出的是，此方法适用于带有子标签的N元树(例如，编译器中的抽象语法树)。在ell和tee中添加一个子名称参数，并为除最后一个(保留为tee)之外的每个子项调用ell。