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

相关文章

  • 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

  • C++类中的static和const用法实例教程 2014-02-10

    这篇文章主要介绍了C++类中的static和const用法,是C++面向对象程序设计中非常重要的概念,需要的朋友可以参考下 static和const是C++程序设计中非常重要的概念,本文实例列举了C++类中的static和const的规则和用法.供大家参考借鉴.具体说明如下: 首先以代码用来举例说明.示例代码如下: class A { public: A():m(10) //const成员必须在构造函数的初始化构造列表中初始化 { q = 40; } void fun1()const { m++

  • C语言 volatile与const同时使用应注意的问题 2014-09-12

    "volatile"的含义是"请不要做没谱的优化,这个值可能变掉的",而并非"你可以修改这个值".因此,它们本来就不是矛盾的 const和volatile放在一起的意义在于: (1)本程序段中不能对a作修改,任何修改都是非法的,或者至少是粗心,编译器应该报错,防止这种粗心: (2)另一个程序段则完全有可能修改,因此编译器最好不要做太激进的优化. "const"含义是"请做为常量使用",而并非"放心

  • The basic concepts of binary tree 2011-05-30

    A binary tree nodes of a finite set: the set or is empty, or by a root node with two sub-trees are called the left and right sub-tree, binary tree composed of disjoint . Related Properties: 1. In the binary tree section i (i> = 1) layer up to 2 i-1 p

iOS 开发

Android 开发

Python 开发

JAVA 开发

开发语言

PHP 开发

Ruby 开发

搜索

前端开发

数据库

开发工具

开放平台

Javascript 开发

.NET 开发

云计算

服务器

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

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

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