写这篇纯属个人兴趣了😂 要遍历二叉树的话优先推荐用递归的方法 在传统的遍历二叉树时,如果要使用递归的方法 前序遍历: void FrontOrder(biTree *s) { if(s){ printf("%d",s->data); FrontOrder(s->lchild); FrontOrder(s->rchild); } } 中序遍历: void InOrder(biTree *s) { if(s){ InOrder(s->lchild); printf("%d",s->data); InOrder(s->rchild); } } 后续遍历: void PostOrder(biTree *s) { if(s){ PostOrder(s->lchild); PostOrder(s->rchild); printf("%d",s->data); } } 用栈的话👇,话不多说,上代码 #include <stdio.h> #define maxsize 24 typedef struct node{ char data; struct node *lchild; struct node *rchild; }biTree; biTree * Q[maxsize]; biTree * Creat(){ char ch; int front,rear; biTree *root,*s; root = NULL; // ---------- front = 1; rear = 0; // ----------置空队列 ch = getchar(); while(ch!='#'){ s = NULL; if(ch!='@'){ s = (biTree*)malloc(sizeof(biTree)); s->data = ch; s->lchild = NULL; s->rchild = NULL; } rear ; Q[rear] = s; if(rear==1)root = s; else{ if(s&&Q[front]) { if(rear%2==0)Q[front]->lchild = s; else Q[front]->rchild = s; } if(rear%2==1)front ; } ch = getchar(); } return root; } typedef struct { biTree data[maxsize]; int top; }seq; void setnull(seq *s) { s->top = -1; } seq *PUSH(seq *s,biTree x) { if(s->top==maxsize-1){ printf("overflow\n"); return (NULL); } else{ s->top ; s->data[s->top] = x; } return s; } int empty(seq *s) { if(s->top>=0)return 0; else return 1; } biTree POP(seq *s) { biTree *emp = NULL; if(empty(s)){ printf("underflow.\n"); return *emp; } else{ s->top--; return (s->data[s->top 1]); } } biTree *top(seq *s) { biTree *emp = NULL; if(empty(s)){ printf("stack is empty.\n"); return emp; } else return (&s->data[s->top]); } void inOrder(biTree *t) { biTree *root = t; seq s; setnull(&s); if(t) { while(root||!empty(&s)){ while(root) { PUSH(&s, *root); root = root->lchild; } if(!empty(&s)) { printf("%c ",s.data[s.top].data); root = top(&s); root = root->rchild; POP(&s); } } } } int main() { biTree *root = Creat(); inOrder(root); printf("\n"); return 0; } 解释一下函数的运行过程 void inOrder(biTree *t) { biTree *root = t; seq s; setnull(&s); if(t) { while(root||!empty(&s)){ while(root) { PUSH(&s, *root); root = root->lchild; } if(!empty(&s)) { printf("%c ",s.data[s.top].data); root = top(&s); root = root->rchild; POP(&s); } } } } 1、当节点 t 非空的话读如二叉树 2、如果当前节点不为 “空或者栈非空” 开始循环 3、内部循环: 当前节点非空时,把当前节点压入栈,然后一直找到它的左孩子为空 找完左孩子,开始你要进行的操作 当栈非空时,输出当前节点的数据 根结点指向右孩子,根结点出栈 4、下一步就开始找右孩子的左子树,开始下一步循环直到栈空并且当前节点为NULL 大家也可以自己搜索流程图辅助理解
来源:https://www./content-4-559501.html |
|