二叉树的非递归遍历和相关运算

二叉树的非递归遍历和相关运算

lixiangrong
2024-01-06 / 0 评论 / 7 阅读 / 正在检测是否收录...
#include <stdio.h>
#include <stdlib.h>

// 7.4.3 二叉树的非递归遍历
typedef char dataType;
typedef struct treeNode
{
    dataType data; // 数据域
    struct treeNode *lChild,*rChild; // 左、右孩子指针域
}node,*binaryTree;

// 顺序栈
#define MAX_SIZE 100
typedef struct stack
{
    node *data[MAX_SIZE]; // 栈中存放的是二叉树结点指针
    int top; // 栈顶指针
}seqStack;

// 顺序循环队列:用于层序(层次)遍历
typedef struct
{
    node *data[MAX_SIZE];
    int front,rear; // 队头、队尾指针
}queue;

// 1.栈初始化
void initStack(seqStack *stack)
{
    stack->top = 0;
}

// 2. 判断栈是否为空
int emptyStack(seqStack stack)
{
    return stack.top == 0;
}

// 3. 入栈
void push(seqStack *stack, node* n)
{
    if(stack->top == MAX_SIZE-1)
    {
        printf("栈已满,无法入栈!\n");
        exit(1);
    }
    stack->data[stack->top++] = n;
}

// 4. 读取栈顶元素
node *get(seqStack stack)
{
    return stack.data[stack.top-1];
}

// 5. 出栈
node* pop(seqStack *stack)
{
    if(emptyStack(*stack))
    {
        printf("栈已空,无法出栈!\n");
        exit(1);
    }
    return stack->data[--stack->top];
}

// 6.队列初始化
void initQueue(queue *q)
{
    q->front = q->rear = 0;
}

// 7.判断队列是否为空
int emptyQueue(queue q)
{
    return q.rear == q.front;
}

// 8.入队
void enQueue(queue *q, node *n)
{
    if((q->rear+1)%MAX_SIZE == q->front)
    {
        printf("队列满,无法入队!\n");
        exit(1);
    }
    q->data[q->rear] = n;
    q->rear = (q->rear + 1)%MAX_SIZE;
}

// 9.出队
node *deQueue(queue *q)
{
    if(emptyQueue(*q))
    {
        printf("队列为空,无法出队!\n");
        exit(1);
    }
    node *n = q->data[q->front];
    q->front = (q->front+1)%MAX_SIZE;
    return n;
}

// 10. 按照前序遍历的顺序创建一个二叉树
binaryTree createTree()
{
    binaryTree t;
    char c;
    if((c = getchar()) == '#')
        t = NULL;
    else
    {
        t = (node *) malloc(sizeof(node));
        t->data = c;
        t->lChild = createTree();
        t->rChild = createTree();
    }
    return t;
}

// 11. 非递归前序遍历
void preOrder(binaryTree t)
{
    seqStack stack; // 声明顺序栈
    stack.top = 0; // 初始化栈
    while (t || !emptyStack(stack)) // 树非空或栈非空
    {
        if(t) // 一路向左直到左孩子为空
        {
            printf("%c ",t->data); // 先访问根节点
            push(&stack,t);
            t = t->lChild; // 再访问左孩子
        } else
        {
            t = pop(&stack);
            t = t->rChild; // 再访问右孩子
        }
    }
}

// 12.非递归中序遍历
void inOrder(binaryTree t)
{
    seqStack stack; // 声明顺序栈
    stack.top = 0; // 初始化栈
    while (t || !emptyStack(stack))
    {
        if(t) // 一路向左直到左孩子为空
        {
            push(&stack,t);
            t = t->lChild;
        } else
        {
            t = pop(&stack);
            printf("%c ",t->data);
            t = t->rChild;
        }
    }
}

// 13.非递归后序遍历
void postOrder(binaryTree t)
{
    seqStack stack; // 声明顺序栈
    stack.top = 0; // 初始化栈
    node *r = NULL; // 记录最近访问的结点
    while (t || !emptyStack(stack))
    {
        if (t) // 一路向左直到左孩子为空
        {
            push(&stack,t); // 沿着根的左孩子依次入栈
            t = t->lChild;
        } else
        {
            t = stack.data[stack.top-1]; // 读取栈顶元素
            if(t->rChild && t->rChild != r) // 右孩子存在且未访问
                t = t->rChild; // 转向右孩子
            else
            {
                pop(&stack); // 出栈
                printf("%c ", t->data);
                r = t; // 记录最近访问的结点(关键步骤)
                t = NULL; // 结点访问后重置为空(关键步骤)
            }
        }
    }
}

// 14. 二叉树层次遍历
seqStack nodeStack;
void levelOrder(binaryTree t)
{
    if(!t)
    {
        printf("二叉树为空!\n");
        return;
    }
    queue q; // 声明队列
    initQueue(&q); // 初始化队列
    enQueue(&q,t); // 根节点入队
    initStack(&nodeStack);
    while (!emptyQueue(q)) // 队列非空
    {
        t = deQueue(&q);; // 出队并访问
        push(&nodeStack,t);
        printf("%c ",t->data);
        if(t->lChild) // 左孩子入队
            enQueue(&q,t->lChild);
        if(t->rChild) // 右孩子入队
            enQueue(&q,t->rChild);
    }
}

// 15. 非递归求二叉树层数(深度或高度)
int level(binaryTree t)
{
    queue q; // 声明队列
    initQueue(&q); // 初始化队列
    int level = 0, first = 0; // first指向每层最左侧结点
    if(!t) return 0;
    enQueue(&q,t); // 根结点入队
    while (!emptyQueue(q)) // 队列非空
    {
        if(first == q.front) // 当队首结点是某层的第一个结点时
        {
            level++; // 层数累加
            first = q.rear; // 更新first指针指向下一层的第一个结点位置
        }
        t = deQueue(&q); // 出队并将孩子结点入队
        if(t->lChild) // 左孩子入队
            enQueue(&q,t->lChild);
        if(t->rChild) // 右孩子入队
            enQueue(&q,t->rChild);
    }
    return level;
}

// 16.非递归求二叉树最大宽度
int width(binaryTree t)
{
    queue q; // 声明循环队列
    initQueue(&q); // 初始化队列
    int i = 1, width = 0, first = 0; // i初值为1,处理只有一个结点的树
    if(!t) return 0; // 树为空时
    enQueue(&q,t); // 根节点入队
    while (!emptyQueue(q)) // 队列非空时
    {
        if(first == q.front) // 当first指向每层第一个节点时
        {
            if(i > width) width = i; // 更新最大宽度
            first = q.rear; // 更新first指针
            i = 0; // 重置i,以计算该层宽度
        }
        t = deQueue(&q); // 元素出队
        i++; // 计算该层宽度
        if(t->lChild)
            enQueue(&q,t->lChild); // 左孩子入队
        if(t->rChild)
            enQueue(&q,t->rChild); // 右孩子入队
    }
    return width;
}

// 17.返回二叉树任意两结点p、q的共同祖先
node *seekAncestor(binaryTree t, node *p, node *q)
{
    seqStack s, s1; // 声明顺序栈
    initStack(&s), initStack(&s1); // 初始化栈
    node *r = NULL; // 记录最近访问的结点
    while (t || !emptyStack(s))
    {
        if (t) // 一路向左直到左孩子为空
        {
            push(&s,t); // 沿着根的左孩子依次入栈
            t = t->lChild;
        } else
        {
            t = get(s); // 读取栈顶元素
            if (t->rChild && t->rChild != r) // 右孩子存在且未访问
                t = t->rChild; // 转向右孩子
            else
            {
                pop(&s); // 出栈
                if (t == p || t == q)
                {
                    if (emptyStack(s1))
                        for (int i = s.top - 1; i >= 0; i--)
                            push(&s1, s.data[i]);
                    else break;
                }
                r = t; // 记录最近访问的结点(关键步骤)
                t = NULL; // 结点访问后重置为空(关键步骤)
            }
        }
    }
    while (!emptyStack(s))
    {
        t = pop(&s);
        for (int j = s1.top-1; j >= 0; j--)
            if(t == s1.data[j])
                return t;
    }
    return NULL;
}

int main()
{
    binaryTree t; // 声明二叉树
    printf("请输入结点,创建一颗二叉树,#表示空结点:\n");
    t = createTree(); // ABD#E##FG###C##
    printf("前序遍历\n");
    preOrder(t);
    printf("\n中序遍历\n");
    inOrder(t);
    printf("\n后序遍历\n");
    postOrder(t);
    printf("\n层序遍历\n");
    levelOrder(t);
    printf("\n树的高度为%d", level(t));
    node *p = nodeStack.data[2], *q = nodeStack.data[6], *n;
    n = seekAncestor(t,p,q);
    if(n) printf("\n结点%c和结点%c的共同祖先是%c",p->data,q->data,n->data);
    else printf("\n结点%c和结点%c没有共同祖先",p->data,q->data);
    printf("\n该二叉树的宽度为%d", width(t));
    return 0;
0

评论 (0)

取消