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; } }
Post preview:
Close preview