大师兄的数据结构学习笔记(四）:树结构

大师兄的数据结构学习笔记(三）:队列
大师兄的数据结构学习笔记(五）:二叉树

一、什么是树(Tree)

• 树是个结点构成的有限集合。
  
• 当时，为空树。
• 任意一个非空树具备以下性质：

1) 有一个成为根(root)的特殊结点，用r表示。
2) 其余结点可分为个互不相交的有限集。
3) 其中每个集合本身又是一棵子树(subtree)。
4) 除了根结点外，每个结点有且仅有一个父结点。
5) 一颗N个结点的树有N-1条边。

• 树的相关术语：

术语	含义
结点的度(Degree)	结点的子树个数
树的度	树的所有结点中最大的度数
叶结点(Leaf)	度为0的结点
父结点(Parent)	有子树的结点是其子树的根结点的父结点
子结点(Child)	与父结点对应的结点
兄弟结点(Sibling)	具有同一父结点的各结点彼此是兄弟结点
路径	两个结点间的结点序列
路径长度	路径所包含的边数
祖先结点(Ancestor)	沿树根到某一结点路径上的所有结点都是它的祖先结点
子孙结点(Descendant)	某一结点的子树中的所有结点它的子孙结点
结点的层次(Level)	根结点层数位1，其余结点的层数是其父结点+1
树的深度(Depth)	数的所有结点中的最大层次是这棵树的深度

二、树的表示方法

1. 双亲表示法

• 由于树中的每个结点都有唯一的一个双亲结点，所以取一块连续的内存空间，在存储每个结点的同时，各自都附加一个记录其父结点位置的变量。

• 适合频繁地查找某结点的父结点时使用。

  
  

typedef int DataType;
const int tree_size = 100; //树结点的最大数量

typedef struct PTNode
{
    DataType data;  //结点的数据类型
    int parent;     //父结点的下标位置
}PTNode;

class Tree
{
private:
    PTNode nodes[tree_size];
    int r, n;       //根的位置下标和结点数
};

2.孩子表示法

• 将树中的每个结点的孩子结点排列成一个线性表，用链表存储起来。
• 对于含有 n 个结点的树来说，就会有 n 个单链表。
• 将 n 个单链表的头指针存储在一个线性表中。
• 适合频繁查找某结点的孩子结点时使用。

typedef int DataType;
const int tree_size = 100; //树结点的最大数量

typedef struct CTNode
{
    int child;  //子结点位置下标
    struct CTNode* next;
}*ChildPtr;

typedef struct
{
    DataType data;  //结点数据类型
    ChildPtr firstchild; //孩子链表指针
}CTBox;

class Tree
{
private:
    CTBox nodes[tree_size];
    int r, n;       //根的位置下标和结点数
};

3.孩子兄弟表示法

• 结合了以上两种表示方法。
• 使用链式存储结构存储普通树。
• 链表中每个结点由孩子指针、数据和兄弟指针三部分组成。
• 通过孩子兄弟表示法，普通树转化为了二叉树，所以孩子兄弟表示法又被称为“二叉树表示法”。

typedef int DataType;

typedef struct CSNode
{
    DataType data;                  //数据结构
    struct CSNode* firstchild;      //子结点指针
    struct CSNode* nextsibling;    //兄弟结点指针
}CSNode,*CSTree;