Binary tree chain to achieve

sponsored links
binaryTree.h
#ifndef LINKEDBINARYTREE_H
#define LINKEDBINARYTREE_H

#include<iostream>
using namespace std;

template<typename T>
class BinTreeNode{
public:
    T data;
    BinTreeNode<T> *leftChild,*rightChild;
    BinTreeNode():leftChild(NULL),rightChild(NULL){}
    BinTreeNode(T x,BinTreeNode<T> *l=NULL,BinTreeNode<T>*r=NULL)
        :data(x),leftChild(l),rightChild(r){}
};

template<typename T>
class BinaryTree{
public:
    BinaryTree():root(NULL){}
    BinaryTree(T value):RefValue(value),root(NULL){}
    BinaryTree(BinaryTree<T>& s);
    ~BinaryTree(){destroy(root);}
    bool IsEmpty(){
        return root==NULL?true:false;
    }
    BinTreeNode<T> *Parent(BinTreeNode<T>* current){
        return (root==NULL||root==current)?
                    NULL:Parent(root,current);
    }
    BinTreeNode<T> *LeftChild(BinTreeNode<T>* current){
        return current!=NULL?current->leftChild:NULL;
    }
    BinTreeNode<T> *rightChild(BinTreeNode<T>* current){
        return current!=NULL?current->rightChild:NULL;
    }
    int Height(){
        return Height(root);
    }
    int Size(){
        return Size(root);
    }
    BinTreeNode<T> *getRoot()const{
        return root;
    }
    void preOrder(void(* visit)(BinTreeNode<T> *p)){
        preOrder(root,visit);
    }
    void inOrder(void(* visit)(BinTreeNode<T> *p)){
        inOrder(root,visit);
    }
    void postOrder(void(* visit)(BinTreeNode<T> *p)){
        postOrder(root,visit);
    }
    void levelOrder(void(* visit)(BinTreeNode<T> *p));
    int Insert(const T& item);
    BinTreeNode<T> *Find(T& item)const;
protected:
    BinTreeNode<T> *root;
    T RefValue;// Data entry stop signs 
    void createBinTree(istream& in,BinTreeNode<T>*& subTree);
    bool Insert(BinTreeNode<T> *& subTree,const T& x);
    void destroy(BinTreeNode<T> *& subTree);
    bool Find(BinTreeNode<T> * subTree,const T& x)const;
    BinTreeNode<T> *Copy(BinTreeNode<T> *orignode);
    int Height(BinTreeNode<T> *subTree)const;
    int Size(BinTreeNode<T> *subTree)const;
    BinTreeNode<T> *Parent(BinTreeNode<T>* subTree,
                           BinTreeNode<T>* current);
    //BinTreeNode<T> *Find(BinTreeNode<T>* subTree,const T& x)const;
    void Traverse(BinTreeNode<T> *subTree,ostream& out);
    void preOrder(BinTreeNode<T>& subTree,
                  void (*visit)(BinTreeNode<T> *p));
    void inOrder(BinTreeNode<T>& subTree,
                 void (*visit)(BinTreeNode<T> *p));
    void postOrder(BinTreeNode<T>& Tree,
                   void (*visit)(BinTreeNode<T> *p));
    friend istream& operator>>(istream& in,BinaryTree<T>& Tree);
    friend ostream& operator<<(ostream& out,BinaryTree<T>& Tree){
        out << "preOrder" << endl;
        Tree.Traverse(Tree.root,out);
        out << endl;
        return out;
    }
};

#endif // LINKEDBINARYTREE_H


binaryTree.cpp
#include"LinkedBinaryTree.h"
#include<iostream>
#include<stdlib.h>
#include"../T3/Stack.h"
using namespace std;

template<typename T>
void BinaryTree<T>::destroy(BinTreeNode<T> *&subTree)
{
    if(subTree!=NULL){
        destroy(subTree->leftChild);// Recursive delete NewNode 
        destroy(subTree->rightChild);// Recursive delete right subtree 
        delete subTree;
    }
}

/*
   Down from the subTree search current Parent nodes 
  */
template<typename T>
BinTreeNode<T>*
BinaryTree<T>::Parent(BinTreeNode<T> *subTree, BinTreeNode<T> *current)
{
    if(subTree==NULL)
        return NULL;
    if(subTree->leftChild||subTree->rightChild==current)
        return subTree;
    BinTreeNode<T> *p;
    if((p=Parent(subTree->leftChild,current))!=NULL)
        return p;
    else
        return Parent(subTree->rightChild,current);
}

template<typename T>
void BinaryTree<T>::Traverse(BinTreeNode<T> *subTree, ostream &out)
{
    if(subTree!=NULL){
        out << subTree->data << ",";
        Traverse(subTree->leftChild,out);
        Traverse(subTree->rightChild,out);
    }
}

template<typename T>
void BinaryTree<T>::createBinTree(istream &in, BinTreeNode<T> *&subTree)
{
    Stack<BinTreeNode<char>*> s;
    subTree = NULL;
    BinTreeNode<char> *p,*t;
    int k;
    char ch;
    in >> ch;
    while(ch!=RefValue){
        switch(ch){
        case '(':
            s.Push(p);
            k=1;
            break;
        case ')':
            s.Pop(t);
            break;
        case ',':
            k=2;
            break;
        default:
            p=new BinTreeNode<char>(ch);
            if(subTree==NULL)
                subTree=p;
            else if(k==1){
                s.getTop(t);
                t->leftChild=p;
            }else{
                s.getTop(t);
                t->rightChild=p;
            }
        }
        in>>ch;
    }
}

template<typename T>
void BinaryTree<T>::inOrder(BinTreeNode<T>& subTree,
             void (*visit)(BinTreeNode<T> *p))
{
    if(subTree!=NULL){
        InOrder(subTree->leftChild,visit);
        visit(subTree);
        InOrder(subTree->rightChild,visit);
    }
}

template<typename T>
void BinaryTree<T>::preOrder(BinTreeNode<T>& subTree,
              void (*visit)(BinTreeNode<T> *p))
{
    if(subTree!=NULL){
        visit(subTree);
        PreOrder(subTree->leftChild,visit);
        PreOrder(subTree->rightChild,visit);
    }
}

/*
   Postorder traversal 
  */
template<typename T>
void BinaryTree<T>::postOrder(BinTreeNode<T>& subTree,
               void (*visit)(BinTreeNode<T> *p))
{
    if(subTree!=NULL){
        postOrder(subTree->leftChild,visit);
        postOrder(subTree->rightChild,visit);
        visit(subTree);
    }
}

template<typename T>
int BinaryTree<T>::Size(BinTreeNode<T> *subTree)const
{
    if(subTree==NULL)
        return 0;
    return 1+Size(subTree->leftChild)+Size(subTree->rightChild);
}

template<typename T>
int BinaryTree<T>::Height(BinTreeNode<T> *subTree) const
{
    if(subTree==NULL)
        return 0;
    int leftHeight = Height(subTree->leftChild);
    int rightHeight = Height(subTree->rightChild);
    int height = leftHeight>rightHeight?leftHeight:rightHeight;
    height = height+1;
    return height;
}

template<typename T>
BinTreeNode<T> *BinaryTree<T>::Copy(BinTreeNode<T> *orignode)
{
    if(orignode==NULL)
        return NULL;
    BinTreeNode<T> *temp = new BinTreeNode<T>;
    temp->data = orignode->data;
    temp->leftChild = Copy(orignode->leftChild);
    temp->rightChild = Copy(orignode->rightChild);
    return temp;
}

template<typename T>
BinaryTree<T>::BinaryTree(BinaryTree<T> &s)
{
    root = Copy(s.root);
}

//template<typename T>
//void BinaryTree<T>::CreateBinTree(ifstream& in,BinTreeNode<T>*& subTree)
//{
//    T item;
//    if(!in.eof()){
//        in>>item;
//        if(item!=RefValue){
//            subTree = new BinTreeNode<T>(item);
//            assert(subTree!=NULL);
//            CreateBinTree(in,subTree->leftChild);
//            CreateBinTree(in,subTree->rightChild);
//        }else{
//            subTree=NULL;
//        }
//    }
//}

template<typename T>
void PrintBTree(BinTreeNode<T> *BT)
{
    if(BT!=NULL){
        cout << BT->data;
        if(BT->leftChild!=NULL||BT->rightChild!=NULL){
            cout << '(';
            PrintBTree(BT->leftChild);
            cout << ',';
            if(BT->rightChild!=NULL)
                PrintBTree(BT->rightChild);
            cout << ')';
        }
    }
}

  • del.icio.us
  • StumbleUpon
  • Digg
  • TwitThis
  • Mixx
  • Technorati
  • Facebook
  • NewsVine
  • Reddit
  • Google
  • LinkedIn
  • YahooMyWeb

Related Posts of Binary tree chain to achieve

  • Hibernate primary key strategy-sequence

    Today, the use of hibernate in the company encountered a troublesome problem, the use of hibernate when the primary key generation strategy set sequence, but always reported in the implementation could not get next sequence value of the error, then o ...

  • hibernate call stored procedure

    hibernate call stored procedure

  • hibernate using c3p0 connection pooling

    Private http://www.lifevv.com/tenyo/doc/20070605102040991.html c3p0 for open source's JDBC connection pool, with the release hibernate. This article describes how to use the hibernate configuration in c3p0. c3p0 connection pool configuration is v ...

  • Hibernate configuration parameters hibernate.hbm2ddl.auto

    Hibernate in the configuration file: <properties> <property name="hibernate.hbm2ddl.auto" value="create" /> </ properties> Parameter Description: validate load hibernate, the authentication to create a database t ...

  • Build flex + spring + blazeds + hibernate application

    Build flex + spring + blazeds + hibernate application First, set up the project blazeds 1, will blazeds.war extract to a directory, such as: myflex /; 2, set up java works were such as: MyFlex, in the orientation of selection create project from exis ...

  • Hibernate connection pool configuration

    Hibernate connection pool configuration <! - Jdbc -> <property name="connection.driver_class"> oracle.jdbc.driver.OracleDriver </ property> <property name="connection.url"> jdbc: oracle: thin: @ 10.203.14.132:15

  • hibernate generic generic DAO

    package org.lzpeng.dao; import java.io.Serializable; import java.util.List; import org.hibernate.Criteria; import org.hibernate.Query; import org.hibernate.criterion.Criterion; import org.springside.modules.orm.hibernate.Page; /** * * @version 2009-1-10 *

  • Struts2 + hibernate + spring problem user log in

    dao layer services layer action jsp <tr> <td align="center"> <b> user name: </ b> </ td> <td> <s: textfield name = "czyNumber" cssClass = "textstyle" theme = "simple" size = &q

  • Hibernate secondary cache

    Hibernate cache: 2-bit cache, also known as process-level cache or SessionFactory level cache, secondary cache can be shared by all of the session Cache configuration and the use of: Will echcache.xml (the document code in hibernate package directory ...

  • Hibernate's lazy strategy

    hibernate Lazy strategy can be used in: <class> tag, it can be true / false Tags can <PROPERTY> values true / false type of necessary tools to enhance <set> <list> can tag values true / false / extra <many-to-one> <on ...

blog comments powered by Disqus
Recent
Recent Entries
Tag Cloud
Random Entries