Binary Tree Serialization

basic definition

// BinaryTree.java
public class BinaryTree {
  private Node root;
 
  private static class Node {
    Node left;
    Node right;
    int data;
 
    Node(int newData) {
      left = null;
      right = null;
      data = newData;
    }
  }
 
  public void BinaryTree() {
    root = null;
  }
 
  public boolean lookup(int data) {
    return(lookup(root, data));
  }
 
  private boolean lookup(Node node, int data) {
    if (node==null) {
      return(false);
    }
 
    if (data==node.data) {
      return(true);
    }
    else if (data<node.data) {
      return(lookup(node.left, data));
    }
    else {
      return(lookup(node.right, data));
    }
  }
 
  public void insert(int data) {
    root = insert(root, data);
  }
 
  private Node insert(Node node, int data) {
    if (node==null) {
      node = new Node(data);
    }
    else {
      if (data <= node.data) {
        node.left = insert(node.left, data);
      }
      else {
        node.right = insert(node.right, data);
      }
    }
 
    return(node); // in any case, return the new pointer to the caller
  }

min/max

Node maxHelper(Node current) {
    if (current == null) return null;
 
    while (current.right != null)
        current =  current.right;
    return current;
}
 
Node minHelper(Node current) {
    if (current == null) return null;
 
    while (current.left != null)
        current =  current.left;
    return current;
}

predecessor in in-order

  • If the element has a left node, then the max element in the left sub tree (which is the right most element) will be predecessor.
  • If the element doesn’t have a left node, then repeat to check whether it has a parent node and also verify whether this element is the left node for its parent.
public Comparable predecessor(Node node) {
    if (node.left != null) return  maxHelper(node.left);
 
    Node parent = node.parent;
/*
    or a different checking approach
    while (parent != null && parent.data > node.value ) {
      parent = parent.parent;
    }
*/
 
    while (parent != null && parent.left == node ) {
      node = parent;
      parent = parent.parent;
    }
 
    return parent;
}

successor in in-order

  • If the element has a right node, then the min element in the right sub tree (which is the left most element) will be successor.
  • If the element doesn’t have a right node, then check whether it has a parent node and also verify whether this element is the right node for its parent.
int successor(Node node) {
    if (node == null) return null;
 
    // min of right subtree
    if (node.right != null) return minHelper(node.right);
 
    // ancestor of node without right subtree
    Node parent = node.parent;
 
    while (parent  != null && parent.right == node) {
        node = parent;
        parent = parent.parent;
    }
 
    return parent;
}

delete

1. Find the node to be removed. If no such node exists, terminate.

2. (1) if (the node to be removed is a leaf)

delete the node.

(2) else if (the target node has no left child)

put right child 's value and sub-links into target node;

(3) else if (the target node has no right child)

put left child 's value and sub-links into target node;

(4) else // the target node has two children.

Replace the target node's data portion with that of its successor, which is the minimum node of the target node's right subtree. Then delete the successor, to which case (1)
or case (2) must apply.

protected Node removeHelper(Node current, Node target) {
    if (current == null) return null;
    if (target.data < current.node ) 
          current.left = removeHelper(current.left, target);
    else if (target.data > current.data) 
          current.right = removeHelper(current.right, target);
    else {
        if (current.isLeaf()) {
            return null;
        }
        if (current.left == null && current.right != null) {
            Node right =  current.right;
            current.data = right.data;
            current.left = right.left;
            current.right = right.right;
 
            right.left=right.right=null;  //release it 
        } else if (current.right == null && current.left != null) {
            Node left =  current.left;
            current.data = left.data;
            current.left = left.left;
            current.right = left.right;
 
            left.left=left.right=null;  //release it
        } else {
            Node p =  current.right;
            if (p.isLeaf()) {
               current.data = p.data;
               current.right = null;  
            } else if (p.left == null) {
               current.data = p.data;
               current.right = p.right;
 
               p.right = null;  // release p
            } else {
               while (p.leftChild != null) {
                  p =  p.leftChild;
              }
 
              current.data = p.data;
              removeHelper( current.right, p);
           }
        }
 
    }
    return current;
}

save & store a BST into a file

save a binary tree into a file.

void writeBinaryTree(Node p, OutputStream out) {
  if (p == null) {
    out.write("#");
  } else {
    out.write(p.data);
    writeBinaryTree(p.left, out);
    writeBinaryTree(p.right, out);
  }
}
 
private class CurrentPosition {
    int index;
    public CurrentPosition() {  index = 0; }
    public void advance() { index++; }
    public int value(){ return index; }
}
 
public void readBinaryTree(StringBuffer in) {
    root = readBinaryTree(in, new CurrentPosition());  
}
 
/*
Since we have two child nodes for every nodes, so index will never out of boundary
*/
Node readBinaryTree(StringBuffer in , CurrentPosition index) {
    char c = in .charAt(index.value());
    index.advance();
 
    if (c == '#') {
        return null;
    } else {
        Node p = new Node(c - '0');
        p.left = readBinaryTree( in , index);
        p.right = readBinaryTree( in , index);
 
        return p;
    }
}
Add a New Comment
or Sign in as Wikidot user
(will not be published)
- +
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License