成长随心记19（二叉树的先中后遍历和层次遍历）

数据结构--树

1，基本术语
    1）度：节点有几个孩子叫做几度
    2）树的度：各节点中度的最大值
    3）有序树：各节点从左至右都是有次序的
2）树的性质
    1）节点数=总度数+1
    2）树的度（度为m的树）--各节点的度的最大值
         任意节点的度<=m，至少有一个节点度为m，一定是非空树，至少有m+1个节点
    3）m叉树--每个节点最多只能有m个孩子的树
        任意节点的度<=m，最多m个孩子，允许所有节点的度都<m，可以是空树
    4）度为m的树第i层至多有m的i-1个节点

3）二叉树
    1）满二叉树特点：
        只有最后一层有叶子节点
        不存在度为1的点
        按层序编号，节点i的左孩子为2i，右孩子为2i+1，节点为i的父节点为i/2
    2）完全二叉树特点：
        只有最后两层可能有叶子
        最多只有一个度为1的点
         按层序编号，节点i的左孩子为2i，右孩子为2i+1，节点为i的父节点为i/2
        in/2为叶子节点
    3）二叉排序树特点：
        左子树上所有节点的关键字都小于根节点的关键字
        左子树和右子树又各是一颗二叉排序树
    4）平衡二叉树：
        左子树和右子树的深度相差小于1

4）二叉树的先中后遍历和层次遍历

#include typedef struct tree {//树节点    struct tree* lchild;//指向左孩子的指针    struct tree* rchild;//指向右孩子的指针    int data;//数据域}tree,*bitree;//tree表示这是一个节点，bitree表示这是一颗树tree* create() {//创建一颗树    bitree T;    int val;    cin >> val;    if (val == -1)//如果等于-1，返回上一节点，停止往下递归        return NULL;    else {        T = new tree;//T指向根节点        T->data = val;//给根节点赋值val        cout <lchild = create();//向左递归，创建左子树        cout <rchild = create();//向右递归，创建右子树    }    return T;}void showleft(bitree T) {//左根遍历-根左右    if (T == NULL)//递归遇到null，返回上一节点        return;    cout <data <lchild);//遍历左孩子    showleft(T->rchild);//遍历右孩子}void showmid(bitree T) {//中根遍历-左根右    if (T == NULL)//递归遇到null，返回上一节点        return;    showmid(T->lchild);//遍历左孩子    cout <data <rchild);//遍历右孩子}void showright(bitree T) {//右根遍历-左右根    if (T == NULL)//递归遇到null，返回上一节点        return;    showright(T->lchild);//遍历左孩子    showright(T->rchild);//遍历右孩子    cout <data << ' ';}void leveshow(bitree T) {//层序遍历    queueq;    bitree tmp;    q.push(T);//将根节点入队    while (!q.empty()) {//如果队列为空跳出循环        tmp = q.front();//用tmp保留出队的节点        q.pop();        cout <data;//打印根节点        if (tmp->lchild != NULL)//如果左孩子不为空，则入队            q.push(tmp->lchild);        if (tmp->rchild == NULL)//如果右孩子不为空，则入队            q.push(tmp->rchild);    }}