[考试]二叉树的四种遍历方法和两种求深度的方法

[考试]二叉树的四种遍历方法和两种求深度的方法 二叉树的四种遍历方法和两种求深度的方法 二叉树的四种遍历方法和两种求深度的方法 用到了以前学的栈和队列的知识，也算是一种复习。不过用到栈来求深度的时候，改变了二叉树，不知道如何去避免, // 二叉树.cpp : 定义控制台应用程序的入口点。 #include "stdafx.h" #include "stdio.h" #include "stdlib.h" typedef struct BiTNode{ //二叉树结构 int data; struct BiTNode *lchild, *rchild; }BiTNode, *BiTree; #define STACK_INIT_SIZE 100 #define STACKINGMENT 10 int CreateBiTree( BiTNode **T ) //用先序顺序建立二叉树 { char c; if( (c = getchar()) == '#') *T = NULL; else { if(!(*T = (BiTree)malloc(sizeof(BiTNode)))) { printf("ERROR!"); return 0; } (*T)->data = c; CreateBiTree(&(*T)->lchild); CreateBiTree(&(*T)->rchild); } return 0; } int PrintfElement( int e ) { printf("%c",e); return 1; } int PreOrderTraverse(BiTree T,int (* PrintfElement)(int e)) //先序遍历二叉树的递归方法 { if(T) //访问根结点 { if(PrintfElement(T->data)) if(PreOrderTraverse(T->lchild,PrintfElement)) // 先序遍历左子树 if(PreOrderTraverse(T->rchild,PrintfElement)) //先 序遍历右子树 return 1; return 0; } else return 1; } int InOrderTraverse(BiTree T,int (*PrintfElement)(int)) //中序遍历二叉树的递归方法 { if(T) { if(InOrderTraverse(T->lchild, PrintfElement)) if(PrintfElement(T->data)) if(InOrderTraverse(T->rchild, PrintfElement)) return 1; return 0; } else return 1; } int PostOrderTraverse(BiTree T, int (*PrintfElement)(int) ) //后序遍历二叉树的递归方法 { if(T) { if(PostOrderTraverse(T->lchild, PrintfElement)) if(PostOrderTraverse(T->rchild, PrintfElement)) if(PrintfElement(T->data)) return 1; return 0; } else return 1; } /*typedef struct{ //栈 BiTree * base; BiTree * top; int stacksize; }SqStack; int InitStack(SqStack **s) //建立空栈 { (*s)->base = (BiTree*)malloc(STACK_INIT_SIZE * sizeof(BiTNode*)); if(!((*s)->base)) return 0; (*s)->top = (*s)->base; (*s)->stacksize = (*s)->stacksize; return 0; } int Push(SqStack *s, BiTree T) //压栈 { if(s->top - s->base >= STACK_INIT_SIZE) { s->base = (BiTree*)realloc(s->base,(STACK_INIT_SIZE + STACKINGMENT) + sizeof(BiTNode*)); s->top = s->base + STACK_INIT_SIZE; s->stacksize += STACK_INIT_SIZE; } *s->top++ = T; return 0; } BiTree Pop(SqStack *s,BiTree T) //出栈, 后返回栈顶元素 { if(s->base == s->top) { printf("已空～"); return 0; } T = * (-- s->top -1); return T; } // 此方法过后二叉树就被改变了。 int DeepBiTree(BiTree T) //二叉树的深度 { BiTree p = T; SqStack *s, a; int deep = 1,max = 0,k = 0,b = -2,i = 0,j = 0; s = &a; InitStack(&s); Push(s, T); if(T->rchild == NULL) b++; while(b) { if(p->lchild) { if(0 == k) { p = p->lchild; j = 1; //表记走过左子树 } else { p = p->rchild; k = 0; i = 1; } Push(s,p); deep++; if(deep > max) max = deep; } else { if(p->rchild != NULL) { i = 1; p = p->rchild; Push(s,p); deep++; if(deep > max) max = deep; } else { p = Pop(s,p); deep--; k = 1; if(i) //把走过的子树置为空， 以后不再走 p->rchild = NULL; if(j) p->lchild = NULL; i = j = 0; } } if(p == T) b++; } free(s->base); return max; }*/ int DeepBiTree(BiTree T) //求二叉树的深度 { int ldeep,rdeep; if(!T) return 0; //空二叉子树深度为0 else { ldeep = DeepBiTree(T->lchild); //先序遍历二叉树谨记:递归是把问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 分解成一个最小的单元，例如这里求二叉树的深度就是 rdeep = DeepBiTree(T->rchild); //左二叉子树的深度和右二叉子树的深度作比较，取大的那个加一就是此二叉树的深度。 } if(ldeep > rdeep) //ldeep就是每个“二叉树”的左子树深度。 return ldeep + 1; //rdeep就是每个“二叉树”的右子树深度。 else return rdeep + 1; } typedef struct QNode{ BiTree data; struct QNode *next; }QNode, *QueuePtr; typedef struct{ QueuePtr front; QueuePtr rear; }LinkQueue; int InitQueue(LinkQueue **Q) //建立空队列 { (*Q)->rear = (*Q)->front = (QueuePtr)malloc(sizeof(QNode));//给对头分配空间 if(!(*Q)->front) return 0; (*Q)->front->next= NULL; //队尾指向空 return 0; } int DestoryQueue(LinkQueue *Q) { while(Q->front) //对头不为空则继续删除 { Q->rear = Q->front->next; //保留对头后一个队员，留出对头以便删除 free(Q->front); //删除原对头结点 Q->front = Q->rear; //指向新对头 } return 0; } int EnQueue(LinkQueue *Q, BiTree T) //插入新队员 切记队列在队尾插入。 { QueuePtr p; if(!(p = (QueuePtr)malloc(sizeof(QNode)))) //生 成新结点(不要搞错结点的类型) return 0; p->data = T; //给新结点赋值 p->next = NULL; //新结点指向空 Q->rear->next = p; //队尾指向新结点 Q->rear = p; //新队尾既是刚插入的结点 return 0; } BiTree DeQueue(LinkQueue *Q, BiTree T) //在对头删除 { QueuePtr p = Q->front->next; // 辅助指针标记要删除的队员 if(Q->front == Q->rear) //空队列不予删除 { printf("队列已空，无法删除～\n"); return 0; } T = p->data; //提取要 删除的队员 Q->front->next = p->next; //删除对头结点 if(Q->rear == p) //若队列已空 Q->rear = Q->front; //则对头等于队尾 free(p); //删除结点 return T; } //队列使用注意:在对头删除，在队尾插入，对头没有指向数据，而队尾有，空队列对头等于队尾。 int LevelOrderTraverse(BiTree T, int (*PrintfElement)(int)) //层序遍历二叉树 { LinkQueue *Q, a; Q = &a; BiTree p = T; InitQueue(&Q); if(!T) //空二叉树结束 return 0; PrintfElement(p->data); //首先输出根结点 if(p->lchild) //若左孩子存在则把左孩子插入队列 EnQueue(Q, p->lchild); if(p->rchild) //若右孩子存在则把右孩子插入队列 EnQueue(Q, p->rchild); while(Q->front != Q->rear) //队列不为空 { p = DeQueue(Q, p); //删除对头 PrintfElement(p->data); //输出结点 if(p->lchild) //同上 EnQueue(Q, p->lchild); if(p->rchild) EnQueue(Q, p->rchild); } DestoryQueue(Q); //销毁队列 return 0; } int main() { int (*p)(int) ; //函数类型指针 int deep; BiTree T; BiTNode s; T = &s; p = PrintfElement; printf("输入字符建立二叉树:"); CreateBiTree( &T ); printf("先序遍历输出二叉树:"); PreOrderTraverse(T,p); printf("\n中序遍历输出二叉树:"); InOrderTraverse(T, p); printf("\n后序遍历输出二叉树:"); PostOrderTraverse(T,p); deep = DeepBiTree(T); printf("\n二叉树的深度:%d\n",deep); printf("层序遍历输出二叉树;"); LevelOrderTraverse(T,p); return 0; }