通用树抽象父类——Tree、TreeNode

树的基本概念

  树的定义：
　　　　树是一种非线性的数据结构
　　　　树是由 n(n >= 0)个结点组成的有限集合，若 n = 0，则称之为空树
　　　　树中(n > 0)的首结点，称为根节点，根节点只有直接后继，没有直接前驱
　　　　除根以外的其它结点划分为m (m >= 0)个互不相交的有限集合T0 , T1, …，Tm-1, 每个集合又是一棵树，该树又称为根树的子树

树的示例

  树中度的概念：
　　　　树的结点包含一个数据及若干指向子树的分支
　　　　结点拥有的子树数目称为结点的度
　　　　树中的度为所有结点中度的最大值
　　　　度为0的结点称为叶结点
　　　　度不为0的结点称为分支结点

树的度示例：度为3的树

  树中的前驱和后继：
　　　　结点的直接后继称为该结点的孩子
　　　　  相应的，该结点称为孩子的双亲
　　　　结点的孩子的孩子…称为该结点的子孙
　　　　  相应的，该结点称为子孙的祖先
　　　　同一个双亲的孩子之间互称兄弟

树的前驱与后继示例

  树中的深度或高度：
　　　　树中结点的最大层次称为树的深度或高度

树中结点的层次示例

  树的有序性：
　　　　如果树中结点的各子树从左向右是有次序的，子树间不能互换位置，则称该树为有序树，否则为无序树

树的有序性示例

  森林的概念：
　　　　森林是由 n(n >= 0)棵互不相交的树组成的集合

3课树组成的森林示例

  树与结点之间的关系：
　　　　树和结点是两个类，树中引用结点（组合关系）

树与结点之间的关系

Tree

实现抽象父类Tree，定义树的基本功能接口
Tree.h

#ifndef __TREE_H_
#define __TREE_H_

#include "Object.h"
#include "TreeNode.h"
#include "SharedPointer.h"


namespace JYlib
{


/*
        树（抽象类）
基本功能：
    树中的元素插入与删除
    获取树的结点数
    获取树的高度
    获取树的度
    清空树
*/
template < typename T >
class Tree : public Object
{
protected:
    TreeNode<T>* m_root;

    //拷贝构造与赋值构造封装，不允许拷贝或者赋值
    Tree(const Tree<T>& e);
    Tree& operator =(const Tree<T>& e);
public:
    Tree()	{ m_root = NULL; }
    virtual bool insert(TreeNode<T>* node) = 0;
    virtual bool insert(const T& value,TreeNode<T>* parent) = 0;
    virtual SharedPointer< Tree<T> > remove(const T& value) = 0;
    virtual SharedPointer< Tree<T> > remove(TreeNode<T>* node) = 0;
    virtual TreeNode<T>* find(const T& value)const = 0;
    virtual TreeNode<T>* find(TreeNode<T>* node)const = 0;
    virtual TreeNode<T>* root()const = 0;
    virtual int degree()const = 0;
    virtual int count()const =0;
    virtual int height()const = 0;
    virtual bool begin() = 0;
    virtual bool next() = 0;
    virtual T current() = 0;
    virtual bool end() = 0;

    virtual void clear() = 0;

};


}



#endif

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

TreeNode

实现抽象父类TreeNode，定义结点的基本功能接口
TreeNode.h

#ifndef __TREENODE_H_
#define __TREENODE_H_

#include "Object.h"

namespace JYlib
{

/*
            树节点(抽象类)
增加了指向父结点的指针（工程需求，有许多用处）

使用工厂模式：对每一个节点产生时就进行标记，是否为堆对象
因为堆对象需要析构，其他对象不需要，要加以区分
*/
template < typename T >
class TreeNode : public Object
{
protected:
    bool m_flag;//堆对象标记

    //拷贝构造与赋值构造封装，不允许拷贝或者赋值
    TreeNode(const TreeNode<T>& e);
    TreeNode& operator =(const TreeNode<T>& e);

    /*
    重载new操作符并成为保护成员函数，使得无法在外界new一个对象
    只能使用提供的封装函数NewNode,确保每个成员的标记正确
    */
    void* operator new(unsigned int size) throw()
    {
        return Object::operator new(size);
    }

public:
    T value;
    TreeNode<T>* parent;

    TreeNode()
    {
        parent = NULL;
        m_flag = false;
    }

    bool flag()//返回该结点是否为堆对象
    {
        return m_flag;
    }

    virtual ~TreeNode() = 0;
};

template < typename T >
TreeNode<T>::~TreeNode()//虚函数 实现抽象类
{

}


}

#endif

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63