数据结构 - 二叉树

递归实现前中后序遍历

#include<stdio.h>
#include<stdlib.h>#define TElemType inttypedef struct BiTNode{TElemType data;struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
BiTNode root;void visit(TElemType& e){printf("%d",e);
}void Preorder(BiTree T,void(*visit)(TElemType& e)){if(T==NULL)return;else{visit(T->data);Preorder(T->lchild, visit);Preorder(T->rchild, visit);}
}void Inorder(BiTree T,void(*visit)(TElemType& e)){if(T==NULL)return;else{Preorder(T->lchild, visit);visit(T->data);Preorder(T->rchild, visit);}
}void Postorder(BiTree T,void(*visit)(TElemType& e)){if(T==NULL)return;else{Preorder(T->lchild, visit);Preorder(T->rchild, visit);visit(T->data);}
}int main( ){return 0;
}

非递归实现中序遍历

#include<stdio.h>
#include<stdlib.h>#define TElemType inttypedef struct BiTNode{TElemType data;struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
BiTNode root;void visit(TElemType& e){printf("%d",e);
}#define DataType BiTreetypedef struct{DataType *s;int t;int MAXNUM;
}SeqStack,*PSeqStack;
void push_seq(PSeqStack pastack,DataType x){if(pastack->t==pastack->MAXNUM-1)printf("\n Stack is full!");else pastack->s[++pastack->t]=x;
}PSeqStack createEmptyStack_seq(int m){PSeqStack stack = (PSeqStack)malloc(sizeof(SeqStack));if(stack){stack->s=(DataType*)malloc(sizeof(DataType)*m);if(!stack->s){free(stack);return 0;}stack->t=-1;stack->MAXNUM=m;return stack;}return 0;
}int isEmptyStack_seq(PSeqStack pastack){return (pastack->t==-1)?1:0;
}int pop_seq(PSeqStack pastack){if(isEmptyStack_seq(pastack)){printf("\n Stack is free!");return 0;}pastack->t--;return 1;
}DataType top_seq(PSeqStack pastack){if(isEmptyStack_seq(pastack)){printf("\n Stack is free!");exit(0);}else{return (pastack->s[pastack->t]);}
}
BiTNode *GoFarLeft(BiTree T,SeqStack *S){if(!T)return NULL;while (T->lchild) {push_seq(S, T);T=T->lchild;}return T;
}void Inorder_I(BiTree T,void(*visit)(TElemType& e)){SeqStack *S = createEmptyStack_seq(10);BiTree t = GoFarLeft(T, S);while (t) {visit(t->data);if(t->rchild)t=GoFarLeft(t->rchild, S);else{if (!isEmptyStack_seq(S)) {t=top_seq(S);pop_seq(S);}else t = NULL;}}
}int main( ){return 0;
}

广度优先遍历

#include<stdio.h>
#include<stdlib.h>#define TElemType inttypedef struct BiTNode{TElemType data;struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
BiTNode root;void visit(TElemType& e){printf("%d",e);
}typedef  BiTree  DataType;
typedef struct Qnode QNode;typedef struct Qnode{DataType info;QNode *link;
}*QueuePtr;typedef  struct{QueuePtr front;QueuePtr rear;
}LinkQueue,*PLinkQueue;LinkQueue q;LinkQueue initQueue(){LinkQueue Q;Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));if(!Q.front)exit(0);Q.front->link=NULL;return Q;
}int enQueue(PLinkQueue q,DataType x){QueuePtr qnode = (QueuePtr)malloc(sizeof(QNode));if(!qnode)return 0;qnode->info=x;qnode->link=NULL;q->rear->link = qnode;q->rear=qnode;return 1;
}DataType deQueue(PLinkQueue q){if(q->front==q->rear)return 0;QueuePtr p=q->front->link;DataType e = p->info;q->front->link=p->link;if(q->rear==p)q->rear=q->front;free(p);return e;
}
int queempty(LinkQueue q){if(q.front->link)return 1;else return 0;
}void LevelOrder(BiTree root){BiTree tnode = root;if(root==NULL)exit(0);LinkQueue q = initQueue();enQueue(&q,tnode);while (!queempty(q)) {tnode = deQueue(&q);printf("%d",tnode->data);if(tnode->lchild)enQueue(&q, tnode->lchild);if(tnode->rchild)enQueue(&q, tnode->rchild);}
}int main( ){return 0;
}