C++数据结构(树的基本表示)

树的基本概念

树是N个结点的有限集合，当N=0的时候呢，称为空树。这是一种特殊情况，在任意一棵非空树中，应该满足，

有且仅有一个特定的称为根的结点。当N>1时，其余的节点可分为m 个互不相交的有限集合，其中每个集合本身又是一棵树，并且称为根节点的子树。显然数的定义是递归的，是一种递归的数据结构。

树作为一种逻辑结构，同时也是一种分层结构，具有以下两个特点，树的根结点没有前驱结点，除根节点外的所有节点，由且只有一个前驱节点。树中所有节点可以有零个或多个后继结点，适合于表示具有层次结构的数据。树中的某个节点最多适合上一层的一个节点，有直接关系,跟结点没有直接上层节点，因此，在N个结点的树中有N-1条边，而树中每个结点于其下一层的0/多个节点有直接关系.

#include
#include
//二叉链表示
struct BiTNode
{
	int data;
	struct BiTNode *Lchild, *rchild;
};
typedef struct BiTNode  BiTNode;
typedef struct BiTNode*  BiTTree;
void main()
{
	BiTNode t1, t2, t3, t4, t5;
	t1.data = 1;
	t2.data = 2;
	t3.data = 3;
	t4.data = 4;
	t5.data = 5;
	//建立关系
	t1.Lchild = &t2;
	t1.rchild = &t3;
	t2.Lchild = &t4;
	t3.Lchild = &t5;
	//树的遍历

}
//三叉链表示
void main()
{
	BiTNode *p1, p2, p3, p4, p5;
	p1 = (BiTNode*)malloc(sizeof(BiTNode));
	p2 = (BiTNode*)malloc(sizeof(BiTNode));
	p3 = (BiTNode*)malloc(sizeof(BiTNode));
	p4 = (BiTNode*)malloc(sizeof(BiTNode));
	p5 = (BiTNode*)malloc(sizeof(BiTNode));
	p1->data = 1;
	p2->data = 2;
	p3->data = 3;
	p4->data = 4;
	p5->data = 5;
	//建立关系
	p1->Lchild = p2;
	p2->rchild = p3;
	p3->Lchild = p4;
	p4->Lchild = p5;
	//树的遍历

}
//双亲表示法   子结点中保存了双亲的位置信息
#define  MAX_TREE_SIZE
typedef struct BPTNope
{
	int data;
	int parentPosition;//指向双亲的指针
	char LRTag;//左右孩子标志域
}BPTNope;
typedef struct BPTTree//BPTNope这个又被BPTTree包含
{
	BPTNope nodes[100];//因为节点之间是分散的,需要把节点存储到数组中
	int num_nodes;//节目数目
	int root;//根结点的位置

}BPTTree;
void main()
{
	BPTTree tree;
	//
	tree.nodes[0].parentPosition = 1000;
	//
	tree.nodes[1].parentPosition = 0;
	tree.nodes[1].data = 'B';
	tree.nodes[1].LRTag = 1;
	//
	tree.nodes[2].parentPosition = 0;
	tree.nodes[2].data = 'C';
	tree.nodes[2].LRTag = 1;

}

小结(基本术语):

1)树中一个结点的子结点个数称为该节点的度，树中结点的最大度数称为树的度

度>0的结点称为分支结点;度为0(没有子女节点)的节点称为叶子节点或者是终端节点。在分支节点中，每个节点的分支数就是该节点的节点的度

结点的深度、高度和层次。节点的层次从树根开始定义，根结点为第一层，它的子节点为第二层。以此类推，结点的深度是从根节点开始自顶向下，逐层累加。点点的高度是从叶节点开始，自底向上逐层垒下。树的高度又称深度，是树中结点的最大层数

有序树和无序树树中结点的子树，从左到右是有次序的，不能交换，这样的数称为有序树。有序数中一个节点的子节点，按从左到右的顺序出现是有。还是有关联的，反之则为无序树

路径和路径，长度，树中两个节点之间的路径是由这两个节点之间所经过的节点序列构成的，而路径长度是路径上所经过的边的个数

由于术中的分支是有向的，即从双亲结点到指向孩子节点，所以树中的路径是从上向下,同一双亲结点的两个孩子，结点之间不存在路径

森林，森林是M和互不相交的树的集合。森林的概念与树的概念十分相近，因为只要把树的根结点删去，就成了森林，反之，只要给n棵独立的数加上一个节点，并把。这N棵树作为该节点的子树，则森林就变成了树.