51_树的定义与操作

关键词：树的定义、度的概念、树中的前驱和后继、树中结点的层次、树的有序性、森林的概念、树的实现

0. 树的定义

树是一种非线性的数据结构；
树是由n(n>=0)个结点组成的有限集合；
如果n=0，称为空树；
如果n>0，则：

• 有一个特定的称之为根(root)的结点
• 根节点只有直接后继， 没有直接前驱
• 除根以外的其他结点划分为m(m>=0)个互不相交的有限集合T0,T1,...Tm-1，每个集合又是一棵树，并且称之为根的子树(sub tree)。

1. 度的概念

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

度为3的树

2. 树中的前驱和后继

• 结点的直接后继称为该结点的孩子——相应的，该节点称为孩子的双亲
• 结点的孩子的孩子的.......称为该结点的子孙——相应的，该结点称为子孙的祖先

• 同一个双亲的孩子之间互称兄弟

  
  树的前驱和后继示例

3. 树中结点的层次

根为第一层
根的孩子为第二层
...
树中结点的最大层次称为树的深度或高度

树的层次结构图

4. 树的有序性

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

5. 森林的概念

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

6. 树的实现

Tree.h

#ifndef TREE_H
#define TREE_H

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

namespace DTLib
{

template < typename T >
class Tree : public Object
{
protected:
    TreeNode<T>* m_root;
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 void clear() = 0;
};
}

#endif // TREE_H

TreeNode.h

#ifndef TREENODE_H
#define TREENODE_H

#include "Object.h"

namespace DTLib
{

template < typename T >
class TreeNode : public Object
{
public:
    T value;
    TreeNode<T>* parent;

    TreeNode()
    {
        parent = NULL;
    }

    virtual ~TreeNode() = 0;
};

template < typename T >
TreeNode<T>::~TreeNode()
{
}
}
#endif // TREENODE_H

树与结点的类关系

7. 小结

• 是一种非线性的数据结构
• 结点拥有唯一前驱（父结点）和若干后继（子节点）
• 树中的结点包含一个数据及若干指向其他结点的指针
• 树与结点在程序中表现为特殊的数据类型

声明：此文章仅是本人在学习狄泰学院《数据结构实战开发教程》所做的笔记，文章中包含狄泰软件资料内容，一切版权归狄泰软件所有！
实验环境：ubuntu10 + Qt Creator2.4.1 + Qt SDK 4.7.4