樹與二叉樹——前序、中序、後序遞歸周遊，層序周遊

二叉樹的結構定義：

#define MAXSIZE 100

typedef char dataType;
struct TreeNode{
    dataType data;
    TreeNode *left, *right;
};
           

建立二叉樹：

//輸入示例：AB##C##
//建立二叉樹
//以先序序列輸入各節點的資料，某節點的左子樹或右子樹為空時，輸入一個特殊的值 x
void createTree(TreeNode *&t, dataType x){
    dataType d;
    scanf("%c", &d);
    if(d == x){
        t = NULL;
    }else{
        t = (TreeNode *)malloc(sizeof(TreeNode));
        t-> data = d;
        createTree(t-> left, x);
        createTree(t-> right, x);
    }
}
           

前序遞歸周遊二叉樹：

void preOrder(TreeNode *root)
{
    if (root == NULL)//遞歸調用的結束條件
        return;
    else
    {
        printf("%c ", root->data);
        preOrder(root->lchild);
        preOrder(root->rchild);
    }
}

           

中序遞歸周遊二叉樹：

void inOrder(TreeNode *root)
{
    if (root == NULL)//遞歸調用的結束條件
        return;
    else 
    {
        inOrder(root->lchild);
        printf("%c ", root->data);
        inOrder(root->rchild);
    }
}

           

後序遞歸周遊二叉樹：

void postOrder(TreeNode *root)
{
    if (root == NULL) //遞歸調用的結束條件
        return;
    else
    {
        postOrder(root->lchild);
        postOrder(root->rchild);
        printf("%c ", root->data);
    }
}
           

層序遞歸周遊二叉樹：

層序周遊算法：
    在進行層序周遊時，通路某一層的結點後，再對各個結點的左孩子和右孩子順序通路。
    這樣一層一層周遊，向通路的結點其左右孩子也要先周遊，這符合隊列的操作特性。
    是以，在進行層序周遊時，設定一個隊列存放已通路的結點。


void levelOrder(TreeNode *root)
{
    TreeNode *q = NULL;//建立工作指針
    TreeNode *Queue[MAXSIZE];//建立存放根節點的順序隊列
    int front;//隊頭
    int rear;//隊尾
    front = rear = -1;
    if (root == NULL)//判斷是否為空樹 
    {
        return;
    }
    Queue[++rear] = root;//跟結點入隊
    while (front != rear)
    {
        q = Queue[++front];//根節點出隊
        printf("%c ", q->data);
        if (q->left) 
        {
            Queue[++rear] = q->left;//左子樹入隊
        }    
        if (q->right)
        {
            Queue[++rear] = q->right;//右子樹入隊
        }
    }
}