12.General Trees§

Created with Raphaël 2.1.2
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

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
}

General Tree Traversal

1 / 41 Settings
<<<>>>

Preorder traversals start by processing the root node.

Created with Raphaël 2.1.2
  • // 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();
  • }
  • }
  • }
Created with Raphaël 2.1.2
R
A
B
C
D
E
F
rt
Proficient Saving... Error Saving
Server Error
Resubmit

Rep: Lists of Children

The "list of children" implementation for general trees.

Rep: Dynamic Node (Array)

A dynamic general tree with fixed-size arrays

Rep: Dynamic Node (linked list)

A dynamic general tree with linked lists of child pointers

Rep: Left-Child/Right-Sibling

Converting from a forest of general trees to a binary tree

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.

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. /
Created with Raphaël 2.1.2
A
Proficient Saving... Error Saving
Server Error
Resubmit

Alternate serialization

0 / 0 Settings
<<<>>>

The first character A' means A is an internal node, and is the root node

  1. A'
  2. B'
  3. /
  4. D
  5. C'
  6. E'
  7. G
  8. /
  9. F'
  10. H
  11. I
Created with Raphaël 2.1.2
A
Proficient Saving... Error Saving
Server Error
Resubmit

Bit Vector Serialization

0 / 0 Settings
<<<>>>

The first character 1 means this is an internal node, and it is the root node

  1. 1
  2. 1
  3. 0
  4. 0
  5. 1
  6. 1
  7. 0
  8. 0
  9. 1
  10. 0
  11. 0
Created with Raphaël 2.1.2
1
Proficient Saving... Error Saving
Server Error
Resubmit

General Tree Serialization

1 / 16 Settings
<<<>>>

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

Created with Raphaël 2.1.2
  1. R
  2. A
  3. C
  4. )
  5. D
  6. )
  7. E
  8. )
  9. )
  10. B
  11. F
  12. )
  13. )
  14. )
Created with Raphaël 2.1.2
Proficient Saving... Error Saving
Server Error
Resubmit