递归实现前中后序遍历
#include
#include
#define TElemType int
typedef 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;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
非递归实现中序遍历
#include
#include
#define TElemType int
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
BiTNode root;
void visit(TElemType& e){
printf("%d",e);
}
#define DataType BiTree
typedef 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;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
广度优先遍历
#include
#include
#define TElemType int
typedef 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;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82