树的概念
首先，让我们来了解一下树的一些基本概念。
下图为一颗一般树。
image.png
树，有且只有一个根结点，哪怕只有一个结点，它其实也是一棵树。
孩子:如图，B,C,D为A的孩子。
度:结点所拥有子树的个数。（A结点的度就是3，B结点的度是2)。
叶子：度为0的结点，称为叶子结点，或者终端结点。(K,J,F,G,M,I,J为叶子结点)
双亲：上一个结点，在树中，双亲指的是一个结点。
兄弟：同属于一个双亲结点下的结点。
高度：距离最长的叶子节点的长度。
深度：从根结点到当前结点的长度。
层：从根节点开始计算，字面意思。
二叉树概念
除了根节点，每个结点最多只有2颗子树。这样的树，我们称为二叉树。
特殊二叉树。
1.斜树
image.png
image.png
2.满二叉树
每一个结点都有左结点和右结点，并且所有的叶子都在一个层级上面。这样的树，称为满二叉树。
image.png
3.完全二叉树
具备有n个结点的二叉树。按照陈序编号陈列，这样的树，称为完全二叉树。
image.png
二叉树的顺序存储结构分析
当二叉树为一颗完全二叉树时，可以使用一个数组进行存储。第一个元素就是根结点。
image.png
当二叉树不是完全二叉树时。
image.png
image.png
空结点使用null来填充。很多空间是被浪费的。
所以一般顺序存储只使用在完全二叉树上。
遍历
1.前序遍历
image.png
void PreOrderTraverse(BiTree T)
{
if(T==NULL)
return;
printf("%c",T->data);/* 显示结点数据，可以更改为其它对结点操作 */
PreOrderTraverse(T->lchild); /* 再先序遍历左子树 */
PreOrderTraverse(T->rchild); /* 最后先序遍历右子树 */
}
中序遍历
image.png
void InOrderTraverse(BiTree T)
{
if(T==NULL)
return ;
InOrderTraverse(T->lchild); /* 中序遍历左子树 */
printf("%c",T->data);/* 显示结点数据，可以更改为其它对结点操作 */
InOrderTraverse(T->rchild); /* 最后中序遍历右子树 */
}
后序遍历
image.png
void PostOrderTraverse(BiTree T)
{
if(T==NULL)
return;
PostOrderTraverse(T->lchild); /* 先后序遍历左子树 */
PostOrderTraverse(T->rchild); /* 再后序遍历右子树 */
printf("%c",T->data);/* 显示结点数据，可以更改为其它对结点操作 */
}
