数据结构学习(c++)——二叉树

类别:VC语言 点击:0 评论:0 推荐:

注:本文只是对学习清华殷人昆《数据结构(用面向对象方法与c++描述)》的人有些微帮助,其他人就没有必要浪费时间看了。因为老实说这本书里的代码实现的确不怎么样。

我的目的,就是努力实现和书里的代码相同的接口,尽最大可能和原代码一摸一样。因为这样的话,一则自己以后看起来比较方便,只要对着课本翻翻就行了;二则这样可能对别的学这本书的人有一定的好处。由于自己的习惯,我在原书的类名前加了_。

/*
  Name: _BinaryTree.h
  Copyright:
  Author: elmar
  Date: 19-07-03 23:43
  Description:
*/

#ifndef _BinaryTree_H
#define _BinaryTree_H

#include <iostream>
#include <deque>    //用于Insert中的层次遍历
using namespace std;

template <class Type> class _BinaryTree;
template <class Type> class _BinTreeNode
{
    friend class _BinaryTree<Type>;
   
    public:
        _BinTreeNode():data(Type()), leftChild(NULL), rightChild(NULL){}
        _BinTreeNode(Type item,
                     _BinTreeNode<Type>* left = NULL,
                     _BinTreeNode<Type>* right = NULL);
        _BinTreeNode(const _BinTreeNode<Type>& b){*this = b;}
        Type GetData() const {return data;}
        _BinTreeNode<Type>* GetLeft() const {return leftChild;}
        _BinTreeNode<Type>* GetRight() const {return rightChild;}
        void SetData(const Type& item) {data = item;}
        void SetLeft(_BinTreeNode<Type>* L) {leftChild = L;}
        void SetRight(_BinTreeNode<Type>* R) {rightChild = R;}
        _BinTreeNode<Type>& operator = (const _BinTreeNode<Type>& b);
       
    private:
        _BinTreeNode<Type> *leftChild, *rightChild;
        Type data;
};

template <class Type> class _BinaryTree
{
    public:
        _BinaryTree(): root(NULL){}
        _BinaryTree(Type value): RefValue(value), root(NULL){}
        _BinaryTree(const _BinaryTree<Type>& bt);
        virtual ~_BinaryTree(){destroy(root);}
        virtual bool IsEmpty() {return root == NULL ? true : false;}
        virtual _BinTreeNode<Type>* Parent(_BinTreeNode<Type>* current)
                {return root == NULL || root == current ? NULL : Parent(root, current);}
        virtual _BinTreeNode<Type>* LeftChild(_BinTreeNode<Type>* current)
                {return root != NULL ? current->leftChild : NULL;}
        virtual _BinTreeNode<Type>* RightChild(_BinTreeNode<Type>* current)
                {return root != NULL ? current->rightChild : NULL;}
        virtual int Insert(const Type& item){return Insert(root, item);}
//        virtual int Find(const Type& item) const;
        const _BinTreeNode<Type>* GetRoot() const {return root;}
        _BinaryTree<Type>& operator = (const _BinaryTree<Type>&);
        _BinaryTree<Type>& operator += (const _BinaryTree<Type>& bt){return Append(bt);}
        friend istream& operator >> (istream& in, _BinaryTree<Type>& Tree)
        {
            Type item;
            cout << "Construct binary tree: " << endl;
            cout << "Input data (end with " << Tree.RefValue <<" ):";
            in >> item;
            while (item != Tree.RefValue)
            {
                Tree.Insert(item);
                cout << "Input data (end with " << Tree.RefValue <<" ):";
                in >> item;
            }
            return in;
        }       
               
        friend ostream& operator << (ostream& out, _BinaryTree<Type>& Tree)
        {
            out << "Preorder traversal of binary tree." << endl;
            Tree.Traverse(Tree.root, out);
            out << endl;
            return out;
        }       
   
    private:
        _BinTreeNode<Type>* root;                   //二叉数的根指针
        Type RefValue;                              //数据输入停止的标志
       
        _BinTreeNode<Type>* Parent(_BinTreeNode<Type>* start, _BinTreeNode<Type>* current);
        int Insert(_BinTreeNode<Type>*& current, const Type& item); //操作成功返回0,否则-1
        void Traverse(_BinTreeNode<Type>* current, ostream& out) const; //输出根为current的二叉树
//        int Find(_BinTreeNode<Type>* current, const Type& item) const;
        void destroy(_BinTreeNode<Type>* current);
        _BinaryTree<Type>& Append(const _BinaryTree<Type>& bt);   //为elmar所加的函数。把二叉树bt加到当前树上
};

template <class Type> _BinTreeNode<Type>::_BinTreeNode(Type item,
                                         _BinTreeNode<Type>* left,
                                         _BinTreeNode<Type>* right)
{
    data = item;
    leftChild = left;
    rightChild = right;
}

template <class Type> _BinTreeNode<Type>& _BinTreeNode<Type>::operator = (const _BinTreeNode<Type>& b)
{
    leftChild = b.leftChild; rightChild = b.rightChild; data = b.data;
    return *this;
}

template <class Type> _BinaryTree<Type>::_BinaryTree(const _BinaryTree<Type>& bt)
{
    root = NULL;
    RefValue = bt.RefValue;
    Append(bt);
}

template <class Type> void _BinaryTree<Type>::destroy(_BinTreeNode<Type>* current)
{
    if (current !=NULL)
    {
        destroy(current->leftChild);
        destroy(current->rightChild);
        delete current;
    }
}

template <class Type> _BinTreeNode<Type>*
_BinaryTree<Type>::Parent(_BinTreeNode<Type>* start, _BinTreeNode<Type>* current)
{
    if (start == NULL) return NULL;
    if (start->leftChild == current || start->rightChild == current) return start;
    _BinTreeNode<Type>* p;
    if ((p = Parent(start->leftChild, current)) != NULL) return p;
    else return Parent(start->rightChild, current);
}

template <class Type> void
_BinaryTree<Type>::Traverse(_BinTreeNode<Type>* current, ostream& out) const
{
    if (current != NULL)
    {
        out << current->data << ' ';
        Traverse(current->leftChild, out);
        Traverse(current->rightChild, out);
    }
}

//层次遍历以current为根的二叉树,把item插入在第一个叶子的的左指针,
//或第一个缺右孩子的节点的右指针
template <class Type> int
_BinaryTree<Type>::Insert(_BinTreeNode<Type>*& current, const Type& item)
{
    _BinTreeNode<Type>* p = new _BinTreeNode<Type>(item);
    if (p == NULL) return -1;
   
    if (current == NULL)
    {
        current = p;
        return 0;
    }
    else
    {
        deque<_BinTreeNode<Type>*>* deck = new deque<_BinTreeNode<Type>*>;//队列
        deck->push_back(current);
       
        typename deque<_BinTreeNode<Type>*>::const_iterator iter;
        while (true)
        {
            iter = deck->begin();
            deck->pop_front();
            if ((*iter)->leftChild == NULL)
            {
                (*iter)->leftChild = p;
                delete deck;
                return 0;
            }
            else if ((*iter)->rightChild == NULL)
            {
                (*iter)->rightChild = p;
                delete deck;
                return 0;
            }
            else
            {
                deck->push_back((*iter)->leftChild);
                deck->push_back((*iter)->rightChild);
            }
        }
       
    }
}

template <class Type> _BinaryTree<Type>& _BinaryTree<Type>::Append(const _BinaryTree<Type>& bt)
{
    deque<_BinTreeNode<Type>*>* deck = new deque<_BinTreeNode<Type>*>;
    deck->push_back(bt.root);

    typename deque<_BinTreeNode<Type>*>::const_iterator iter;
    while (!deck->empty())
    {
        iter = deck->begin();
        deck->pop_front();
        this->Insert((*iter)->GetData());
       
        if ((*iter)->leftChild != NULL)
        {
            deck->push_back((*iter)->leftChild);
        }
        if ((*iter)->rightChild != NULL)
        {
            deck->push_back((*iter)->rightChild);
        }

    }//while
   
    delete deck;
    return *this;
}

template <class Type> _BinaryTree<Type>& _BinaryTree<Type>::operator = (const _BinaryTree<Type>& bt)
{
    RefValue = bt.RefValue;
    if (bt.root == NULL) return *this;
   
    if (!this->IsEmpty())this->destroy(root);
   
    return this->Append(bt);
}

#endif

本文地址:http://com.8s8s.com/it/it1589.htm