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

二叉树的四种遍历方法和两种求深度的方法用到了以前学的栈和队列的知识，也算是一种复习。不过用到栈来求深度的时候，改变了二叉树，不知道如何去避免？// 二叉树.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 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...