数据结构:树结构（数据结构树的结构图）

在程序设计中，树结构也是一种经常用到的数据结构。与线性结构不同，树结构采用的是非线性结构组织数据。在实际应用中，许多问题采用非线性的结构来进行描述会更加简单，方便。

直观地看来，树结构是以分支关系定义的一种层次结构。也就是说，应用树结构组织起来的数据应当具有层次关系。而具有这类特性的数据在计算机中应用是十分广泛的。例如：操作系统中的文件管理，网络系统中的域名管理，数据库系统中的索引，编译系统中的语法树等数据都是用树形结构组织的。

用形式化的语言描述，树的定义是这样的：树是由n(n≥0)个结点组成的有穷集合。在任意的一棵非空树中

1、有且仅有一个称为根(Root)的结点；

2、当n>1时，其余的结点分为m（m>0）个互不相交的有限集，T1,T2,……Tm 其中，每一个集合本身又是一棵树，并称为根(Root)的子树(SubTree)。

直观地讲，树的结构如下图所示。

树结构在计算机中的存储形式很多，这里只介绍最为简单的一种树的存储形式――多重链表表示。在多重链表中，每个结点由一个数据域和若干个指针域组成，其中，每一个指针域的指针指向该结点的一个孩子结点。

二叉树的定义

由于二叉树使用的范围最广，最具有代表意义，并且通过一定的方法可以将一棵多叉树转化为二叉树，因此本书重点讨论二叉树。

二叉树是一种特殊形式的树结构。前面已经提到，二叉树的特点是每个结点最多有两棵子树，下面给出二叉树更为严格的定义。

二叉树（Binary Tree）是这样的树结构：它或者为空，或者由一个根结点加上两棵分别称为左子树和右子树的互不相交的二叉树组成。显然这个定义是递归形式的。

从二叉树的定义可知，二叉树宏观上由3部分组成，即根结点，左子树，右子树。因此只要完整地遍历了这3部分，就等于遍历了整个二叉树。根结点很好访问，因为它就是一个结点。关键是如何遍历左子树和右子树。可以把左子树和右子树看成两棵独立的树，因为它们也都是由根结点，左子树，右子树三部分组成，因此遍历它们的方式与遍历原先那棵二叉树的方式是一样的。这样就构成了递归形式的二叉树遍历方法。根据二叉树遍历顺序的不同，对二叉树的遍历有3种方案：先序遍历，中序遍历，后续遍历。

代码操作应用：

#include "stdio.h"
typedef struct BiTNode{
    char data;										/*结点的数据域*/
    struct BiTNode *lchild , *rchild;				/*指向左孩子和右孩子*/
} BiTNode , *BiTree;
/*创建一棵二叉树*/
CreatBiTree(BiTree *T){
    char c;
    scanf("%c",&c);
    if(c == ' ') *T = NULL;
    else{
       *T = (BiTNode * )malloc(sizeof(BiTNode));	/*创建根结点*/
        (*T)->data = c;					/*向根结点中输入数据*/
        CreatBiTree(&((*T)->lchild));	/*递归地创建左子树*/
        CreatBiTree(&((*T)->rchild));	/*递归地创建右子树*/
    }
}
/*访问二叉树结点，输出包含D字符结点位于二叉树中的层数*/
visit(char c,int level){
     if(c == 'D')
        printf("%c is at %dth level of BiTree\n",c,level);
}
/*遍历二叉树*/
PreOrderTraverse(BiTree T,int level){
    if(T){											/*递归结束条件，T为空*/
			visit(T->data,level);					/*访问根结点*/
			PreOrderTraverse(T->lchild,level+1);	/*先序遍历T的左子树*/
			PreOrderTraverse(T->rchild,level+1);	/*先序遍历T的右子数*/
    }
}
main()
{
   int level = 1;
   BiTree T = NULL;		/*最开始T指向空*/
   CreatBiTree(&T);		/*创建二叉树*/
   PreOrderTraverse(T,level);/*遍历二叉树，找到包含D字符结点位于二叉树中的层数*/
   getche();
}