C语言数据结构二叉树的层序、先序、中序、后序遍历(完整代码)-创新互联

C语言数据结构二叉树的层序、先序、中序、后序遍历

先序、中序、后序遍历相似,区别在输出和递归顺序。

成都创新互联公司是一家以重庆网站建设公司、网页设计、品牌设计、软件运维、营销推广、小程序App开发等移动开发为一体互联网公司。已累计为户外休闲椅等众行业中小客户提供优质的互联网建站和软件开发服务。

层次遍历需要用到队列,原理是:把根节点入队,如果队列里不为空->出队输出 结点内容->如果左孩子不为空,入队;右孩子不为空,入队。在队不为空的条件下进行循环。

完整代码在下面,可以运行嗷

#include#includetypedef struct BiTNode
{char data;
    struct BiTNode *rchild,*lchild;
}BiTNode,*BiTree;

//队列的结构体 为层序遍历定义
typedef struct queue
{BiTNode arr[50]; //开50数组
    int front,rear;
}Queue;

//前序遍历输入二叉树
void creattree(BiTree *T)
{char ch;
    scanf("%c",&ch);
    if(ch=='#')
    {*T=NULL;
    }
    else
    {*T=(BiTree)malloc(sizeof(BiTNode));
        if(!*T)
            exit(0);
         (*T)->data=ch;
         creattree(&(*T)->lchild);
         creattree(&(*T)->rchild);
    }
}

//前序遍历
void pretra(BiTree T)
{if(T==NULL)
        return;
    printf("%c",T->data);
    pretra(T->lchild);
    pretra(T->rchild);
}

//中序遍历
void intra(BiTree T)
{if(T==NULL)
        return;
    intra(T->lchild);
    printf("%c",T->data);
    intra(T->rchild);
}

//后序遍历
void posttra(BiTree T)
{if(T==NULL)
        return;
    intra(T->lchild);
    intra(T->rchild);
    printf("%c",T->data);
}

void initequeue(Queue *q)
{q->front=0;
    q->rear=0;
}
int length(Queue *q)
{return ((q->rear-q->front)%50);
}

int enqueue(Queue *q,BiTNode e)
{if((q->rear+1)%50==q->front)   //判断队列是否满了
    return 0;

    q->arr[q->rear]=e;
    q->rear=(q->rear+1)%50;
    return 1;
}
BiTNode dequeue(Queue *q)
{if(q->rear==q->front)     //判断是否为空
        exit(0);

    BiTNode e;
    e=q->arr[q->front];
    q->front=(q->front+1)%50;
    return e;
}
//层序遍历    需要使用队列
void leveltra(BiTree T)
{if(T==NULL)
    return;

    Queue *Q=(Queue*)malloc(sizeof(Queue));
    initequeue(Q);
    enqueue(Q,*T);
    while (Q->front!=Q->rear)   //如果队列不为空
    {BiTNode x=dequeue(Q);
        printf("%c",x.data);
        if(x.lchild)
        {enqueue(Q,*x.lchild);
        }
        if(x.rchild)
        {enqueue(Q,*x.rchild);
        }
    }

}

int main()
{printf("请以前序顺序输入二叉树,以#隔开\n");
    BiTree T;
    creattree(&T);
    printf("前序输出二叉树\n");
    pretra(T);
    printf("层序输出二叉树\n");
    leveltra(T);
    return 0;
}

此代码是学习数据结构课的笔记,如有建议或错误,请留言哦。谢谢!

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


本文标题:C语言数据结构二叉树的层序、先序、中序、后序遍历(完整代码)-创新互联
URL链接:http://ybzwz.com/article/egcig.html