树的概念

首先，让我们来了解一下树的一些基本概念。
下图为一颗一般树。

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);/* 显示结点数据，可以更改为其它对结点操作 */
}