12.1.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

12.1.1.2. General Tree ADT¶

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

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

12.1.1.3. General Tree Traversal¶

1 / 41 Settings

<<<>>>

Preorder traversals start by processing the root node.

• // Preorder traversal for general trees
• static void preorder(GTNode rt) {
• PrintNode(rt);
• if (!rt.isLeaf()) {
• GTNode temp = rt.leftmostChild();
• while (temp != null) {
• preorder(temp);
• temp = temp.rightSibling();
• }
• }
• }

R

A

B

C

D

E

F

rt

Saving...
Server Error
Resubmit

12.1.1.4. Rep: Lists of Children¶

12.1.1.5. Rep: Dynamic Node (Array)¶

12.1.1.6. Rep: Dynamic Node (linked list)¶

12.1.1.7. Rep: Left-Child/Right-Sibling¶

12.1.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.

12.1.1.9. Binary tree serialization¶

1 / 23 Settings

<<<>>>

The sequential representation in the array was generated by a simple preorder traversal. Now we will see how to reconstruct the original tree.

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

rt

Saving...
Server Error
Resubmit

12.1.1.10. Alternate serialization¶

1 / 20 Settings

<<<>>>

The sequential representation in the array was generated by a simple preorder traversal. Now we will see how to reconstruct the original tree.

1. A'
2. B'
3. /
4. D
5. C'
6. E'
7. G
8. /
9. F'
10. H
11. I

A

B

C

D

E

F

G

H

I

rt

Saving...
Server Error
Resubmit

12.1.1.11. Bit Vector Serialization¶

1 / 17 Settings

<<<>>>

The array shows the structure for a full binary tree. A preorder enumeration would go with this to get the values. This visualization shows a reconstruction of the tree shape.

1. 1
2. 1
3. 0
4. 0
5. 1
6. 1
7. 0
8. 0
9. 1
10. 0
11. 0

1

1

1

0

1

1

0

0

0

rt

Saving...
Server Error
Resubmit

12.1.1.12. General Tree Serialization¶

1 / 16 Settings

<<<>>>

We will reconstruct a general tree from the sequential representation shown in the array.

1. R
2. A
3. C
4. )
5. D
6. )
7. E
8. )
9. )
10. B
11. F
12. )
13. )
14. )

R

A

B

C

D

E

F

rt

Saving...
Server Error
Resubmit