数据结构第三周笔记——树(上)(慕课浙大版本--XiaoYu)（三）

1.从结点访问其左、右儿子结点
2.访问左儿子后，右儿子结点怎么办？
  1.需要一个存储结构保存暂时不访问的结点
  2.存储结构：堆栈、队列

遍历从根结点开始，首先将根结点入队，然后开始执行循环：结点出队、访问该结点、其左右儿子入队

//代码实现
void LevelOrderTraversal(BinTree BT)
{
    Queue Q; BinTree T;
    if(!BT) return;//若是空树直接返回
    Q = CreateQueue(MaxSize);//创建并初始化队列Q
    AddQ(Q,BT);//把BT这个根节点放到Q这个队列里
    while(!IsEmptyQ(Q)){
        T = DeleteQ(Q);//抛出元素赋给T就是一个指针
        printf("%d\n",T->Data);//访问去除队列的结点
        if(T->Left) Add(Q,T->Left);//左右儿子放到队列里去
        if(T->Right) AddQ(Q,T->Right);
    }
}

void PreOrderPrintLeaves(BinTree BT)
{
    if(BT){
        if(!BT-Left && !BT->Right)
            printf("%d",BT->Data);
        PreOrderPrintLeaves(BT -> Left);
        PreOrderPrintLeaves(BT -> Right);
    }
}

void PreOrderGetHeight(BinTree BT)
{
    int HL,HR,MaxH
    if(BT){
        HL = PostOrderGetHeight(BT->Left);//求左子树的深度，这两个都是递归哦
        HR = PostOrderGetHeight(BT->Right);//求右子树的深度
        MaxH = (HL > HR) ? HL :HR;//取左右子树较大的深度
        return (MaxH + 1);//返回树的深度
    }
    else return 0;//空树深度为0
}

静态链表数组实现代码
    #define MaxTree 10
    #define ElementType char
    #define Tree int
    #define Null -1
    struct TreeNode
    {
        ElementType Element;
        Tree Left;//这里Left跟Right不是指针
        Tree Right;
    }T1[MaxTree],T2[MaxTree];//NULL在C语言这个stdlb.h中定义是0
//静态链表优势：有链表的灵活性，但他的存储又是在数组上面

int main()
{
    建二叉树1
    建二叉树2
    判别是否同构并输出
        return 0;
}
需要设计的函数：
    1.读数据建二叉树
    2.二叉树同构判别
    怎么判别二叉树是不是同构的代码实现
    int main()
{
    Tree R1,R2;
    R1 = BuildTree(T1);//建第一棵树R1
    R2 = BuildTree(T2);//建第二课树R2
    if(Isomorphic(R1,R2)) printf("Yes\n");//判断二叉树是不是同构的
    else printf("No\n");
    return 0;
}

最后if(!check[i]) break;中返回的值是0的就是根结点，因为有指向的都被转化为1了
T[i].Left = cl - '0';的原因是我们是以字符的形式读取进来的，字符2减去字符0就是整数2