#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;
版权属于:
lixiangrong
作品采用:
《
署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)
》许可协议授权
评论 (0)