如何建立网站快捷链接,wordpress多功能主题 cosy,北京做网站建设价格低,扬州网站建设推广专家二叉树的先序,中序,后序遍历以及线索二叉树的遍历(2008-05-04 17:52:49)标签#xff1a;杂谈C二叉树的先序,中序,后序遍历以及线索二叉树的遍历头文件//*******************************************************************************//二叉树中的数据类型为ElemType//***…二叉树的先序,中序,后序遍历以及线索二叉树的遍历(2008-05-04 17:52:49)标签杂谈C二叉树的先序,中序,后序遍历以及线索二叉树的遍历头文件//*******************************************************************************//二叉树中的数据类型为ElemType//*******************************************************************************// BinaryTree.h: interface for the CBinaryTree class.////#include //C语言#define OK 1#define ERROR 0class CBinaryTree{public:CBinaryTree();virtual ~CBinaryTree();protected:typedef int ElemType;struct Node{ //数据ElemType data; //数据域信息int lt; //前继指针标志int rt; //后继指针标志Node* lchild; //指向左孩子Node* rchild; //指向右孩子}*root,*head;public:int Create();int PreOrderTraverse();int MidOrderTraverse();int LastOrderTraverse();void LevelOrderTraverse();int GetLeafCount();int GetDepth();int GetNodeCount();int MidOrderTraverseThr();void ChangeLeftRight();void Destroy();private: //重载以上函数,供以上函数调用int Create(Node* node);int PreOrderTraverse(Node*node);int MidOrderTraverse(Node*node);int LastOrderTraverse(Node *node);int GetLeafCount(Node*node);void GetNodeCount(Node*node,int count);int GetDepth(Node*node);void ChangeLeftRight(Node*node);void Visit(Node*node);void Destroy(Node*node);};// 实现文件// BinaryTree.cpp: implementation of the CBinaryTree class.#include BinaryTree.h#include Stack.h#include Queue.h//// Construction/Destruction//CBinaryTree::CBinaryTree(){rootNULL;headNULL;}CBinaryTree::~CBinaryTree(){Destroy();}int CBinaryTree::Create(){ //创建一个二叉树return Create(root);//用户调用此函数创建根结点由此函数调用其内的//CreateNode()创建除根结点外的其它所有结点}int CBinaryTree::PreOrderTraverse(){ //先序遍历二叉树return PreOrderTraverse(root);}int CBinaryTree::MidOrderTraverse(){ //中序遍历二叉树return MidOrderTraverse(root);}int CBinaryTree::LastOrderTraverse(){ //后序遍历二叉树return LastOrderTraverse(root);}void CBinaryTree::LevelOrderTraverse(){ //借助于堆栈,完成二叉树的层次遍历CQueue queue;if(!root) return;queue.InitQueue();Node*proot; //初始化Visit(p);queue.EnQueue((long)p);//访问根结点并将根结点地址入队while(!queue.QueueEmpty()){ //当队非空时重复执行下列操作p(Node*)queue.DeQueue(); //地址出队if(p-lchild){Visit(p-lchild);queue.EnQueue((long)p-lchild); //处理左孩子}if (p-rchild){Visit(p-rchild);queue.EnQueue((long)p-rchild); //处理右孩子}}}int CBinaryTree::GetLeafCount(){ //返回叶子结点数return GetLeafCount(root);}int CBinaryTree::GetNodeCount(){ //返回总结点数int count0;GetNodeCount(root,count);return count;}int CBinaryTree::GetDepth(){ //返回二叉树的深度return GetDepth(root);}void CBinaryTree::ChangeLeftRight(){ //交换左右两孩子结点if(root!NULL)ChangeLeftRight(root);}int CBinaryTree::Create(Node *node){int i;cout不创建本结点):;cini;if(i0)nodeNULL;else{if(!(nodenew Node))return ERROR;node-datai;node-lt0;node-rt0;Create(node-lchild); //创建左子树Create(node-rchild); //创建右子树}return OK;}int CBinaryTree::PreOrderTraverse(Node *node){if(node!NULL){coutdataif(PreOrderTraverse(node-lchild)) //遍历左子树if(PreOrderTraverse(node-rchild)) //遍历右子树return 1;return 0;}elsereturn 1;}int CBinaryTree::MidOrderTraverse(Node *node){if(node!NULL){if(MidOrderTraverse(node-lchild))//遍历左子树coutdataif(MidOrderTraverse(node-rchild))//遍历右子树return 1;return 0;}elsereturn 1;}int CBinaryTree::LastOrderTraverse(Node *node){if(node!NULL){if(LastOrderTraverse(node-lchild)) //遍历左子树if(LastOrderTraverse(node-rchild)) //遍历右子树{coutdatareturn 1;}return 0;}elsereturn 1;}int CBinaryTree::MidOrderTraverseThr(){ //中序线索化二叉树if(head!NULL)delete head;headnew Node;if(headNULL)return 0;int i0;Node*preNULL,*curNULL;long *tempnew long[GetNodeCount()];head-lt0; //无前驱,有左孩子head-rt1; //有后继,无右孩子head-rchildhead;if(rootNULL)head-lchildhead;else{head-lchildroot;prehead;curroot;for(;i0 || cur!NULL;){for(;cur!NULL;temp[i](long)cur,i,curcur-lchild);if(i0){cur(Node*)temp[--i];coutdataif(cur-lchildNULL){cur-lt1;cur-lchildpre;}if(pre-rchildNULL){pre-rt1;pre-rchildcur;}precur;curcur-rchild;}}pre-rchildhead;pre-rt1;head-rchildpre;}delete temp;return 1;}void CBinaryTree::GetNodeCount(Node *node,int count){if(node!NULL)count;elsereturn;GetNodeCount(node-lchild,count);//统计左子树个数GetNodeCount(node-rchild,count);//统计右子树个数}int CBinaryTree::GetDepth(Node *node){int d0,depthr0,depthl0;if (nodeNULL)return 0; // 如果是空树则其深度为 0else{depthlGetDepth(node-lchild); //求node的左子树的深度depthrGetDepth(node-rchild); //求node的右子树的深度return depthldepthr?1depthl:1depthr;}}int CBinaryTree::GetLeafCount(Node *node){int n,m;if(nodeNULL)return 0; // 如果二叉树是空树则返回 0else if((node-lchildNULL) (node-rchildNULL))return 1; //如果二叉树的左孩子和右孩子均为空则返回1else // 如果二叉树的左孩子或右孩子不为空{nGetLeafCount(node-lchild); //求左子树的叶子结点数目mGetLeafCount(node-rchild); //求右子树的叶子结点数目return nm; // 返回总的叶子结点数目}}void CBinaryTree::ChangeLeftRight(Node *node){if(node!NULL){ChangeLeftRight(node-lchild);ChangeLeftRight(node-rchild);Node*tempnode-lchild;node-lchildnode-rchild;node-rchildtemp;}}void CBinaryTree::Visit(Node *node){ //访问结点coutdata}void CBinaryTree::Destroy(){ //销毁二叉树Destroy(root);rootNULL;if(head)delete head;headNULL;}void CBinaryTree::Destroy(Node *node){if(node!NULL){Destroy(node-lchild);Destroy(node-rchild);delete node;nodeNULL;}}分享喜欢0赠金笔加载中请稍候......评论加载中请稍候...发评论登录名 密码 找回密码 注册记住登录状态昵 称评论并转载此博文发评论以上网友发言只代表其个人观点不代表新浪网的观点或立场。后一篇 游戏名称
