二叉树的创建和遍历

/**** name: 二叉树的创建和遍历** author: Dev|il** date: 2011-10-15 12:56**/#include <iostream>#include <queue>using namespace std;const int MAX_TREE_SIZE = 1000;typedef int ElemType;typedef bool Status;typedef ElemType bitTree[MAX_TREE_SIZE]; //树的线性定义,只适合存储满二叉树const ElemType END = -1;//树的二叉链表定义typedef struct LNode{ElemType data;struct LNode *lchild, *rchild;}BitNode, *BiTree;/////////////////////////////////函数的声明/////////////////////////////////////////////按先序DLR输入二叉树节点的值,构造二叉链表表示的二叉树TStatus DLRCreateBiTree(BiTree &t);//DLR//采用二叉链表存储结构,visit是对节点操作的应用函数//先序遍历二叉树t,对每个节点调用visit函数一次且一次//一旦visit操作失败,则函数操作失败Status PreOrderTraverse(BiTree t, Status (* visit)(ElemType e));//LDR//采用二叉链表的存储结构,visit是对节点操作的应用函数//中序遍历二叉树t,对每个节点调用visit函数一次且一次//一旦visit操作失败,则函数操作失败Status InOrderTranverse(BiTree t, Status(*visit)(ElemType e));//LRD//采用二叉链表的存储结构,visit是对节点操作的应用函数//后序遍历二叉树t,对每个节点调用visit函数一次且一次//一旦visit操作失败,则函数操作失败Status PostOrderTranverse(BiTree t, Status(*visit)(ElemType e));//采用二叉链表的存储结构,visit是对节点操作的应用函数//层序遍历二叉树t,对每个节点调用visit函数一次且一次//一旦visit操作失败,则函数操作失败void LevelOrderTranverse(BiTree t, Status(*visit)(ElemType e));//访问函数Status visit(ElemType e);//返回二叉树t的深度int DLRBiTreeDepth(BiTree t);/////////////////////////////////////////////////////////////////////////////////////////////////////////////////函数的实现//////////////////////////////////Status DLRCreateBiTree(BiTree &t){ElemType e;cin>>e;if(e == END)t = NULL;else{t = (BiTree)malloc(sizeof(BitNode)); //创建节点,相当于建立头if(!t)return false;t->data = e; //赋数据if(!DLRCreateBiTree(t->lchild)) //建立左子树return false;if(!DLRCreateBiTree(t->rchild)) //建立右子树return false;}return true;}Status PreOrderTraverse(BiTree t, Status (* visit)(ElemType e)){if(t){if(visit(t->data))if(PreOrderTraverse(t->lchild, visit))if(PreOrderTraverse(t->rchild, visit))return true;return false;}elsereturn true;}Status InOrderTranverse(BiTree t, Status(*visit)(ElemType e)){if(t){if(InOrderTranverse(t->lchild, visit))if(visit(t->data))if(InOrderTranverse(t->rchild, visit))return true;return false;}elsereturn true;}Status PostOrderTranverse(BiTree t, Status(*visit)(ElemType e)){if(t){if(PostOrderTranverse(t->lchild, visit))if(PostOrderTranverse(t->rchild, visit))if(visit(t->data))return true;return false;}elsereturn true;}void LevelOrderTranverse(BiTree t, Status(*visit)(ElemType e)){queue<BiTree> q;q.push(t);while(!q.empty()){BiTree cur = q.front();q.pop();visit(cur->data);if(cur->lchild)q.push(cur->lchild);if(cur->rchild)q.push(cur->rchild);}}Status visit(ElemType e){cout<<e<<"  ";return true;}int BiTreeDepth(BiTree t){int Ldepth, Rdepth, max;if(!t)return 0;else{Ldepth = BiTreeDepth(t->lchild);Rdepth = BiTreeDepth(t->rchild);max = Ldepth > Rdepth ? Ldepth : Rdepth;return max + 1;}}/////////////////////////////////////////////////////////////////////////////int main(){BiTree t;DLRCreateBiTree(t);cout<<"先序遍历:";PreOrderTraverse(t, visit);cout<<endl<<"中序遍历:";InOrderTranverse(t, visit);cout<<endl<<"后序遍历:";PostOrderTranverse(t, visit);cout<<endl<<"层次遍历:";LevelOrderTranverse(t, visit);cout<<endl<<"树的深度:";cout<<BiTreeDepth(t);cout<<endl;return 0;}