c++ - 以漂亮的方式打印二叉树

Question

只是想知道我是否可以得到一些关于以以下形式打印漂亮二叉树的提示:

5
     10
          11
          7
               6
     3
          4
          2

现在打印的是:

   2
    4
    3 
    6
    7
    11
    10
    5

我知道我的示例与我当前正在打印的内容是颠倒的，如果我按照当前打印的方式从根目录向下打印并不重要。任何提示都非常感谢我的完整问题:

如何修改我的打印件以使树看起来像一棵树？

    //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;

       }
    }
}

Answer 1

为了以递归方式漂亮地打印一棵树，您需要将两个参数传递给您的打印函数:

• 要打印的树节点，以及
• 缩进级别

例如，您可以这样做:

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 的顶部。