1、树的定义

2、相关的术语

但是在数据结构中，任何一棵树，删去根节点就变成森林了。

3、树的抽象数据类型

ADT Tree
{
    Data:
        树是由一个根结点和若干棵子树构成的.
        树中结点具有相同数据类型及层次结构.
    
    Operation:
        
        //操作结果：构造一棵空树
        InitTree(&T)
        
        //初始条件：串S是以广义表形式表示的树
        //操作结果：按照S构造一棵树
        CreateTree(&T,S)
        
        //初始条件：树T存在，Visit是对结点操作的应用函数
        //操作结果：按某种次序对T的每个结点调用函数Visit()
        //一次且至多一次，一旦visit()失败，则操作失败.
        OrderTree(T,Visit())
        
        //初始条件：树T存在
        //操作结果：在树T中查找元素e，若查找成功，返回true
        //否则返回false
        SearchTree(T,&e)
        
        //初始条件：树T存在
        //操作结果：以某种形式输出树T
        PrintTree(T)
        
        //初始条件：树T存在
        //操作结果：求树T的深度
        TreeDepth(T)
        
        //初始条件：树T存在
        //操作结果：销毁树T
        DestroyTree(&T)
}

4、树的存储结构

树中节点之间的逻辑关系都是父子关系，即通过双亲和孩子来刻画结点之间的逻辑关系，因而树的存储结构要求不仅存储各结点的数据信息，还要唯一地反映树中各结点之间的逻辑关系--父子关系，其关键是如何表示结点的双亲和孩子。根据结点中指针域所指的对象可分为双亲表示方法，孩子表示法和双亲孩子表示法。

（1）双亲表示法

a>数组表示

#define MAX_TREE_SIZE 100               //树中结点的最大个数
typedef struct
{
    TElemType data;                        //结点的值
    int parent;                            //结点的双亲在数组中的下标
}pTreeNode;                             //结点类型

pTreeNode pTree[MAX_TREE_SIZE];

b>链表表示

#define MAX_TREE_SIZE 100               //树中结点的最大个数
typedef struct
{
    TElemType data;                        //结点的值
    pTreeNode *parent;                    //结点的双亲指针
}pTreeNode;                             //结点类型

（2）孩子表示法

a>数组表示

#define MAX_SON_SIZE 3                  //树的度
typedef struct
{
    TElemType data;                        //结点的值
    int Child[MAX_SON_SIZE];            //结点的孩子在数组中的下标
}CTreeNode;                                //数组元素类型

CTreeNode CTree[MAX_TREE_SIZE];

b>链表表示

typedef struct CTNode
{
    TElemType data;                     //结点的值
    struct CTNode *child[MAX_SON_SIZE];    //结点的指针域，指向孩子结点
}CTNode,*CTree;                            //结点的类型

c>左孩子右兄弟表示法

typedef struct LRTNode
{
   TElemType data;                        //结点的值
   struct LRTNode *lchild;                //左孩子指针
   struct LRTNode *rsibling;            //右兄弟指针
}LRTNode,*LRTree;                        //结点的类型

（3）双亲孩子表示法

a>数组表示

typedef struct
{
    TElemType data;                        //结点的值
    int parent;                            //结点的双亲在数组中的下标
    int child[MAX_SON_SIZE];            //结点的孩子在数组中的下标
}PCTreeNode;                             //数组元素的类型

b>链表表示法

typedef struct pCTNode                    
{    
    TElemType data;                        //结点的值
    struct pCTNode *parent;                //结点的双亲指针    
    struct pCTNode *child[MAX_SON_SIZE];//结点的孩子指针
}PCTNode,*pCTree;                          //结点类型

c>双亲数组孩子链表表示法

typedef struct Node
{
    int child;                            //孩子结点在数组中的下标
    struct Node *next;                    //孩子链表中的结点类型
}CNode;

typedef struct
{
    TElemType data;                        //结点的值
    int parent;                            //结点的双亲在数组中的下标
    CNode *Childlink;                    //指向孩子链表
}PCLink;                                //数组元素的类型

5、树的基本操作实现

typedef struct CTNode
{
    TElemType data;                     //结点的值
    struct CTNode *child[MAX_SON_SIZE];    //结点的指针域，指向孩子结点
}CTNode,*CTree;                            //结点的类型

（1）初始化操作

void InitTree(CTree &T)
{
    T = NULL;
}

（2）创建树操作

void CreateTree(CTree &T,char *S)
{
    CTree stack[MS],p;
    int i=0,d[MS];
    int top = -1;
    while (S[i])
    {
        switch(S[i])
        {
        case ' ': break;
        case '('://??
            top++;
            stack[top] = p;
            d[top] = 0;
            break;
        case ')'://??
            top--;
            break;
        case ',':
            d[top]++;
            break;
        default:
            if (!(p=(CTree)malloc(sizeof(CTNode))))
                exit(1);
            p->data = S[i];
            for (int i = 0;i < MAX_SON_SIZE;i++)
                p->child[i] = NULL;
            if (!T)
                T = p;
            else
                stack[top]->child[d[top]] = p;
            break;
        }
        i++;
    }
}

（3）树的遍历

a 前序遍历

先访问根节点，然后从左到右依次先序遍历每一个子树，此遍历过程是一个递归的过程。对上图进行前序遍历得到的结果是：

A B D E H I F C G

<span style="font-weight: normal;">//前序遍历
void PreOrderTree(CTree T)
{
	if (T)
	{
		cout << T->data << ' ';
		for (int i=0;i<MAX_SON_SIZE;i++)
		{
			PreOrderTree(T->child[i]);
		}
	}
}</span>

b 后序遍历

先从左到右依次后序遍历根节点的一个子树，然后再访问根节点，这种遍历也是一个一个递归的过程，同样对上图进行遍历得到的结果是：

D H I E F B G C A

//后序遍历
void PostOrderTree(CTree T)
{
	if (T)
	{
		for (int i=0; i<MAX_SON_SIZE; i++)
		{
			PostOrderTree(T->child[i]);
		}
		cout << T->data << ' ';
	}
}

c 层序遍历

从树的第一层（根节点）开始，从上到下逐层遍历，在同一层中，则按照从左到右的顺序进行访问，直到整个树种的所有节点都被访问为止。对上图进行层序遍历的结果是：

A B C D E F G H I

void LevelOrderTree(CTree T)
{
    SqQueue  Q;								//定义一个队列
    CTree    p;								//
    InitQueue_Sq(Q,MAX_TREE_SIZE,10);		//初始化队列
    if(T)									//非空跟指针进队
		EnQueue_Sq(Q,T);
	while(!QueueEmpty_Sq(Q))				//非空队列循环
	{
		DeQueue_Sq(Q,p);					//队列首元素出队
		cout<< p->data << ' ';				//打印输出元素值
		for(int i=0;i<MAX_SON_SIZE;++i)
		{
			if(p->child[i])
				EnQueue_Sq(Q,p->child[i]);
		}
	}
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!