C 指標筆記（五）：資料結構應用——循環佇列與二元樹遍歷

循環佇列（環狀緩衝區）

#define QSIZE 8
typedef struct {
    int front, rear, count;
    int data[QSIZE];
} CirQueue;

void Init(CirQueue *q) { q->front = q->rear = q->count = 0; }

int IsFull(CirQueue *q)  { return q->count == QSIZE; }
int IsEmpty(CirQueue *q) { return q->count == 0; }

int Enqueue(CirQueue *q, int val) {
    if (IsFull(q)) return 0;
    q->data[q->rear] = val;
    q->rear = (q->rear + 1) % QSIZE;
    q->count++;
    return 1;
}

int Dequeue(CirQueue *q, int *out) {
    if (IsEmpty(q)) return 0;
    *out = q->data[q->front];
    q->front = (q->front + 1) % QSIZE;
    q->count--;
    return 1;
}

二元樹三種遞歸遍歷

typedef struct Node {
    char data;
    struct Node *left, *right;
} Node;

Node *Create() {
    char ch = getchar();
    if (ch == '*') return NULL;
    Node *n = malloc(sizeof(Node));
    n->data = ch;
    n->left  = Create();
    n->right = Create();
    return n;
}

void PreOrder(Node *t)  { if (t) { visit(t); PreOrder(t->left); PreOrder(t->right); } }
void InOrder(Node *t)   { if (t) { InOrder(t->left); visit(t); InOrder(t->right); } }
void PostOrder(Node *t) { if (t) { PostOrder(t->left); PostOrder(t->right); visit(t); } }

void visit(Node *t) { printf("%c ", t->data); }

指標在資料結構中的角色

• 佇列：front/rear 為陣列索引，配合取模實現環狀；
• 鏈表/樹：指標直接串聯節點，動態配置記憶體；
• 遞歸函數隱式使用呼叫堆疊，指標傳遞節點位址。