C++

Forum

 
 
Create Binary Tree from Preorder Traversal

Numeri (84)
I am trying to read/write binary trees to a file for a little project I'm working on for fun. I got frustrated and gave up; now, I am trying again! So I am writing the tree to file (or, rather, to string for now) like so:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
string wBinTree(node *p)
{
    string str = "";
    if (!p)
    {
        str += "# ";
    }
    else
    {
        str += p->data + " ";
        str += (wBinTree(p->lChild)+wBinTree(p->rChild));
    }
    return str;    
}


So that this tree:
1
2
3
4
5
 
    root
   /    \
  aaa string
 / \    /
C   D  1231


will be serialized as this string:
root aaa C # # D # # string 1231 # # #

where 
#
is a null node.

But now I'm completely lost as to recreating the tree from a string. I thought of perhaps using an array/vector/string of 1's and 0's or trues and falses to keep track of where I was in the tree, but it's really beyond me... Any help?

Thank you in advance,
Numeri
vlad from moscow (6539)
You can use std::istringstream to read separate substrings and place them in member data 'data' of nodes.
Numeri (84)
I don't have a problem with that as much as I do with creating the nodes and connecting them in the right places; does that make sense?

Thank you!
Numeri
Numeri (84)
bump
cire (8284)
How did you build the tree in the first place?

Read back the individual tokens from the string representation and rebuild the tree in the same way. Generally that would involve some sort of insert function.
Script Coder (1468)
The best way I can think off (At The Moment) is to have three "states":

1)Add - Just adds element to left child
2)L-NULL - Just added a null node to left child
3)R-NULL - Just added null node to right child

start in state 1 and remain in state 1 until you add null node. If the null node is the left child go to the null node's parent and go back to state 1. If the null node is the right child go the the null node's grandparent and go back to state 1.

It should be logically correct.
Hope it helps.
Numeri (84)
@cire well, I've just hardcoded a tree in so far. It's probably not the best, but...

Using Script Coder's idea, this is what I have right now - sorry for the length:
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
128
129
130
131
132
133
134
135
136
137
138
 
#include <iostream>
#include <conio.h>
#include <string>
#include <vector>

using namespace std;

class node{
public:
	std::string data;
	node* lChild;
	node* rChild;
	node* parent;

	node()
	{
		data = "";
		lChild = NULL;
		rChild = NULL;
		parent = NULL;
	}
};

string wBinTree(node *p);
void rBinTree(string s, vector<node> *nodes);

int main()
{
	node a, b, c, d, e;
	a.lChild = &b; a.rChild = &c;
	b.lChild = &d; b.rChild = &e;
	a.data = "A"; b.data = "B"; c.data = "C"; d.data = "D"; e.data = "E";
	b.parent = &a;
	c.parent = &a;
	d.parent = &b;
	e.parent = &b;

	string str = wBinTree( &a );
	cout << str;
	vector< node > tree(1);
	
	rBinTree(str, &tree);
	cout << wBinTree( &tree[0] );

	_getche();
	return 0;
}

string wBinTree(node *p)
{
	string str = "";
	if (!p)
	{
		str += "# ";
	}
	else
	{
		str += p->data + " ";
		str += (wBinTree(p->lChild)+wBinTree(p->rChild));
	}
	return str;
}

void rBinTree(string s, vector<node> *nodes)
{
	nodes->resize(1);
	int pos = 0, curNode = 0;
	string data = "";
	enum state{
		AddL,
		AddR,
		NulL,
		NulR
	};

	state curState = AddL;

	while(pos < s.length())
	{
		switch(s[pos])
		{
		case ' ':
			if( data == "#" )
			{
				if( curState == AddL )
				{
					curState = NulL;
					if( curNode - 1 >= 0 )
					{
						curNode--;
						curState = AddR;
					}
				}
				if( curState == AddR )
				{
					curState = NulR;
					if( curNode - 2 >= 0 )
					{
						curNode -= 2;
						curState = AddR;
					}
				}
			}
			else
			{
				if( curState == AddL )
				{
					nodes->resize(nodes->size()+1);
					(*nodes)[curNode].lChild = &((*nodes)[curNode+1]);
					curNode++;
					(*nodes)[curNode].data = data;
				}
				if( curState == AddR )
				{
					nodes->resize(nodes->size()+1);
					(*nodes)[curNode].rChild = &((*nodes)[curNode+1]);
					curNode++;
					(*nodes)[curNode].data = data;
					curState = AddL;
				}
				if( curState == NulL )
				{
					;
				}
				if( curState == NulR )
				{
					;
				}
			}
			data = "";
			break;
		default:
			data += s[pos];
			break;
		}
		pos++;
	}
}


It is still having errors:
Unhandled exception at 0x551cc9c7 (msvcr100d.dll) in Binary Tree RW Testing.exe: 0xC0000005:
Access violation reading location 0xabababab.


Using breakpoints, I've found it doesn't 'break' until line 43, though I'm sure the error is in the rBinTree() function.

Any additional help?

Thank you,
Numeri
cire (8284)
well, I've just hardcoded a tree in so far. It's probably not the best, but...


I'd say it was bass ackwards. The utility of a tree is related to the order of the elements. What purpose does your tree serve?
Script Coder (1468)
Any additional help?

I would ditch the vector representation as it seems to be the one causing you problems and implement a tree class that allows you traverse a tree properly (similar to a linked list). Include functions like left(), right(), parent(), grandparent(). Also maybe have a "current" pointer to the current node with in the tree.

I hope what I am saying makes sense, if not just let me know what you are unclear on and I will re-explain.
JLBorges (13770)
> Any additional help?

"To iterate is human; to recurse, divine." - Laurence Peter Deutsch.

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
 
#include <string>
#include <memory>
#include <sstream>
#include <iostream>

struct node
{
    using pointer = std::shared_ptr<node> ;
    node( const std::string& d, const pointer& lc, const pointer& rc )
        : data(d), left_child(lc), right_child(rc) {}
    std::string data ;
    pointer left_child ;
    pointer right_child ;
};

std::ostream& write( std::ostream& stm, const node::pointer& tree )
{
    if(tree)
    {
        stm << tree->data << ' ' ;
        write( stm, tree->left_child ) ;
        return write( stm, tree->right_child ) ;
    }
    else return stm << "# " ;
}

node::pointer make_tree( std::istream& stm )
{
    std::string data ;
    if( stm >> data && data != "#" )
    {
        auto left_child = make_tree(stm) ;
        return std::make_shared<node>( data, left_child, make_tree(stm) ) ;
    }
    else return nullptr ;
}

int main()
{
    std::istringstream stm( "root aaa C # # D # # string 1231 # # #" ) ;
    auto tree = make_tree(stm) ;
    write( std::cout, tree ) << '\n' ;
}

http://ideone.com/KAFzYb
Numeri (84)
@cire aren't the two rather equivalent? Creating a tree and reading a tree from a string? Creating it is probably easier though, I guess.

@Script Coder if I got rid of the vector, how do I stop the nodes from being destroyed when the function ends? Also, do you mean the entire tree is one object?

@JLBorges Could you explain the entire node struct, especially line 8 and 10? Also, is auto different in C++11? Because I thought auto defined the scope that the variable should be accessible in. In addition, could you expound on the meaning of const node::pointer& tree? Is the pointer keyword new as well? Or have I (apparently) just not learned of it yet?

Thank you so much everyone!

Numeri
closed account (Dy7SLyTq)
auto doesnt define scope. auto does the type for you. i think it does it at run time but it might be compile time.

lets say you had:
auto i = 1;
auto becomes int. its useful in the range-based for loop and when dealing with templates.
Numeri (84)
Is that new?? I thought it was used like
auto int num = 10;
meaning that num was accessible whenever in the scope it was created in.
Last edited on
Zhuge (4664)
Yes, it's a C++11 feature. The use of auto as a scope specifier has almost never been used in modern code since it is the default.
cire (8284)
Prior to C++11, auto specified automatic storage duration. Of course, objects have this storage duration by default wherever such duration is desired (and it wasn't legal anywhere else), so nobody ever used it.

auto int num ; was entirely equivalent to int num ; in any block scope.

Since C++11, auto is used to automatically declare the type of a variable based on the static (compile-time) type of its initializer.

1
2
3
 
    std::vector<int> v ;
    // ...
    auto it = v.begin() ;  // it is of type std::vector<int>::iterator




In addition, could you expound on the meaning of const node::pointer& tree? Is the pointer keyword new as well?


using pointer = std::shared_ptr<node> ; is equivalent to typedef std::shared_ptr<node> pointer ; where pointer is an alias for the type std::shared_ptr<node>
JLBorges (13770)
> Could you explain the entire node struct, especially line 8 and 10?
> could you expound on the meaning of const node::pointer& tree?

Line 8 defines a C++11 type alias.
With struct node { using pointer = std::shared_ptr<node> ; /* ... */ };
we create a type alias; the node::pointer is an alias (another name) for the type std::shared_ptr<node>

In const node::pointer& tree, the type of tree is a reference to const node::pointer ie. a reference to a const shared pointer to node

For std::shared_pointer<>, see: http://msdn.microsoft.com/en-us/library/vstudio/hh279669.aspx

In line 10, the constructor uses an initialization list to initialize the members.
See:http://www.learncpp.com/cpp-tutorial/101-constructor-initialization-lists/



C++98 code (with node being a non-copyable type): 

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
 
#include <string>
#include <sstream>
#include <iostream>

struct node
{
    node( const std::string& d, node* lc, node* rc )
        : data(d), left_child(lc), right_child(rc) {}

    ~node() { delete left_child ; delete right_child ; }

    std::string data ;
    node* left_child ; // unique owning pointer
    node* right_child ; // unique owning pointer

    private: node( const node& ) ; void operator= ( const node& ) ; // non-copyable
};

std::ostream& write( std::ostream& stm, node* tree )
{
    if(tree)
    {
        stm << tree->data << ' ' ;
        write( stm, tree->left_child ) ;
        return write( stm, tree->right_child ) ;
    }
    else return stm << "# " ;
}

node* make_tree( std::istream& stm )
{
    std::string data ;
    if( stm >> data && data != "#" )
    {
        /*auto*/ node* left_child = make_tree(stm) ;
        return new node( data, left_child, make_tree(stm) ) ;
    }
    else return 0 ;
}

int main()
{
    std::istringstream stm( "root aaa C # # D # # string 1231 # # #" ) ;
    /*auto*/node* tree = make_tree(stm) ;
    write( std::cout, tree ) << '\n' ;
    delete tree ;
}

http://ideone.com/nE2QTZ
Numeri (84)
Thank you so much everyone! Getting functional code is no use when I don't understand it, so thanks for taking time to explain.

Numeri
Topic archived. No new replies allowed.