二叉树的四种遍历方法和两种求深度的方法.doc

二叉树的四种遍历方法和两种求深度的方法用到了以前学的栈和队列的知识，也算是一种复习。不过用到栈来求深度的时候，改变了二叉树，不知道如何去避免？/ 二叉树.cpp : 定义控制台应用程序的入口点。#include stdafx.h#include stdio.h#include stdlib.htypedef struct BiTNode /二叉树结构int data;struct BiTNode *lchild, *rchild;BiTNode, *BiTree;#define STACK_INIT_SIZE 100#define STACKINGMENT 10int 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; /空二叉子树深度为0else ldeep = DeepBiTree(T-lchild); /先序遍历二叉树谨记：递归是把问题分解成一个最小的单元，例如这里求二叉树的深度就是 rdeep = DeepBiTree(T-rchild); /左二叉子树的深度和右二叉子树的深度作比较，取大的那个加一就是此二叉树的深度。if(ldeep rdeep) /ldeep就是每个“二叉树”的左子树深度。 return ldeep + 1; /rdeep就是每个“二叉树”的右子树深度。else return rdeep + 1;typedef struct QNodeBiTree data;struct QNode *next;QNode, *QueuePtr;typedef structQueuePtr 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