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
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
}

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

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

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

Bit Vector Serialization

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

General Tree Serialization

Settings

Proficient Saving... Error Saving
Server Error
Resubmit