Creating, modifying and accessing a tree
Contents
Creating and building a tree from scratch
A new empty tree is created by simply calling the empty constructor:
t = tree %#ok<NASGU,NOPTS>
t =
tree with properties:
Node: {[]}
Parent: 0
or specifying the root node content as an extra argument:
t = tree('I am the root node') %#ok<NOPTS>
t =
tree with properties:
Node: {'I am the root node'}
Parent: 0
Note that the object itself is composed only of a double array that holds the node's parent indices (0 for the root, which has no parent), and a cell array to hold the node's data.
Adding a node
We will add a child node to the root, and voluntarily make a mistake. You add nodes to another node in a tree using the addnode method. It requires you pass the index of the node you want to attach the node to, and the new node content. The root of the tree has always the index 1:
t.addnode(1, 'I am the first child of the root');
But look what happened to the tree stored in t:
disp(t.tostring)
I am the root node
Apparently, no nodes were attached to the root. It is because the tree class is not a handle class. It is a per-value class, so it cannot be edited by reference, like you would do in Java. It is the only tricky bit with this, and can be confusing if like me you are used to other OOP languages, such as Java.
So, when adding a node, you do not modify the variable t, but copy the resulting tree to t, like this:
t = t.addnode(1, 'I am the first child of the root');
disp(t.tostring)
I am the root node
|
I am the first child of the root
Since we specify the target node using its index in the tree, you might want to store it for a later usage. The second output of addnode is the index of the newly attached node, and can be used in the following manner:
t = tree('root'); [ t node1 ] = t.addnode(1, 'Node 1'); %% attach to root % node1 now contains the index of the first node. [ t node2 ] = t.addnode(1, 'Node 2'); %% attach to root [ t node11 ] = t.addnode(node1, 'Child of node 1'); %% attach to first node disp(t.tostring)
root
+--+--------+
| |
Node 1 Node 2
|
|
Child of node 1
Removing a node
Removing a node is not a trivial operation. The node gets removed, but its children cannot be left on their own. So when you remove a node, its children get reattached to the node's parent.
t = t.removenode(node1); disp(t.tostring)
root +-------+----+ | | Node 2 Child of node 1
What data to put in the tree?
Well, since node data are internally represented as a cell array, you can put anything, and it does not have to be homogeneous:
t = tree('string');
[t n1] = t.addnode(1, 124);
[t n2] = t.addnode(1, pi);
[t n3] = t.addnode(1, rand(5 ,5));
disp(t.tostring)
string +-----+---+------+ | | | 124 3.1416 <5x5 double>
Having non-homogeneous data in a tree can be nice, but the price to pay is that errors might pop up if you try some operations on trees that assume the data is homogeneous. There is no protection against such errors; we assume you know what you are doing.
Accessing the tree content
To get what is stored at a node, you must know its index, and use the get method:
t.get(1) % the root content t.get(n1) % first node content t.get(n2) % etc... t.get(n3)
ans =
string
ans =
124
ans =
3.1416
ans =
0.3816 0.4456 0.6797 0.9597 0.2551
0.7655 0.6463 0.6551 0.3404 0.5060
0.7952 0.7094 0.1626 0.5853 0.6991
0.1869 0.7547 0.1190 0.2238 0.8909
0.4898 0.2760 0.4984 0.7513 0.9593
Modifying the tree content
To change the data stored by one node, you use the counterpart method set, again with the node index. Careful: the by-value access trick plays again here, and you must assign the modified tree to a variable:
t = t.set(n2, 'I changed.');
disp(t.tostring)
string +-------+---+--------+ | | | 124 I changed. <5x5 double>
Grafting and chopping a branch
You can deal with trees like any good gardener would, and make operations such as grafting. Grafting is like adding a node to a tree, except that this time, you attach a whole tree to a node.
t = tree('A'); t = t.addnode(1, 'B'); t = t.addnode(1, 'C'); [t targetNode] = t.addnode(1, 'D');
We need to create another tree to demonstrate grafting. We could do this the usual way, but since tree is a per-value class, we can simply copy the first object to a new one, using the trivial syntax:
nt = t; t = t.graft(targetNode, nt); disp(t.tostring)
A
+--+-+---+
| | |
B C D
|
|
A
+-++--+
| | |
B C D
Et voilà!
Of course, grafting has its counterpart: chopping.
t = t.chop(targetNode); disp(t.tostring)
A ++-+ | | B C
Note that the target node was removed as well.
Getting a branch as a subtree
You might want to access a branch of the tree, and make a new tree of it. This is done with the subtree method, that requires the index of the node that will become the root of the new tree. All the subnodes of this node will be copied to the new tree:
lineage = tree.example; t = lineage.subtree(19); disp(t.tostring)
EMS
+-----------+-----+
| |
MS E
+--+--+ +-----+-----+
| | | |
MS.a MS.p E.a E.p
+--+--+ +--+--+
| | | |
E.al E.ar E.pl E.pr
Copying a tree and its structure
A very nice feature of this class, synchronized iteration, is based on copying tree structure. So we must know how to copy tree.
The tree class has a copy-constructor, if you pass it a tree as argument:
copy = tree(t); %#ok<NASGU>
Note this would have worked just the same using the trivial MATLAB assignment syntax:
copy = t;
Again, since tree is a per-value class, copy is an independent copy of the first tree. A modification made to one of the two trees will not affect the other.
These two calls copy the whole tree, node content included. Sometimes, you just need to get the tree layout or structure, which is the parent/children hierarchy of the tree, leaving behind any node content. There are several way to do that.
Using the copy-constructor with a 'clear' argument copy the tree, but discard any node content:
emptyTree = tree(t, 'clear');
disp(emptyTree.tostring)
ø
+-----+--+
| |
ø ø
++-+ +--+--+
| | | |
ø ø ø ø
++-+ ++-+
| | | |
ø ø ø ø
The 'ø' symbol is used to represent a node with empty content.
Using the copy-constructor with any other argument will fill the new tree with this argument:
oneTree = tree(t, 1); zeroTree = tree(t, 0); optimisticTree = tree(t, 'I feel great!'); trueTree = tree(t, true); % Display two trees side by side (we can use |horzcat| since their % display string have the same number of rows) disp( [ oneTree.tostring optimisticTree.tostring ] ) disp('-') disp( [ zeroTree.tostring trueTree.tostring ] )
1 I feel great!
+-----+--+ +-----------------------------+--------------+
| | | |
1 1 I feel great! I feel great!
++-+ +--+--+ +------+-------+ +--------------+--------------+
| | | | | | | |
1 1 1 1 I feel great! I feel great! I feel great! I feel great!
++-+ ++-+ +------+-------+ +------+-------+
| | | | | | | |
1 1 1 1 I feel great! I feel great! I feel great! I feel great!
-
0 true
+-----+--+ +-----------+-----+
| | | |
0 0 true true
++-+ +--+--+ +--+--+ +-----+-----+
| | | | | | | |
0 0 0 0 true true true true
++-+ ++-+ +--+--+ +--+--+
| | | | | | | |
0 0 0 0 true true true true
This is nice, because this way you can very easily generate trees that can be used to store extra information on the data stored in the first tree. For our C.elegans lineage, the lineage tree holds the cell names, but we could use another one to store their X position at a given time, a third one for their Y position, etc...
Why copy-trees are important: synchronized trees
The trees you initialize this way - copying the structure of a mother tree and filling its content with some default value - have a very nice property: they are synchronized.
A specific node in the mother tree has the same index than a node in a synchronized tree. You can get both content with the same node index. This property is trivial (if you look at the code, it will jump at you), but it is nonetheless very handy. Of course, this stays valid as long as you do not add or remove any node from one of the tree you want to keep synchronized. The four methods that can mess with synchronization are quite logically:
- adddnode
- removenode
- graft
- chop
In the above paragraph we mentioned that we wish to use several trees to store different properties for a common object (rather than a single tree that holds everything), and this is what allows it. When we will meet iteration, it will prove elegant as well.
If you want to know if two trees are 'synchronized', use the issync method:
zeroTree.issync(oneTree)
ans =
1
oneTree = oneTree.addnode(9, 'intrusion');
zeroTree.issync(oneTree)
ans =
0
Back to main page.