二叉树的存储结构以及遍历

二叉树顺序存储

#define Maxsize 100
struct typedef{
    Elemtype value; //结点中的数据元素 
    bool isEmpty;//结点是否为空 
}; 

TreeNode t[Maxsize];

定义一个长度为Maxsize的数组t，从上到下，从左到右的顺序
结构存储完全二叉树中的各个节点.

**二叉树的链式存储**

typedef struct BiTNode{
    Elemtype data;
    struct BiTNode *lchild,*rchild;

}BiTNode,*BiTree;

//定义一颗空树
BiTree root == NULL;
//插入根结点
root = (BiTree) malloc(sizeof(BiTNode)) ;
root->data = {1};
root->lchild = NULL;
root->rchild = NULL;

//插入新结点 
BiTNode *p =(BiTNode) malloc (sizeof(BiTNode));
p->data = {2};
p->lchild = NULL;
p->rchild = NULL;
root->lchild = p;//作为根节点的左孩子 

先序遍历（根左右）
1.如果二叉树为空，则什么也不做
2.二叉树非空->访问根节点->先序遍历左子树->先序遍历右子树

typedef struct BiNode{
    Elemtype data;
    struct BiNode *lchild,*rchild;
}BiTNode,*BiTree;

//先序遍历
void PreOrder(BiTree T)
{
    if(T !=NULL)
    {
        visit(T); //访问根节点 
        PreOrder(T->lchild);//递归遍历左子树 
        PreOrder(T->rchild);//递归遍历右子树 
    }
 } 

//中序遍历
void PreOrder(BiTree T)
{
    if(T !=NULL)
 {
    PreOrder(T->lchild);
    visit(T);
    PreOrder(T->rchild;)
 }
 } 

//后序遍历
void PreOrder(BiTree T)
{
    if(T !=NULL)
 {
    PreOrder(T->lchild);
    PreOrder(T->rchild); 
    visit(T);
 }
 } 

层次遍历
算法思想
1.初始化一个辅助队列
2.根节点入队
3.若队列非空，则队头结点出队，访问该结点，并将其左右孩子插入队尾
4.重复3直到队空

typedef struct BiNode{
    Elemtype data;
    struct BiNode *lchild,*rchild;
}BiTNode,*BiTree;

typedef struct LinkNode{
    BiTNode *data; //存指针而不是结点会节省很多空间
    struct LinkNode *next; 
}LinkNode;

typrdef struct{
 LinkNode *front,*rear; //队头队尾 
}LinkQueue;

void LevelOrder(BiTree T){
    LinkQueue Q;
    InitQueue(Q);
    BiTree p;
    EnQueue(Q,T); //根节点入队
    while(!EmptyQueue(Q)) //队列不空则循环 
    {
        DeQueue(Q,p); //队头结点出队 
        visit(p);
        if(T->lchild != NULL) EnQueue(Q,p->lchild); //左孩子入队 
        if(T->rchild != NULL) EnQueue(Q,p->rchild); //右孩子入队 


     } 
}