Tree

---

binary search tree, children on the left < x < children on right side
insertion and search complexity O(logN) delete is complicated.
illustration http://www.cs.mcgill.ca/~cs251/OldCourses/1997/topic9/

java code refer : http://www.cs.mcgill.ca/~cs251/OldCourses/1997/topic9/
c++ code refer: http://en.literateprograms.org/Binary_search_tree_(C)

hashing: http://www.cs.mcgill.ca/~cs251/OldCourses/1997/topic12/

One advantage balanced binary search trees have over hash tables is that they also retain a relative ordering among their contents. While the other operations aren't quite as fast as a hash table (refer to the table below), logarithmic time is certainly not bad by any means. However, if you're not interested in the ordering of its items or frequent iterating, a hash table is certainly the way to go.

http://horizon.ece.utexas.edu/~jacome/ee360cN/lectures/
balanced tree : http://www.cs.mcgill.ca/~cs251/OldCourses/1997/topic19/

tree

http://www.mathcs.duq.edu/drozdek/DSinCpp/genBST.h
http://hi.baidu.com/hbmubai/blog/item/0f7712019ea809d1277fb5f3.html

preorder recrusive or not

public void iterativePreorder() {
        BSTNode<E> p = root;
        Stack<BSTNode<E>> stack = new Stack<BSTNode<E>>();
        if (p != null) {
            stack.push(p);

            while (!stack.isEmpty()) {
                p = (BSTNode<E>) stack.pop();
                visit(p);
                if (p.right != null)
                    stack.push(p.right);
                if (p.left != null)
                    stack.push(p.left);
            }
        }
    }

inorder non recursive

public void iterativeInorder() {
        BSTNode<E> p = root;
        Stack<BSTNode<E>> stack = new Stack<BSTNode<E>>();
        while (p != null) {
 
            while (p != null) {
                if (p.right != null)    stack.push(p.right);
                stack.push(p);
                p = p.left;
            }
 
            p = (BSTNode<E>) stack.pop();
            while (!stack.isEmpty() && p.right == null) {
                visit(p);
                p = (BSTNode<E>) stack.pop();
            }
            visit(p);
            if (!stack.isEmpty()) {
                p = (BSTNode<E>) stack.pop();
            } else {
                p = null;
            }
        }
    }

iterative post order

approach -1

// left-to-right postorder = right-to-left preorder

public void iterativePostorder() { 
    IntBSTNode p = root; 
    Stack travStack = new Stack(); //trace用堆疊
    output = new Stack(); //結果堆疊

    if (p != null) { // left-to-right postorder = right-to-left preorder   LRV
        travStack.push(p); 

        while (!travStack.isEmpty()) {
            p = (IntBSTNode) travStack.pop(); 
            output.push(p); 

            if (p.left != null) travStack.push(p.left); 
            if (p.right != null) travStack.push(p.right); 
         } //while

         while (!output.isEmpty()) { 
            p = (IntBSTNode) output.pop(); 
            p.visit(); 
         } 
    } //if
}

approach 2:

public void iterativePostorder() {
        BSTNode<E> p = root, q = root;
        Stack<BSTNode<E>> stack = new Stack<BSTNode<E>>();
        while (p != null) {
            while (p.left != null{
                stack.push(p);
                p = p.left;
            }

            while (p != null && (p.right == null || p.right == q)) {
                visit(p);
                q = p;
                if (stack.isEmpty())
                    return;
                p = (BSTNode<E>) stack.pop();
            }
            stack.push(p);
            p = p.right;
        }
    }

misc

• 一對中序順序(inorder sequence)及前序順序(preorder sequence)可唯一決定一個二元樹。
• 一對中序順序(inorder sequence)及後序順序(postorder sequence)亦可唯一決定一個二元樹。
• 一對前序順序(preorder sequence)及後序順序(postorder sequence)無法決定唯一一個二元樹

有一個前序順序為：ABCDEFGHI 中序順序為：BCAEDGHFI 則其相對應的二元樹為何？
解：前序追蹤的第一個字元A一定是樹根，再從中序追蹤知在A之前的節點BC是左子樹，在A之後的節點EDGHFI是右子樹，由此我們可以大略的建立出其相對應的二元樹形狀。
再由前序追蹤的第二個字元B知其為樹根，從中序追蹤知B的左子樹是空的，右子樹是C，因此其進一步結果如下
http://www.google.com/url?sa=t&source=web&ct=res&cd=9&url=http%3A%2F%2Ftmue.edu.tw%2F~lai%2Faf-teach%2Faf-algorithm-DS%2FDSinjava%2FDS-Trees.ppt&ei=Zb6dSo_nOJ6-tAOhvODaBg&rct=j&q=iterativepostorder+bst&usg=AFQjCNFb5ZLU6wt3rrxX_ymcJ8gJRQABHQ

breadth traversal

void Tree::LevelOrder()
{
      Queue Q;
      TreeNode *currentNode = root;
      while (currentNode)
      {
              Visit(currentNode);
              if (currentNode->leftChild)      Q.Push(currentNode->leftChild);
              if (currentNode->rightChild)   Q.Push(currentNode->rightChild);
              if (Q.IsEmpty())   return;       
              currentNode = Q.Pull();
       }
}

insert

void BinarySearchTree::insert(int d)
{
    tree_node* t = new tree_node;
    tree_node* parent;
 
    t->data = d;
    t->left = NULL;
    t->right = NULL;
 
    parent = NULL;
 
  // is this a new tree?
  if(isEmpty()){
      root = t;
  } 
  else
  {
    //Note: ALL insertions are as leaf nodes
    tree_node* curr = root;
 
    while(curr)
    {
        parent = curr;
        if(t->data > curr->data) curr = curr->right;
        else curr = curr->left;
    }
 
    if(t->data < parent->data)
       parent->left = t;
    else
       parent->right = t;
  }
}

struct node* insert(struct node* node, int data) {
  // 1. If the tree is empty, return a new, single node
  if (node == NULL) {
    return(newNode(data));
  }
  else {
    // 2. Otherwise, recur down the tree
    if (data <= node->data) node->left = insert(node->left, data);
    else node->right = insert(node->right, data);
 
    return(node); // return the (unchanged) node pointer
  }
}

delete

Tree-Delete(T, z)
/* Determine which node to splice out: either z or z’s successor. */
 if left[z] = NIL or right[z] = NIL
     then y = z
     else y = Tree-Successor[z]
 
/* Get x as descendant of y. */
if  left[y] != NIL
      then x = left[y] 
      else x = right[y]
 
/* y is removed from the tree by manipulating pointers of  p[y] and x */
if x != NIL
    then p[x] = p[y]
 
 if p[y] = NIL
     then root[T] = x
     else if  y = left[p[i]]
            then left[p[y]] = x
            else right[p[y]] = x
 
/* copy y's data into z and delete y*/
if y != z 
     then  key[z] = key[y]
               copy y’s data into z.
 
delete y;

other_versions

precedendor

successor

Tree-Successor(x)
1.  if right[x] != NIL 
2.          then return Tree-Minimum(right[x]) 
3.     y = p[x] 
4.     while y != NIL and x = right[y]
5.     do x = y
6.          y = p[y]
7.     return y

version-1 + 2 c code and splice code

min value

int minValue(struct node* node)  
{  
  struct node* current = node;  

  while (current->left != NULL)  
  {  
    current = current->left;  
  } 

  return(current->data);  
}

Write C code to check if a given binary tree is a binary search tree or not?

int isThisABST(struct node* mynode)  
{  
    if (mynode==NULL) return(true);  
    if (node->left!=NULL && maxValue(mynode->left) > mynode->data)  
       return(false); 
    if (node->right!=NULL && minValue(mynode->right) <= mynode->data)  
       return(false);  
    if (!isThisABST(node->left) || !isThisABST(node->right))  
       return(false);  

    return(true);  
}

deepest common ancestor

Find the deepest common ancestor of two leaves in a binary search tree;
Do not traverse from the leaves. Instead, locate the node top/down.
How about finding the shallowest common ancestor of two leaves?

找shallowest的 trivial，就是root。
找deepest的,比较两个叶节点的值，小的p，大的q。从根节点起，当前节点x。

void deepest(node * x)
{
   if(x==null) return;
 
   push_into_queue(x);    
 
   if(x.value> p.value && x.value < q.value)
         return;
    if(x.value> q.value)
       deepest(x->left);
     if(x.value< p.value) 
       deepest(x->right);
}

convert a binary tree into a linked list

struct Tree
{
 int i;
 struct Tree* left;
 struct Tree* right;
};
Tree * Convert_to_list (Tree* T)
{
Tree * T1, T2, temp;
if (T != NULL)
{
   T1 = Convert_to_list(T->left)
   T2 = Convert_to_list(T->right)
   T->right = T2;
   if (T1!= NULL)
   {
     temp = T1;
     while (temp->right)
        temp = temp->right;
     temp->right = T;
     return T1;
   }
   else
     return T;
}
else
   return NULL;
}

Threaded Tree

insert

public void threadedInsert(int el) {
IntThreadedNode newNode = new IntThreadedNode(el);
If (root == null) {    // tree is empty
   root = newNode;
   return;}
IntThreadedNode p = root, prev = null;
while (p != null) {    // find a place to insert newNode;
    prev = p;
   if (el < p.key)
       p = p.left;
   else if (!p.Successor)     // go to the right only if it is
       p = p.right;    // a descendant, not a successor;
   else break;     // don't follow successor link;
 }
 if (el < prev.key) {    // if newNode is left child of
    prev.left = newNode;    // its parent, the parent
    newNode.Successor = true;// also becomes its successor;
    newNode.right = prev;   }
 else if (prev.Successor) {    // if parent of the newNode
    newNode.Successor = true;// is not the rightmost node,
    prev.Successor = false;    // make parent's successor
    newNode.right = prev.right;    // newNode’s successor,
    prev.right = newNode;}
 else prev.right = newNode;    // otherwise it has no successory;
} //

inorder

protected void threadedInorder( ) {
  IntThreadedNode prev, p = root;

  if (p != null) {    //process only nonempty trees;
    while (p.left != null)    // go to the leftmost node;
              p = p.left;

    while (p !=null) {
            p.visit( );
            prev = p;
            p = p.right;    //go to the right node

           if (p != null && !prev.successor) // if it is a descendant,go to the leftmost node,
                    while (p.left != null)    p = p.left;    
   }// while (p !=null) 
 } // if 
}