数据结构-二叉树的基本操作

二叉树的存储

        顺序存储

        顺序存储结构适用于完全二叉树，用一组连续的存储单元按照完全二叉树的每个结点编号的顺序存放结点内容。

const int M = 100;
typedef struct{
    int data[M];    
    int n;            //当前完全二叉树的结点个数
}BTree;

        顺序存储利用了完全二叉树的结点编号的性质。特点是空间利用率高，便于寻找孩子和双亲。但是如果二叉树不是完全二叉树，则需要将空缺的位置用其他符号填补，如果空缺的结点过多则会导致空间利用率的下降。

        因此，为了更好的应对一般情况，需要对二叉树的结点个数进行动态存储。

        链式存储

        链式存储是二叉树最常用的存储结构。每一个结点的存储都由多个结点组成，分别是指向左孩子的指针、保存当前结点信息的变量和指向右孩子的指针。

        一个二叉链表由头指针确定。若二叉树为空，则头指针指向NULL，若结点的某一个孩子不存在，则相应的指针为空。在具有个结点的二叉树中，共有个指针域，其中有个用来指示结点的左孩子和右孩子，其他的个指针域为空。

typedef struct bnode{
    int data;
    struct bnode *lchild,*rchild;
}Bnode,*BTree;

        链式存储的特点是寻找孩子结点容易，寻找双亲困难。因此可以多设置一个指针域指向双亲。在每次存储新结点时新建指向即可。

二叉树的遍历

        二叉树作为非线性结构，对于遍历会有不同的方式。而二叉树的遍历就是以某种顺序对二叉树的每一个结点进行访问，每个结点仅访问一次。而对于所有的访问，按照人们先左后右的习惯，可以大致分为以下三种：

        先序遍历

        按照根、左、右的顺序，先访问根结点，然后分别访问左子树、右子树。每次访问一个新结点时重复以上操作。

        因此，先序遍历的第一个值是整个二叉树的根节点。

        由于这种访问的特性，先序遍历可以使用递归的方法实现。

void PreOrder(BTree t)
{
    if(t)
    {
        printf("%d",t->data);
        PreOrder(t->lchild);    //遍历左子树
        PreOrder(t->rchild);    //遍历右子树
    }
}

        中序遍历

        按照左、根、右的顺序，先访问根节点的左子树，然后访问根节点，最后访问根节点的左子树。同样可以用递归实现。

void InOrder(BTree t)
{
    if(t)
    {
        InOrder(t->lchild);    //访问左子树
        printf("%d",t->data);
        InOrder(t->rchild);    //访问右子树
    }
}

         后序遍历

        按照左、右、根的顺序，先访问左子树，然后访问右子树，最后访问根节点。

        因此，后序遍历的最后一个值是整个二叉树的根节点。

void PostOrder(BTree t)
{
    if(t)
    {
        PostOrder(t->lchild);    //访问左子树
        PostOrder(t->rchild);    //访问右子树
        printf("%d",t->data);
    }
}

         层次遍历

        从二叉树的根节点开始按照第一层到最后一层的顺序从左到右进行遍历。这种遍历不能使用递归算法。

        由于存储二叉树时从根节点开始按照从第一层到最后一层，每一层从左到右的顺序进行存储，遍历时则是按照与存储同样的顺序进行遍历，所以可以使用队列。

void LeOrder(BTree t)
{
    if(t == NULL)
        return;
    Init_Queue();                //初始化队列
    Push(Q,t->data);             //将根节点入队
    while(!Empty(Q))             //队列不为空时
    {
        Front(Q,x);              //取队首
        BTree t->data = x;
        printf("%d",x);
        Pop(Q);                  //将队首出队
        if(t->lchild)            //访问左子树
            Push(Q,t->lchild);
        if(t->rchild)            //访问右子树
            Push(Q,t->rchild);
    }
}