CS225/lab_avl/printtree.h at master · Tianhao1108/CS225 · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#pragma once

#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>

// Curiously recurring template pattern
// You don't actually need to extend this class,
// but here are the functions you need to implement
template <class DerivedDescriptor>
class GenericNodeDescriptor
{
	public:
	virtual bool isNull() const = 0;
	virtual std::string key() const = 0;
	virtual DerivedDescriptor left() const = 0;
	virtual DerivedDescriptor right() const = 0;
};

namespace private_print_functions
{
	template <class NodeDescriptor>
	int getPrintHeight(NodeDescriptor croot);

	template <class NodeDescriptor>
	void printSubtree(NodeDescriptor croot,
			std::vector<std::string> & output,
			int left,
			int top,
			int curr_width);
}

template <class NodeDescriptor>
void printTree(NodeDescriptor root, std::ostream & out = std::cout)
{
	using namespace private_print_functions;

	// Base case
	if (root.isNull())
	{
		out << "(empty)" << std::endl;
		return;
	}

	// Make a character matrix for outputting the tree onto
	int root_height = getPrintHeight(root);
	int print_matrix_width = (4 << root_height) - 3;
	int print_matrix_height = 2 * root_height + 1;

	// Initialize this matrix to be filled with spaces
	std::vector<std::string> output(print_matrix_height);
	for (size_t i = 0; i < output.size(); ++i)
		output[i] = std::string(print_matrix_width + 4, ' '); // + 4 extra room for long things

	// Recursively print each node
	printSubtree(root, output, 0, 0, print_matrix_width);

	// Output the matrix
	for (int row = 0; row < print_matrix_height; ++row)
		out << output[row] << std::endl;
}

namespace private_print_functions
{
	template <class NodeDescriptor>
	int getPrintHeight(NodeDescriptor croot)
	{
		if (croot.isNull())
			return -1;
		int l_height = getPrintHeight(croot.left());
		int r_height = getPrintHeight(croot.right());
		return 1 + std::max(l_height, r_height);
	}


	template <class NodeDescriptor>
	void printSubtree(NodeDescriptor croot, std::vector<std::string> & output, int left, int top, int curr_width)
	{
		// Convert data to std::string
		std::string nodeStr = croot.key();

		// Output data
		int left_start_shift = 1 - (nodeStr.length()-1)/2;
		for (size_t i = 0; i < nodeStr.length() && left + curr_width/2 + i < output[top].length(); i++)
			output[top][left + curr_width/2 + left_start_shift + i] = nodeStr[i];

		// Calculate / \ offset = 2 ^ height
		int branchOffset = (curr_width+3) >> 3; //(1 << (node->printData - 1));

		// Print left child
		int center = left + curr_width/2;
		int leftcenter = left + (curr_width/2 - 1)/2;
		int rightcenter = left + curr_width/2 + 2 + (curr_width/2 - 1)/2;

		if (!croot.left().isNull())
		{
			int branch_pos = center - branchOffset + 1;
			// draw left upper branch
			for (int pos = center + left_start_shift - 2; pos > branch_pos; pos--)
				output[top][pos] = '_';
			// draw left '/'
			output[top+1][branch_pos] = '/';
			// draw left lower branch
			for (int pos = branch_pos-1; pos > leftcenter + 2; pos--)
				output[top+1][pos] = '_';
			// draw left subtree
			printSubtree(croot.left(), output, left, top+2, curr_width/2 - 1);
		}

		// Print right child
		if (!croot.right().isNull())
		{
			int branch_pos = center + branchOffset + 1;
			// draw right upper branch
			for (int pos = center + left_start_shift + nodeStr.length() + 1; pos < branch_pos; pos++)
				output[top][pos] = '_';
			// draw right '\'
			output[top+1][branch_pos] = '\\';
			// draw right lower branch
			for (int pos = branch_pos+1; pos < rightcenter; pos++)
				output[top+1][pos] = '_';
			// draw right subtree
			printSubtree(croot.right(), output, left + curr_width/2 + 2, top+2, curr_width/2 - 1);
		}
	}
}