树(Tree)——(二)链式存储

用代码实现前序、中序、后序，第一种方法就是使用递归，另一种是使用栈。将分别讲述。

目录

1. 递归实现

main函数（C语言版本）

2. 利用栈实现

mystack.h

mystack.cpp

main函数

3.补充：求树高度的函数

---

 

 

1. 递归实现

main函数（C语言版本）

#include <stdio.h>

#if 0  //如下图示意图的树
                  a1
         b2             c3
     d4     e5              f6

前中后序如下
preOrder : 1 2 4 5 3 6 中左右
midOrder : 4 2 5 1 3 6 左中右
postOrder: 4 5 2 6 3 1 左右中;

#endif
//先中后，三种遍历的方式，本质是压栈顺序是没有什么不同的，
//所谓先中后，无非是访问根节点的时机不同而已。

typedef struct _TreeNode  //二叉树的结构体
{
        int _data;
        struct _TreeNode *_left;
        struct _TreeNode *_right;
}TreeNode;


void preOrderTraverse(TreeNode* r)  //先序遍历
{
    if(r)
    {
        printf("%d ",r->_data);            //根左右
        preOrderTraverse(r->_left);   //递归,每个节点,都是独立的树,需要再次先序遍历,代码较少,但是思考是需要些时间的
        preOrderTraverse(r->_right);
    }
}

void middleOrderTraverse(TreeNode* r)  //中序遍历
{
    if(r)
    {
        middleOrderTraverse(r->_left);   //左根右
        printf("%d ",r->_data);
        middleOrderTraverse(r->_right);
    }
}

void postOrderTraverse(TreeNode* r)  //后序遍历
{
    if(r)
    {
        postOrderTraverse(r->_left);   //左右根
        postOrderTraverse(r->_right);
        printf("%d ",r->_data);
    }
}

int main()
{
    TreeNode a,b,c,d,e,f;    //画树
    TreeNode * root = &a;
    a._data=1;b._data=2;c._data=3;
    d._data=4;e._data=5;f._data=6;
    a._left=&b;a._right=&c;
    b._left=&d;b._right=&e;
    c._left=NULL; c._right=&f;
    d._left=d._right=e._left=e._right=f._left=f._right=NULL;

    preOrderTraverse(root);
    putchar(10);
    middleOrderTraverse(root);
    putchar(10);
    postOrderTraverse(root);
    return 0;
}

 

2. 利用栈实现

这里需要栈的定义和函数

mystack.h

#include<stdio.h>
#include<stdlib.h>
typedef struct _TreeNode
{
        int _data;
        struct _TreeNode *_left;
        struct _TreeNode *_right;
}TreeNode;

typedef struct _Node
{
        TreeNode* data;  //变量改成TreeNode*
        struct _Node* next;
}Node;

typedef struct _Stack
{
        Node* top;
}Stack;

void initStack(Stack *s);         //先初始化
int isStackEmpty(Stack *s);//判断是否为空
void push(Stack *s, TreeNode *ch); //往里压
TreeNode* pop(Stack *s);                //往外弹
void resetStack(Stack*s);      //复位
void destroyStack(Stack*s);  //销毁

mystack.cpp

#include"mystack.h"
void initStack(Stack *s)         //初始化
{
    s->top=(Node*)malloc(sizeof(Node)); 
    s->top->next=NULL;
}

int isStackEmpty(Stack *s)//判断是否为空
{
    return s->top->next==NULL; 
}

void push(Stack *s, TreeNode* ch) //往里压
{
    Node *cur=(Node*)malloc(sizeof(Node));
    cur->data=ch;
    cur->next=s->top->next;    //链表的头插法
    s->top->next=cur;
}

TreeNode * pop(Stack *s)                //往外弹
{
    Node*t=s->top->next;       //找一个替身
    s->top->next=t->next;       //把头节点后面的首节点拿下来，实现先进后出，后进先出
    TreeNode * ch;
    ch=t->data;               //因为要释放 t ,而且需要返回char，所以创建个变量记录下
    free(t);
    return ch;
}

void resetStack(Stack*s)  //复位
{
    while(!isStackEmpty( s))//一直弹出就行，pop函数里已经有释放
        pop(s);
}

void destroyStack(Stack*s)  //销毁
{
    resetStack(s);
    free(s->top);
}

 

main函数

#include <stdio.h>
#include"mystack.h"

#if 0
                  a1
         b2             c3
     d4     e5              f6

前中后序如下
preOrder : 1 2 4 5 3 6 中左右
midOrder : 4 2 5 1 3 6 左中右
postOrder: 4 5 2 6 3 1 左右中;

#endif

//非递归形式，迭代循环，使用栈
void preOrderIterator(TreeNode * r) //先序
{
    if(r)
    {
        Stack s;
        initStack(&s);
        while (r || !isStackEmpty(&s)) // r 不为空即或者栈内不为空
        {
            while (r)  //若 r 不为空，则一直指向左节点，给左节点压栈，直到左节点为空
            {
                printf("%d ",r->_data);
                push(&s,r);
                r=r->_left;
                //压栈
            }
            r=pop(&s);  //左节点为空，则弹出，判断是否存在右节点，若有则继续判断左节点
            r=r->_right;
            //出栈
        }
    }
}

void midOrderIterator(TreeNode * r) //中序
{
    if(r)
    {
        Stack s;
        initStack(&s);
        while (r || !isStackEmpty(&s))
        {
            while (r)
            {
                push(&s,r);
                r=r->_left;
                //压栈
            }
            r=pop(&s);
            printf("%d ",r->_data);  //实际就是改变打印输出顺序
            r=r->_right;
            //出栈
        }
    }
}

void postdOrderIterator(TreeNode * r) //后序，逻辑较复杂
{
    if(r)
    {
        Stack s;
        initStack(&s);
        TreeNode *cur; //当前结点
        TreeNode *pre=NULL; //前一次访问的结点
        push(&s,r);
        while(!isStackEmpty(&s))
        {
            cur = pop(&s);    
            push(&s,cur);  //这一步实际上就是在拿取栈顶的节点，来判断此节点的左右是否有子节点。
            if((cur->_left==NULL&&cur->_right==NULL)||
               (pre!=NULL&&(pre==cur->_left||pre==cur->_right)))
            {
                //如果当前结点没有子结点或者子节点都已被访问过
                printf("%d ",cur->_data);
                pop(&s);
                pre=cur;
            }
            else
            {
                if(cur->_right != NULL)
                    push(&s,cur->_right);
                if(cur->_left != NULL)
                    push(&s,cur->_left);
            }
        }
    }
}
int main()
{
    TreeNode a,b,c,d,e,f;    //画树
    TreeNode * root = &a;
    a._data=1;b._data=2;c._data=3;
    d._data=4;e._data=5;f._data=6;
    a._left=&b;a._right=&c;
    b._left=&d;b._right=&e;
    c._left=NULL; c._right=&f;
    d._left=d._right=e._left=e._right=f._left=f._right=NULL;


    preOrderIterator(root);
    putchar(10);
    midOrderIterator(root);
    putchar(10);
    postdOrderIterator(root);
    return 0;
}

3.补充：求树高度的函数

int getHeightByPostOrder(TreeNode  * t)
{
    int lH, rH, maxH;
    if(t)
    {
        lH = getHeightByPostOrder(t->_left); //求左右高度，然后取出最大的
        rH = getHeightByPostOrder(t->_right);
        maxH = (lH>rH)?lH:rH;
        return maxH +1;
    }
    else
        return 0;
}