首先来简单说下一些关于的基本概念。

树是一种非线性的数据结构

1，树是由 n(n>=0)个结点组成的有限集合

如果n = 0 ,称为空树

如果n > 0,则：

有一个特定的称之为根（root）的结点，它只有直接后继，但没有直接前驱

除了根以外的其他结点划分为：m(m>=0)个互不相交的有限集合，T0,T1,T2…Tn-1,每个集合又是一棵树，并且称之为根的子树

2，树中的概念：

树的结点包括一个数据及若干指向子树的分支

结点拥有的子树树称为结点的度

度为0的结点称为叶结点

度不为0的结点称为分支结点

树的度的定义为所有结点中的度的最大值

3,树中结点之间的关系

(1)结点的直接后继称为该结点的孩子

(2)相应的该结点称为孩子的双亲

(3)结点的孩子的孩子的……称为该结点的子孙

(4)相应的该结点称为子孙的祖先

(5)同一个双亲的孩子之间互称兄弟

4，树的深度或高度

(1)结点的层次

(2)根为第1层

(3)根的孩子为第2层

(4)……

(5)树中结点的最大层次称为树的深度或高度

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

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

7，树的相关操作

树的操作

树的一些常用操作

->创建树

->销毁树

->清空树

->插入结点

->删除结点

->获取结点

->获取根结点

->获取树的结点数

->获取树的高度

->获取树的度

树在程序中表现为一种特殊的数据类型

树的操作在程序中的表现为一组函数

Tree:

Tree*Tree_Create();

voidTree_Destroy(Tree* tree);

voidTree_Clear(Tree* tree);

intTree_Insert(Tree* tree, TreeNode* node, int pos);

TreeNode*Tree_Delete(Tree* tree, int pos);

TreeNode*Tree_Get(Tree* tree, int pos);

TreeNode*Tree_Root(Tree* tree);

intTree_Height(Tree* tree);

intTree_Count(Tree* tree);

intTree_Degree(Tree* tree);

再来说下，这里树的基本存储结构。假定我们初始有一棵树，那么我们如何来规定他的存储结构呢？

首先，我们规定每个树结点中有三个属性(1)表示其父亲的指针(2)表示结点中的数据(3)表示孩子的链表，这里为什么是个链表呢？因为一个结点的的孩子可能有一个，也有可能有多个，所以用一个链表表示最为合适了。

第二，每个树之间的关系，我们可以模仿二叉树中的先序遍历思想，对这颗树进行遍历，我们知道，遍历的结果肯定是个序列，那么我们此时就可以果断的把这种序列认为是一种链表结构，那么后期对于树的操作也就可以移植到链表上来了。

最后，关于树的深度、度、删除、根结点的获取与计算，都是在表示那颗树的结点上来操作的。那么这里特别说明一下，由于整个树存在两个链表，所以对于每次删除，插入都要向两个链表中删除和插入。（一个结点既要存在于他父亲的孩子链表中，又要存在于表示整棵树的链表中）

这里我们用到了链表的知识，如果对于链表不熟悉，可以参阅链表的实现与操作(C语言实现)。这里有详尽的代码。

源代码：

#ifndef _GTREE_H_
#define _GTREE_H_

typedef void GTree;
typedef void GTreeData;
typedef void (GTree_Printf)(GTreeData*);

GTree* GTree_Create();

void GTree_Destroy(GTree* tree);

void GTree_Clear(GTree* tree);

int GTree_Insert(GTree* tree, GTreeData* data, int pPos);

GTreeData* GTree_Delete(GTree* tree, int pos);

GTreeData* GTree_Get(GTree* tree, int pos);

GTreeData* GTree_Root(GTree* tree);

int GTree_Height(GTree* tree);

int GTree_Count(GTree* tree);

int GTree_Degree(GTree* tree);

void GTree_Display(GTree* tree, GTree_Printf* pFunc, int gap, char div);

#endif

CPP实现部分：