文章目录
非线性结构——树定义树分类树的存储树的操作（二叉树）树的应用链式二叉树遍历具体程序
非线性结构——树定义
专业定义：
有且只有一个称为根的节点。有若干个互不相交的子树，这些子树本身也是一棵树。 通俗地讲：
树是由节点和边组成。每个节点只有一个父节点，但可以有多个子节点。但有一个节点例外，该节点没有父节点，此节点称为根节点。 专业术语：
节点父节点子节点子孙堂兄弟深度：从根节点到最底层节点之间的层数称之为深度。叶子结点：没有子节点的节点。非终端节点：实际就是非叶子节点。度：子节点拥有最多叶子节点的个数。
树分类
一般树（可以有序）
任意一个节点的子节点的个数都不受限制。 二叉树（有序）
任意一个节点的子节点的个数最对是两个，且子节点的位置不可更改。二叉树分类：
一般二叉树满二叉树：在不增加层数的情况下，无法再增加节点。完全二叉树：如果只是删除了满二叉树最底层最右边的连续若干个节点，这样形成的二叉树就是完全二叉树。完全二叉树包含满二叉树（满二叉树是完全二叉树的特例）。 森林
n个互不相交的树的集合。
树的存储
二叉树的存储
连续存储（完全二叉树）
优点：查找某个节点的父节点和子节点（也包括判断有没有子节点）速度很快缺点：耗用内存空间过大 链式存储 一般树的存储
双亲表示法（求父节点方便） 孩子表示法（求子节点方便） 双亲孩子表示法（求父节点子节点都很方便） 二叉树表示法
把一个普通数转换成二叉树来存储。设法保证任意一个节点的左指针域指向它的第一个孩子，右指针域指向它的兄弟节点。一个普通树转化成的二叉树一定没有右子树。 森林的存储
同样是转化成二叉树来存。
树的操作（二叉树）
先序遍历
先访问根节点，再先序访问左子树，再先序访问右子树。 中序遍历
中序遍历左子树，再访问根节点，再中序遍历右子树。 后序遍历
中序遍历左子树，中序遍历右子树，最后访问根节点。 已知两种遍历序列求二叉树
通过先序和中序或者中序和后序，我们可以还原出元素二叉树（确定唯一二叉树）。但是通过先序和后序是无法还原原始二叉树的。已知先序和中序，求后序 已知中序和后序，求先序
树的应用
树是数据库数据组织的一种重要形式操作系统子父进程的关系就是一棵树面向对象语言中类的继承关系本身就是一棵树赫夫曼树
链式二叉树遍历具体程序
#include<stdio.h>
#include<malloc.h>
struct BTNode
{
char data
;
struct BTNode
* pLchild
;
struct BTNode
* pRchild；
}
struct BTNode
* CreateBTree(void);
void PreTraverseBTree(struct BTNode
* pT
);
void PostTraverseBTree(struct BTNode
* pT
);
void InTraverseBTree(struct BTNode
* pT
);
int main(void){
struct BTNode
* pT
= CreateBTree();
PreTraverseBTree(pT
);
InTraverseBTree(pT
);
PostTraverseBTree(pT
);
return 0;
}
void PreTraverseBTree(struct BTNode
* pT
){
if(pT
!= NULL){
printf("%c\n",pT
->data
);
if(NULL != pT
){
PreTraverseBTree(pT
->pLchild
);
}
if(NULL != pT
){
PreTraverseBTree(pT
->pRchild
);
}
}
}
void PostTraverseBTree(struct BTNode
* pT
){
if(pT
!= NULL){
if(NULL != pT
){
PreTraverseBTree(pT
->pLchild
);
}
if(NULL != pT
){
PreTraverseBTree(pT
->pRchild
);
}
printf("%c\n",pT
->data
);
}
}
void InTraverseBTree(struct BTNode
* pT
){
if(pT
!= NULL){
if(NULL != pT
){
PreTraverseBTree(pT
->pLchild
);
}
printf("%c\n",pT
->data
);
if(NULL != pT
){
PreTraverseBTree(pT
->pRchild
);
}
}
}
struct BTNode
* CreateBTree(void){
struct BTNode
* pA
= (struct BTNode
*)malloc(sizeof(struct BTNode
));
struct BTNode
* pB
= (struct BTNode
*)malloc(sizeof(struct BTNode
));
struct BTNode
* pC
= (struct BTNode
*)malloc(sizeof(struct BTNode
));
struct BTNode
* pD
= (struct BTNode
*)malloc(sizeof(struct BTNode
));
struct BTNode
* pE
= (struct BTNode
*)malloc(sizeof(struct BTNode
));
pA
->data
= 'A';
pB
->data
= 'B';
pC
->data
= 'C';
pD
->data
= 'D';
pE
->data
= 'E';
pA
->pLchild
= pB
;
pA
->pRchild
= pC
;
pB
->pLchild
= pB
->pRchild
= NULL;
pC
->pLchild
= pD
;
pC
->pRchild
= NULL;
pD
->pLchild
= NULL;
pD
->pRchild
= pE
;
pE
->pLchild
= pE
->pRchild
= NULL;
return pA
;
}
