30.22.1.1. General Trees¶

C1

C2

C3

V

P

R

S1

S2

Children of V

Subtree rooted at V

Siblings of V

Ancestors of V

Root

Parent of V

30.22.1.2. General Tree ADT¶

// General tree node ADT
interface GTNode {
  Object value();
  boolean isLeaf();
  GTNode parent();
  GTNode leftmostChild();
  GTNode rightSibling();
  void setValue(Object value);
  void setParent(GTNode par);
  void insertFirst(GTNode n);
  void insertNext(GTNode n);
  void removeFirst();
  void removeNext();
}

// General tree ADT
interface GenTree {
  void clear();      // Clear the tree
  GTNode root();     // Return the root
  // Make the tree have a new root, give first child and sib
  void newroot(Object value, GTNode first, GTNode sib);
  void newleftchild(E value); // Add left child
}

30.22.1.3. General Tree Traversal¶

1 / 41 Settings

<<<>>>

Preorder traversals start by processing the root node.

R

A

B

C

D

E

F

rt

Saving...
Server Error
Resubmit

30.22.1.4. Rep: Lists of Children¶

30.22.1.5. Rep: Dynamic Node (Array)¶

30.22.1.6. Rep: Dynamic Node (linked list)¶

30.22.1.7. Rep: Lift-Child/Right-Sibling¶

30.22.1.8. Serialization¶

Serialization is the process of storing an object as a series of bytes.

A sequential tree serialization typically stores the node values as they would be enumerated by a preorder traversal, along with sufficient information to describe the tree's shape.

30.22.1.9. Binary tree serialization¶

0 / 0 Settings

<<<>>>

We begin with the first node in the string 'A' which will be the root node

1. A
2. B
3. /
4. D
5. /
6. /
7. C
8. E
9. G
10. /
11. /
12. /
13. F
14. H
15. /
16. /
17. I
18. /
19. /

A

B

C

D

E

F

G

H

I

Saving...
Server Error
Resubmit

30.22.1.10. Alternate serialization¶

Settings

Saving...
Server Error
Resubmit

30.22.1.11. Bit Vector Serialization¶

Settings

Saving...
Server Error
Resubmit

30.22.1.12. General Tree Serialization¶

Settings

Saving...
Server Error
Resubmit