//Tree.h文件

//Tree.h 文件
#pragma once
#include <list>
#include <algorithm>
using namespace std;

struct TreeNode;   //定義一個(gè)結(jié)構(gòu)體原形
class Tree;        //定義一個(gè)類原形
class Iterator;    //定義一個(gè)類原形
typedef list<TreeNode*> List; //重命名一個(gè)節(jié)點(diǎn)鏈表

TreeNode* clone(TreeNode*, List&, TreeNode*);//Clone復(fù)制函數(shù)

struct TreeNode {
    int _data;                         //數(shù)據(jù)
    TreeNode* _parent;                 //父節(jié)點(diǎn)
    List _children;                    //子節(jié)點(diǎn)
    TreeNode(int, TreeNode* );          //構(gòu)造函數(shù)
    void SetParent(TreeNode& );         //設(shè)置父節(jié)點(diǎn)
    void InsertChildren(TreeNode& );    //插入子節(jié)點(diǎn)
};

class Tree{
public:

    //下面是構(gòu)造器和運(yùn)算符重載
    Tree();                                //默認(rèn)構(gòu)造函數(shù)
    Tree(const Tree&);                     //復(fù)制構(gòu)造函數(shù)
    Tree(const int);                       //帶參數(shù)構(gòu)造函數(shù)
    Tree(const int,const list<Tree*>&);    //帶參數(shù)構(gòu)造函數(shù)
    ~Tree();                               //析構(gòu)函數(shù)
    Tree& operator=(const Tree&);           //=符號(hào)運(yùn)算符重載
    bool operator==(const Tree&);           //==符號(hào)運(yùn)算符重載
    bool operator!=(const Tree&);           //!=符號(hào)運(yùn)算符重載

                                        //下面是成員函數(shù)
    void Clear();                         //清空
    bool IsEmpty()const;                  //判斷是否為空
    int Size()const;                      //計(jì)算節(jié)點(diǎn)數(shù)目
    int Leaves();                         //計(jì)算葉子數(shù)
    int Root()const;                      //返回根元素
    int Height();                         //計(jì)算樹的高度


                                      //下面是靜態(tài)成員函數(shù)
    static bool IsRoot(Iterator);         //判斷是否是根
    static bool isLeaf(Iterator);         //判斷是否是葉子
    static Iterator Parent(Iterator);     //返回其父節(jié)點(diǎn)
    static int NumChildren(Iterator);     //返回其子節(jié)點(diǎn)數(shù)目

                                     //跌代器函數(shù)
    Iterator begin();                //Tree Begin
    Iterator end();                  //Tree End
    friend class Iterator;            //Iterator SubClass
private:
    list<TreeNode*> _nodes;            //節(jié)點(diǎn)數(shù)組
    list<TreeNode*>::iterator LIt;     //一個(gè)節(jié)點(diǎn)迭代器
    int height(TreeNode*);
    int level(TreeNode*,Iterator);
};

//This is TreeSub Class Iterator
class Iterator{
private:
    Tree* _tree;                        //Tree data
    list<TreeNode*>::iterator _lit;     //List Iterator
public:
    Iterator();                                 //默認(rèn)構(gòu)造函數(shù)
    Iterator(const Iterator&);                  //復(fù)制構(gòu)造函數(shù)
    Iterator(Tree*,TreeNode*);                  //構(gòu)造函數(shù)
    Iterator(Tree*,list<TreeNode*>::iterator);  //構(gòu)造函數(shù)
                                                //運(yùn)算符重載
    void operator=(const Iterator&);            //賦值運(yùn)算符重載
    bool operator==(const Iterator&);           //關(guān)系運(yùn)算符重載
    bool operator!=(const Iterator&);           //關(guān)系運(yùn)算符重載
    Iterator& operator++();                     //前綴++運(yùn)算符
    Iterator operator++(int);                   //后綴++運(yùn)算符
    int operator*()const;                       //獲得節(jié)點(diǎn)信息
    bool operator!();                           //賦值運(yùn)算符重載

    typedef list<TreeNode*>::iterator List;
    friend class Tree;
};

//Tree.cpp 文件

#include "stdafx.h"
#include "Tree.h"

//***** 下面是對(duì)于TreeNode結(jié)構(gòu)體的定義實(shí)現(xiàn)*****///

TreeNode::TreeNode(int type = 0, TreeNode* Parent = 0) {
    _data = type;
    _parent = Parent;
}
void TreeNode::SetParent(TreeNode& node) {
    _parent = &node;
}
void TreeNode::InsertChildren(TreeNode& node) {
    TreeNode* p = &node;
    _children.push_back(p);
}



//***** 下面是對(duì)于Tree類的定義實(shí)現(xiàn)*****///
Tree::Tree() {

}

Tree::Tree(const int type) {
    _nodes.push_back(new TreeNode(type));
}

Tree::Tree(const Tree& t) {
    if (t._nodes.empty())return;
    clone(t._nodes.front(), _nodes, 0);
}
Tree::Tree(const int type, const list<Tree*>& lit) {
    TreeNode* root = new TreeNode(type);//建立根節(jié)點(diǎn)
    _nodes.push_back(root);//放入樹中
    list<Tree*>::const_iterator it;
    for (it = lit.begin(); it != lit.end(); it++) {
        if (!((*it)->_nodes.empty())) {//如果當(dāng)前節(jié)點(diǎn)元素不為空
            Tree* tp = new Tree(**it);
            TreeNode* p = tp->_nodes.front();
            root->_children.push_back(p); //設(shè)置根的子節(jié)點(diǎn)
            p->_parent = root;            //設(shè)置節(jié)點(diǎn)的父節(jié)點(diǎn)為根
            list<TreeNode*>::iterator lit1 = tp->_nodes.begin();
            list<TreeNode*>::iterator lit2 = tp->_nodes.end();
            list<TreeNode*>::iterator lit3 = _nodes.end();
            _nodes.insert(lit3, lit1, lit2);
        }
    }
}

Tree::~Tree() {
    for (list<TreeNode*>::iterator it = _nodes.begin(); it != _nodes.end(); it++) {
        delete* it;
    }
}

Tree& Tree::operator =(const Tree & t) {
    Clear();
    Tree* p = new Tree(t);
    _nodes = p->_nodes;
    return *this;
}

bool Tree::operator ==(const Tree& t) {
    if (_nodes.size() != t._nodes.size()) {
        return false;
    }
    list<TreeNode*>::iterator it = _nodes.begin();
    list<TreeNode*>::const_iterator _it = t._nodes.begin();
    while (it != _nodes.end() && _it != t._nodes.end()) {
        if ((*it)->_data != (*_it)->_data) {
            return false;
        }
        it++;
        _it++;
    }
    return true;
}

bool Tree::operator !=(const Tree& t) {
    if (_nodes.size() != _nodes.size()) {
        return true;
    }
    else {
        list<TreeNode*>::iterator it = _nodes.begin();
        list<TreeNode*>::const_iterator _it = t._nodes.begin();
        while (it != _nodes.end() && _it != t._nodes.end()) {
            if ((*it)->_data != (*_it)->_data) {
                return true;
            }
            it++;
            _it++;
        }
        return false;
    }
}

void Tree::Clear() {
    for (list<TreeNode*>::iterator it = _nodes.begin(); it != _nodes.end(); it++) {
        delete* it;
    }
    _nodes.clear();
}

bool Tree::IsEmpty()const {
    return _nodes.empty();
}

int Tree::Size()const {
    return (int)_nodes.size();
}

int Tree::Leaves() {
    int i = 0;
    list<TreeNode*>::iterator it = _nodes.begin();
    while (it != _nodes.end()) {
        if ((*it)->_children.size() == 0) {
            i++;
        }
        it++;
    }
    return i;
}


int Tree::Height() {
    if (_nodes.size() != 0) {
        TreeNode* TNode = _nodes.front();
        return height(TNode);
    }
    else {
        return -1; //判斷為空樹
    }
}

int Tree::height(TreeNode* node) {
    if (!node) {
        return -1;
    }
    else {
        list<TreeNode*> plist = node->_children;
        if (plist.size() == 0) {
            return 0;
        }
        int hA = 0;
        for (list<TreeNode*>::iterator it = plist.begin(); it != plist.end(); it++) {
            int hB = height(*it);
            if (hB>hA) {
                hA = hB;
            }
        }
        return hA + 1;
    }
}


Iterator Tree::begin() {
    return Iterator(this, _nodes.begin());
}

Iterator Tree::end() {
    return Iterator(this, _nodes.end());
}
int Tree::Root()const {
    return (*_nodes.begin())->_data;
}


bool Tree::IsRoot(Iterator it) {
    TreeNode p = *it;
    if (p._parent == 0) {
        return true;
    }
    return false;
}

bool Tree::isLeaf(Iterator it) {
    TreeNode p = *it;
    if (p._children.size() == 0) {
        return true;
    }
    return false;
}

Iterator Tree::Parent(Iterator it) {
    TreeNode p = *it;
    Tree* t = it._tree;
    Iterator Ite(t, p._parent);
    return Ite;
}


int Tree::NumChildren(Iterator it) {
    TreeNode p = *it;
    return (int)p._children.size();
}

//***** 下面是對(duì)于Tree::Iterator類的定義實(shí)現(xiàn)*****///
Iterator::Iterator() {
}

Iterator::Iterator(const Iterator& it) {
    _tree = it._tree;
    _lit = it._lit;
}

Iterator::Iterator(Tree* t, TreeNode* n) {
    _tree = t;
    list<TreeNode*>& nodes = _tree->_nodes;
    _lit = find(nodes.begin(), nodes.end(), n);//<algorithm> Members
}

Iterator::Iterator(Tree * t, list<TreeNode*>::iterator lt) {
    _tree = t;
    _lit = lt;
}

void Iterator::operator =(const Iterator& it) {
    _tree = it._tree;
    _lit = it._lit;
}

bool Iterator::operator ==(const Iterator & it) {
    return _tree == it._tree && _lit == it._lit;
}

bool Iterator::operator !=(const Iterator & it) {
    return _tree != it._tree || _lit != it._lit;
}

Iterator& Iterator::operator ++() {
    ++_lit;
    return *this;
}

Iterator Iterator::operator ++(int) {
    Iterator it(*this);
    ++_lit;
    return it;
}

int Iterator::operator *() const {
    return ((*_lit)->_data);
}

bool Iterator::operator !() {
    return _lit == _tree->_nodes.end();
}

//Clone函數(shù)
TreeNode* clone(TreeNode* node, List& nodes, TreeNode* nodep) {
    TreeNode* cp = new TreeNode(node->_data, nodep);
    nodes.push_back(cp);
    List& l = node->_children;
    List& cl = cp->_children;
    for (list<TreeNode*>::iterator lt = l.begin(); lt != l.end(); lt++) {
        cl.push_back(clone(*lt, nodes, cp));
    }
    return cp;
}