队列使用--树的层次遍历

树
一 . 结构
1.双亲表示：数据域和双亲在数组中的位置
typedef struct{
char data;
int parent;
}TNODE;
TNODE t[M];

2.孩子表示法：结点包含指向孩子的指针（个数为树的度），
typedef stru treenode{
type data;
struct treenode * sons[MAXSONS];// MAXSONS为树的度
}TNODE;

3.孩子兄弟表示法：
也叫二叉树表示法或者二叉链表表示法，左指针指向该结点的第一个孩子，右指针指向该结点的下一个兄弟
typedef struct tnode{
type data;
struct tnode *lchild;
struct tnode *lright;
}TNODE;

二 .二叉树：
度最大为2
子树有左右，不能颠倒
可以为空

特殊的二叉树：
满二叉树：深度为k，有2^k-1个结点
完全二叉树：有n个结点，与满二叉树的编号为1~n的结点对应

二叉树的特点：
1.深度为k最多有2**k-1个结点
2.i层有2**i个结点
3.终端结点数n0是度为2的结点数n2的关系n0=n2+1
4.n个结点的完全二叉树的深度为|log 2 n| + 1；
5.n个结点的二叉树，对任一结点i（1 <= i <= n ）
有： i=1： 结点i为根，无双亲
i>1: 双亲是[i/2]

2i > n: 结点i无左孩子
2i <=n: 结点i的左孩子是2i

2i+1>n: 结点i无右孩子
2i+1>=n: 结点i的右孩子是2i+1

二叉树的存储：
1.顺序存储：适用于完全二叉树，数组的下标和结点的编号对应
2.链式存储：左右孩子结点指针；如果有n个结点，则适用n-1个指针，有n+1个指针没有使用
还可以使用三叉链表：
在二叉链表基础上增加一个指向父亲的指针

3.遍历：前序，中序，后序，层次：

看看层次：
//使用的是
/*
typedef struct tnode{
type data;
struct tnode *lchild;
struct tnode *lright;
}TNODE;
*/
void levelorder(JD *t)
{
    JD *q[20]; //辅助队列
    int front=0, rear=0;
    if(NULL != t)
    {
        rear++;
        q[rear] = t;//根入队；
     }
    while(front != rear)
     {
            front++;
            t = q[front];
            printf("%d\n" , t->data);
            if(t -> lchild != NULL)
            {
                rear++;
                q[rear] = t->lchild;
            }

            if(t -> rchild != NULL)
            {
                rear++;
                q[rear] = t->rchild;
            }
      }
}

增加的一个辅助队列，存放从根开始，从左到右往下的结点地址，每访问一个结点，将结点的子结点存放在队尾。
实用中要注意数组大小并增加越界检查。