1
我正在做一个任务，我需要创建一个二叉树。我有正确的二进制逻辑，但我很难在如何以及在哪里创建树。下面的屏幕截图是我目前的输出结果，我想将它制作成树形的形式，其顶部的根位于下方。此时如果水平线变得更容易，我甚至会在这一点上解决这个问题。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;
}