C树！你今天爬了吗？C/C++二叉树的创建和遍历

一、前言

        最近在准备计算机考试，有时间的时候就会学学简单的数据结构，做一些学习笔记的分享，看一下二叉树。根据我的理解，二叉树就是类似一棵树的二分叉数据存储结构。它和链表有点相似，链表是线性的，只能沿一个方向去查找数据，二叉树就不一样。

“二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个节点最多只能有两棵子树，且有左右之分。”

二、创建二叉树

        1、二叉树的结构

struct Tree
{
    char data;
    struct Tree*left;
    struct Tree*right;
};

        2、创建节点

        我是一个一个的建立的。

struct Tree*createTree(int data);//创建一个树体

{

    struct Tree*tree = (struct Tree*)malloc(sizeof(struct Tree));

    tree->data=data;

    tree->left=NULL;

    tree->right=NULL;

    return tree;

}

        3、形成二叉树

        上面，我们建立了一个树的节点，通过节点与节点的链接，就可以形成一棵树;

//形成树的结构
void beingTree(struct Tree*nodeTree,struct Tree*letfTree,struct Tree*rightTree)
{
    nodeTree->left=letfTree;
    nodeTree->right=rightTree;
}
//主函数调用
struct Tree*tree1=createTree(5);
struct Tree*tree2=createTree(2);
struct Tree*tree3=createTree(11);
struct Tree*tree4=createTree(3);
struct Tree*tree5=createTree(6);
struct Tree*tree6=createTree(4);
struct Tree*tree7=createTree(8);

beingTree(tree1,tree2,tree3);
beingTree(tree2,tree4,tree5);
beingTree(tree3,tree6,tree7);

inordertraversal(tree1);

这样就创建了一棵满二叉树（除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树。）如下图：

​

满二叉树

        除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树。

完全二叉树

        和满二叉树不同的是最后一层不是满的，除了最了一层，其余的k-1层是一个满二叉树，最后一层的结点是从左开始排列的。（满二叉树是特殊的完全二叉树，但完全二叉树不一定是满二叉树）

二、遍历二叉树

        1、前序遍历（根左右）

                前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。 在遍历左、右子树时，仍然先访问 根结点 ，然后遍历左子树，最后遍历右子树。很容易发现，通过前序遍历，上图的结果为：5-2-3-6-11-4-8，前序遍历还有一种方法记忆，从第一个根节点开始，围绕树的边沿画线先经过哪一个节点就记下哪一个节点的值。代码的话这里采用递归的方式。

//递归---前序遍历---根左右
void ordertraversal(struct Tree*tree)
{   
    if(tree)
    {
        printf("%c\n",tree->data);
        ordertraversal(tree->left);
        ordertraversal(tree->right);
    }
    else
        return ;
}

        二、中序遍历（左根右）

                也叫做 中根遍历 、中序周游。 在二叉树中，中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。 中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。上图的结果为：3-2-6-5-4-11-8

//递归---中序遍历---左根右
void inordertraversal(struct Tree*tree)
{   
    if(tree)
    {
        inordertraversal(tree->left);
        printf("%c\n",tree->data);
        inordertraversal(tree->right);
    }
    else
        return ;
}

        三、后序遍历（左右根）

                后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后遍历根结点。上图的结果为：3-6-2-4-8-11-5

//递归---后序遍历---左右根
void pastordertraversal(struct Tree*tree)
{
    if(tree)
    {
        pastordertraversal(tree->left);
        pastordertraversal(tree->right);
        printf("%c\n",tree->data);
        
    }
    else
        return ;

}

/*---这儿原来是准备写释放二叉树的空间的，没来得及---*/