Binary tree chain to achieve

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 << ')';
        }
    }
}
分类:CPP 时间:2011-05-31 人气:200
分享到:
blog comments powered by Disqus

相关文章

  • 随机数生成算法的C++实现 2010-04-11

    头文件: /* * Copyright (c) 2008-2011 Zhang Ming (M. Zhang), zmjerry@163.com * * This program is free software; you can redistribute it and/or modify it * under the terms of the GNU General Public License as published by the * Free Software Foundation, e

  • boost源码剖析之:泛型编程精灵type_traits(rev#2) 2014-06-08

    动机 使用traits的动机一般有三种,分派.效率.使某些代码通过编译. 分派 下面有一个模板函数,假设一个动物收容组织提供了它,他们接受所有无家可归的可怜的小动物,于是他们向外界提供了一个函数接受注册.函数看起来像这样: template<class T> // T表示接受的是何种动物 void AcceptAnimals(T animal) { ... //do something }; 但是,如果他们想将猫和狗分开处理(毕竟饲养一只猫和饲养一只狗并不相同.他们可能会为狗买一根链子,而温顺

  • C++中const修饰二级指针(从类型'int**'到类型'const int**'的转换无效) 2013-04-17

    先上代码: void func(const int ** arg) { } int main(int argc, char **argv) { int **p; func(p); return 0; } 这个代码用gcc编译会出现这样的错误: main.cpp: 在函数'int main(int, char**)'中: main.cpp:8:8: 错误: 从类型'int**'到类型'const int**'的转换无效 [-fpermissive] main.cpp:1:6: 错误: 初始化'vo

  • Understanding of the const 2010-03-09

    const for many people both strange and familiar. The problem can be very difficult in some places difficult to understand. I am just learning C at the right time to understand it is very vague. Seems a little understanding, but can not give you why t

  • Android Developer notes 4: DisplayMetrics class, how to get screen width and height 2010-06-28

    Classes for facilities with DisplayMetrics screen width and height of code: package com.andy.android; import android.app.Activity; import android.os.Bundle; import android.util.DisplayMetrics; import android.widget.TextView; /** * DisplayMetrics Simp

  • Find all nodes in a layer binary tree and find the height of binary tree 2010-11-10

    1, the output binary tree all nodes on a layer, usually recursive manner. 2, find the height of binary tree, but also with recursive manner. /* How to print a binary tree a layer of all nodes ? How to find the binary tree height ? */ #include <stdio.

  • C language const keyword 2011-01-04

    Const C language has been a pain in the hearts of C language for beginners, because const has different effects in different locations, have different roles in different scenarios. This allows beginners lost in the mind. Today, with everyone study co

  • Words of C language const 2011-05-12

    const in the C language, be regarded as a relatively new descriptors, we call the constant modifier, which means that the object of their modified constant (immutable). Let's look at the syntax of Points in how it is used. 1, the function of the body

  • Get screen width and screen height and determine if they had 2011-06-01

    void f () { Display display = ((WindowManager) getSystemService (WINDOW_SERVICE)). GetDefaultDisplay (); int width = display.getWidth (); int height = display.getHeight (); int orientation = display.getOrientation (); switch (orientation) { case Conf

  • java upload pictures at the same time get the picture width and height 2011-09-16

    public ActionForward upload(ActionMapping mapping, ActionForm form, HttpServletRequest request, HttpServletResponse response) throws IOException { FileForm fileForm = (FileForm) form; FormFile file1 = fileForm.getFile1(); HashMap<String, Object> jso

iOS 开发

Android 开发

Python 开发

JAVA 开发

开发语言

PHP 开发

Ruby 开发

搜索

前端开发

数据库

开发工具

开放平台

Javascript 开发

.NET 开发

云计算

服务器

Copyright (C) codeweblog.com, All Rights Reserved.

CodeWeblog.com 版权所有 黔ICP备15002463号-1

processed in 0.146 (s). 12 q(s)