二叉树的相关复习

-------------------------------------------------------------------------

二叉树的前序递归遍历

void PreOrderTraverse(BiTree t)
{
    if(t != NULL)
    {
        printf("%c ", t->data);
        PreOrderTraverse(t->lchild);
        PreOrderTraverse(t->rchild);
    }
}

二叉树的中序递归遍历

void InOrderTraverse(BiTree t)
{
    if(t != NULL)
    {
        InOrderTraverse(t->lchild);
        printf("%c ", t->data);
        InOrderTraverse(t->rchild);
    }
}

二叉树的后续递归遍历

void PostOrderTraverse(BiTree t)
{
    if(t != NULL)
    {
        PostOrderTraverse(t->lchild);
        PostOrderTraverse(t->rchild);
        printf("%c ", t->data);
    }
}

----------------------------------------------------------------------------------

二叉树的前序非递归遍历

根据前序遍历访问的顺序，优先访问根结点，然后再分别访问左孩子和右孩子。即对任一结点，其可看做是根结点，因此可以直接访问，访问完之后，若其左孩子不为空，按相同的规则访　　问它的左子树；当访问其左子树时，再访问它的右子树，因此其处理过程如下：

对于任一结点p：

a. 访问结点p，并将结点p入栈；

b. 判断结点p的左孩子是否为空，若为空，则取栈顶结点并进行出栈操作，并将栈顶结点的右孩子置为当前的结点p，循环置a；若不为空，则将p的左孩子置为当前结点p；

c. 直到p为空，并且栈为空，则遍历结束。

int NoPreOrderTraverse(BiTree t)
{
    SqStack s;
    InitStack(&s);
 
    BiTree tmp = t;
    if(tmp == NULL)
    {
        fprintf(stdout, "the tree is null.
");
        return ERROR;
    }
 
    while((tmp != NULL) || (IsEmpty(&s) != 1)) 
    {
        while(tmp != NULL)
        {
            Push(&s, tmp);
            printf("%c ", tmp->data);
            tmp = tmp->lchild;
        }
        if(IsEmpty(&s) != 1)
        {
            Pop(&s, &tmp);
            tmp = tmp->rchild;
        }
    }
     
    return OK;
}

二叉树的中序非递归遍历

　　根据中序遍历的顺序，对于任一结点，优先访问其左孩子，而左孩子结点又可以看做一个根结点，然后继续访问其左孩子结点，直到遇到左孩子结点为空的结点才停止访问，然后按相同的　　规则访问其右子树。其处理过程如下：

对于任一结点：

a. 若其左孩子不为空，则将p入栈，并将p的左孩子设置为当前的p，然后对当前结点再进行相同的操作；

b. 若其左孩子为空，则取栈顶元素并进行出栈操作，访问该栈顶结点，然后将当前的p置为栈顶结点的右孩子；

c. 直到p为空并且栈为空，则遍历结束。

int NoInOrderTraverse(BiTree t)
{
    SqStack s;
    InitStack(&s);
     
    BiTree tmp = t;
    if(tmp == NULL)
    {
        fprintf(stderr, "the tree is null.
");
        return ERROR;
    }
 
    while(tmp != NULL || (IsEmpty(&s) != 1))
    {
        while(tmp != NULL)
        {
            Push(&s, tmp);
            tmp = tmp->lchild;
        }
 
        if(IsEmpty(&s) != 1)
        {
            Pop(&s, &tmp);
            printf("%c ", tmp->data);
            tmp = tmp->rchild;
        }
    }
    return OK;
}

二叉树的后续非递归遍历

　　后序遍历的非递归实现是三种遍历方式中最难的一种。因为在后序遍历中，要保证左孩子和右孩子都已被访问，并且左孩子在右孩子之前访问才能访问根结点，这就为流程控制带来了难　　题。下面介绍一种思路。

要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点p，先将其入栈。若p不存在左孩子和右孩子，则可以直接访问它，或者p存在左孩子或右孩子，但是其左孩子和右孩　　子都已经被访问过了，则同样可以直接访问该结点。若非上述两种情况，则将p的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候，左孩子在右孩子之前别访问，左孩子和右　　孩子都在根结点前面被访问。

int NoPostOrderTraverse(BiTree t)
{
    SqStack s;
    InitStack(&s);
 
    BiTree cur;     //当前结点  
    BiTree pre = NULL;      //前一次访问的结点
    BiTree tmp;
 
    if(t == NULL)
    {
        fprintf(stderr, "the tree is null.
");
        return ERROR;
    }
 
    Push(&s, t);
    while(IsEmpty(&s) != 1)
    {
        GetTop(&s, &cur);//
        if((cur->lchild == NULL && cur->rchild == NULL) || (pre != NULL && (pre == cur->lchild || pre == cur->rchild)))
        {
            printf("%c ", cur->data);    //如果当前结点没有孩子结点或者孩子结点都已被访问过
            Pop(&s, &tmp);
            pre = cur;
        }
        else
        {
            if(cur->rchild != NULL)
            {
                Push(&s, cur->rchild);
            }
            if(cur->lchild != NULL)
            {
                Push(&s, cur->lchild);
            }
        }
    }
    return OK;
}

------------------------------------------------------------------------------------

二叉树的层序遍历

按照从根结点到叶结点、从左子树到右子树的次序访问二叉树的结点，具体思路如下：

A. 初始化一个队列，并把根结点入队列；

B. 当队列为非空时，循环执行步骤3到步骤5，否则执行步骤6；

C. 出队列取得一个结点，访问该结点；

D. 若该结点的左子树为非空，则将该结点的左子树入队列；

E. 若该结点的右子树为非空，则将该结点的右子树入队列；

F. 结束。

int TraverseBiTree(BiTree t)
{
    LinkQueue q;
    InitQueue(&q);
     
    BiTree tmp = t;
    if(tmp == NULL)
    {
        fprintf(stderr, "the tree is null.
");
        return ERROR;
    }
 
    InsertQueue(&q, tmp);
    while(QueueIsEmpty(&q) != OK)
    {
        DeQueue(&q, &tmp);
        printf("%c ", tmp->data);
        if(tmp->lchild != NULL)
        {
            InsertQueue(&q, tmp->lchild);
        }
        if(tmp->rchild != NULL)
        {
            InsertQueue(&q, tmp->rchild);
        }
    }
 
    return OK;
}

------------------------------------------------------------------------

创建二叉树

//创建树
//按先后次序输入二叉树中结点的值(一个字符),#表示空树
//构造二叉链表表示的二叉树
BiTree CreateTree(BiTree t)
{
    char ch;
    scanf("%c", &ch);
 
    if(ch == '#')
    {
        t = NULL;
    }
    else
    {
        t = (BitNode *)malloc(sizeof(BitNode));
        if(t == NULL)
        {
            fprintf(stderr, "malloc() error in CreateTree.
");
            return;
        }
 
        t->data = ch;                        //生成根结点
        t->lchild = CreateTree(t->lchild);    //构造左子树
        t->rchild = CreateTree(t->rchild);    //构造右子树
    }
    return t;
}

-------------------------------------------------------------------------------------------

二叉树的深度

int BiTreeDeep(BiTree t)
{
    int dept = 0;
     
    if(t)
    {
        int lchilddept = BiTreeDeep(t->lchild);
        int rchilddept = BiTreeDeep(t->rchild);
 
        dept = lchilddept >= rchilddept ? (lchilddept + 1) : (rchilddept + 1);
    }
 
    return dept;
}