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

  二叉树T:一个有穷的结点集合
​   这个集合可以为空
    若不为空，则它是由根结点和称为其左子树TL和右子树TR的两个不相交的二叉树组成(L和R是下标)

有n个结点的二叉树，对树种结点按从上到下，从左到右的顺序进行编号，编号为i(1 <= i <= n)结点与满二叉树中编号为i结点在二叉树中位置相同
跟上方的区别就是除了最底下一层可以右边缺一点，上面跟满二叉树是一样的。最底下一层左边顺序不能乱

有一颗二叉树，其两个儿子的结点个数为15个，一个儿子的结点个数为32个，问该二叉树的叶结点个数是多少？
16

类型名称：二叉树
数据对象集：一个有穷的结点集合。
  若不为空，则由根结点和其左、右二叉子树组成。
操作集： BT属于BinTree,Item属于ElementType
重要操作有：
1.Boolean IsEmpty(BinTree BT)：判别BT是否为空;
2.void Traversal(BinTree BT)：遍历，按某顺序访问每个结点;(重要)
3.BinTree CreateBinTree():创建一个二叉树

1.void PreOrderTraversal(BinTree BT)://先序--根、左子树、右子树
2.void InOrderTraversal(BinTree BT)://中序--左子树、根、右子树
3.void PostOrderTraversal(BinTree BT)://后序--左子树、右子树、根
4.void LevelOrderTraversal(BinTree BT)://层次遍历(层序遍历,从上到下、从左到右

完全二叉树：按从上至下，从左到右顺序存储n个结点的完全二叉树的结点父子关系;
//这个树最适合数组方式解决

问题：
如果参照完全二叉树的表示方法用数组存储下面这棵二叉树，那么结点e所对应的数组下标是多少（树根下标为1）？
答案：6

typedef struct TreeNode *BinTree;
typedef BinTree Position;
struct TreeNode{
    ElementType Data;
    BinTree Left;
    BinTree Right;
}

遍历过程为：
1.访问根节点
2.先序遍历其左子树
3.先序遍历其右子树 
对应的递归程序：
void PreOrderTraversal(BinTree BT)//BT是树
{
    if( BT ){//看树是不是空的，空的就退出去，不空就访问根节点
        printf("d",BT->Data);
        PreOrderTraversal(BT->Left);//指向左子树的那个根节点的地址进行递归
        PreOrderTraversal(BT->Right);//指向右子树的那个根节点的地址进行递归
    }
}

先是从根开始  A(B D F E)(C G H I)
先序遍历=>A B D F E C G H I

遍历过程为：
1.中序遍历其左子树
2.访问根结点;
3.中序遍历其右子树 
对应的递归程序：
void PreOrderTraversal(BinTree BT)//BT是树
{
    if( BT ){//看树是不是空的，空的就退出去，不空就访问根节点
        PreOrderTraversal(BT->Left);//指向左子树的那个根节点的地址进行递归
        printf("d",BT->Data);
        PreOrderTraversal(BT->Right);//指向右子树的那个根节点的地址进行递归
    }
}

中序遍历 => D B E F A G H C I
(D B E F) A ( G H C I)
先是左边再右边，这里我原本的疑问是为什么是先E在F而不是先F再E
原因是E-F是一个树，然后因为这个是左子树，所以从左边开始，E在F的左边

遍历过程为：
1.后序遍历其左子树
2.中序遍历其右子树 
3.访问根结点
对应的递归程序：
void PreOrderTraversal(BinTree BT)//BT是树
{
    if( BT ){//看树是不是空的，空的就退出去，不空就访问根节点
        PreOrderTraversal(BT->Left);//指向左子树的那个根节点的地址进行递归
        PreOrderTraversal(BT->Right);//指向右子树的那个根节点的地址进行递归
        printf("d",BT->Data);
    }
}

注意点：后序遍历，那当然得从下面开始咯，所以会发现B跟E是E优先。H跟C比是H优先
 (D E F B)(H G I C) A
 后序遍历 => D E F B H G I C A

先序、中序和后序遍历过程：遍历过程中经过结点的路线一样，只是访问各结点的时机不同
图中先从入口到出口的曲线上用三种符号分别标记除先序，中序和后序的访问各结点时刻

1.遇到一个结点，就把它压栈，并去遍历它的左子树;
2.当左子树遍历结束后，从栈顶弹出这个结点并访问它;
3.然后按其右指针再去中序遍历该结点的右子树
以下是完整代码实现演示
void InOrderTraversal(BinTree BT)
{
    BinTree T = BT;//把BT赋给临时变量T
    Stack S = CreateStack(MaxSize);//创建并初始化堆栈
    while(T || !IsEmpty(S) ){//树不空且堆栈不空
        while(T){//判断堆栈空不空
            //一直向左并将沿途结点压入堆栈
            Push(S,T);//把T压入堆栈S中
            T = T->Left;//然后把T往左挪，就是边挪边把结点压到堆栈里面去，压到底T为NULL就退出来
        }
        if(!IsEmpty(S)){
            T = Pop(S);//结点弹出堆栈
            printf("%5d",T->Data);//(访问)打印结点
            T = T->Right;//转向右子树
        }
    }
}
ppoopoppoo错误
PPOPOOPPOO正确
    第二次碰到同一个的时候就print出来