数据结构之树

简介:

树形结构是非线性结构，可以表达数据之间一对多的关系，这里说下树以及二叉树结构。

树的定义

树是由N个节点组成的有限集合，如果n=0，则它是一个空树。如果n>0,这n个节点仅存在一个节点作为树的节点，其它节点可分成若干个子集代表子树。它的特点是每一个节点可以有零个或多个后继节点，但有且只有一个前驱节点。

树的性质

• 树的节点数等于所有节点的度数+1
• 度为m的树中第i层至多有m的（i-1）个平方的节点（i>=1）
• 高度为h的m次树最多有m-1分之m的（h-1）个平方的节点
• 具有n个节点的m次树的最小高度为大于等于log m (n(m-1)+1)的值的最小整数

树的运算

树的遍历过程有三种方式，先根遍历，后根遍历以及层次遍历

1. 先根遍历：访问根节点，然后按照从左至右的顺序遍历子树
2. 后跟遍历：先按照从左至右的顺序遍历子树，再访问根节点
3. 层次遍历：从根节点开始，从上到下，从左到右遍历树

树的存储结构

树的存储结构不同，也会影响其运算

1. 双亲存储结构
   typedef struct
   { ElemType data; //存放节点的值
   int parent; //存放双亲的位置
   } PTree[MaxSize];
   在这个存储结构中，求某个节点的根节点很容易，但是求孩子节点时，则需要遍历整个结构
2. 孩子链存储结构
   typedef struct node
   {
   ElemType data; //节点的值
   struct node * sons[MaxSons]; 指向孩子节点
   } TSonNode;
   在这个存储结构中找到某个节点的子节点很容易，找双亲节点则比较费时，MaxSon为树的度，如果树的度较大，会存在较多的空指针域
3. 孩子兄弟链存储结构
   typedef struct tnode
   {
   ElemType data; //节点的值
   struct tnode hp; //指向兄弟
   struct tnode vp; //指向孩子节点
   }TSBNode;
   该结构的优点是比较容易将树转换成二叉树，但同样找双亲节点比较麻烦