数据结构——二叉树基本操作源代码.doc

数据结构二叉树基本操作(1)./ 对二叉树的基本操作的类模板封装/-#includeusing namespace std;/-/定义二叉树的结点类型BTNode,其中包含数据域、左孩子，右孩子结点。template struct BTNodeT data ;/数据域BTNode* lchild;/指向左子树的指针BTNode* rchild;/指向右子树的指针;/-/CBinary的类模板template class BinaryTreeBTNode* BT;public: BinaryTree()BT=NULL;/ 构造函数,将根结点置空BinaryTree()clear(BT);/ 调用Clear()函数将二叉树销毁void ClearBiTree()clear(BT);BT=NULL;/ 销毁一棵二叉树void CreateBiTree(T end);/ 创建一棵二叉树，end为空指针域标志bool IsEmpty();/ 判断二叉树是否为空int BiTreeDepth();/ 计算二叉树的深度bool RootValue(T &e);/ 若二叉树不为空用e返回根结点的值，函数返回true，否则函数返回falseBTNode*GetRoot();/ 二叉树不为空获取根结点指针，否则返回NULLbool Assign(T e,T value);/ 找到二叉树中值为e的结点，并将其值修改为value。T GetParent(T e);/ 若二叉树不空且e是二叉树中的一个结点那么返回其双亲结点值T GetLeftChild(T e);/ 获取左孩子结点值T GetRightChild(T e);/ 获取右孩子结点值T GetLeftSibling(T e);/ 获取左兄弟的结点值T rightsibling(BTNode*p,T e);T GetRightSibling(T e);/ 获取右孩子的结点值bool InsertChild(BTNode* p,BTNode* c,int RL);/ 插入操作bool DeleteChild(BTNode* p,int RL); /删除操作void PreTraBiTree();/ 递归算法：先序遍历二叉树void InTraBiTree();/ 递归算法：中序遍历二叉树void PostTraBiTree();/ 递归算法：后序遍历二叉树void PreTraBiTree_N();/ 非递归算法：先序遍历二叉树void InTraBiTree_N();/ 非递归算法：中序遍历二叉树void LevelTraBiTree(); / 利用队列层次遍历二叉树int LeafCount();/ 计算叶子结点的个数BTNode* SearchNode(T e);/ 寻找到结点值为e的结点，返回指向结点的指针void DisplayBTreeShape(BTNode*bt,int level=1);/二叉树的树形显示算法template void BinaryTree:DisplayBTreeShape(BTNode*bt,int level) if(bt)/空二叉树不显示 DisplayBTreeShape(bt-rchild,level+1);/显示右子树 coutendl; /显示新行 for(int i=0;ilevel-1;i+) cout ; /确保在第level列显示节点 coutdata; /显示节点 DisplayBTreeShape(bt-lchild,level+1);/显示左子树 /if/DisplayBTreetemplate static int clear(BTNode*bt) /销毁一棵二叉树if(bt)/根结点不空 clear(bt-lchild); /递归调用Clear()函数销毁左子树clear(bt-rchild); /递归调用Clear()函数销毁右子树cout释放了指针bt所指向的空间。endl;delete bt; /释放当前访问的根结点 return 0;template void BinaryTree:CreateBiTree(T end)/创建一棵二叉树：先序序列的顺序输入数据，end为结束的标志cout请按先序序列的顺序输入二叉树,-1为空指针域标志：endl;BTNode*p;T x;cinx;/输入根结点的数据if(x=end) return ;/end 表示指针为空，说明树为空p=new BTNode;/申请内存if(!p)cout申请内存失败！data=x;p-lchild=NULL;p-rchild=NULL;BT=p;/根结点create(p,1,end);/创建根结点左子树，1为标志，表示左子树create(p,2,end);/创建根结点右子树，2为标志，表示右子树template static int create(BTNode*p,int k,T end)/静态函数，创建二叉树，k为创建左子树还是右子树的标志，end为空指针域的标志BTNode*q;T x;cinx;if(x!=end)/先序顺序输入数据q=new BTNode;q-data=x;q-lchild=NULL;q-rchild=NULL;if(k=1) p-lchild=q;/q为左子树if(k=2) p-rchild=q;/p为右子树create(q,1,end);/递归创建左子树create(q,2,end);/递归创建右子树return 0;template bool BinaryTree:IsEmpty()/判断二叉树是否为空if(BT=NULL) return true;/树根结点为空，说明树为空return false;template int BinaryTree:BiTreeDepth()/利用递归算法计算树的深度BTNode*bt=BT;/树根结点int depth=0;/开始的时候数的深度初始化为0if(bt)/如果树不为空Depth(bt,1,depth);return depth;template static int Depth(BTNode* p,int level,int &depth)/这个函数由BiTreeDepth()函数调用完成树的深度的计算/其中p是根结点，Level 是层，depth用来返回树的深度if(leveldepth) depth=level;if(p-lchild) Depth(p-lchild,level+1,depth);/递归的遍历左子树，并且层数加1if(p-rchild) Depth(p-rchild,level+1,depth);/递归的遍历右子树，并且层数加1return 0;template bool BinaryTree:RootValue(T &e)/若二叉树不为空用e返回根结点的值，函数返回true，否则函数返回falseif(BT!=NULL)/判断二叉树是否为空e=BT-data;/若不空，则将根结点的数据赋值给ereturn true;/操作成功，返回truereturn false;/二叉树为空，返回falsetemplate BTNode*BinaryTree:GetRoot()/获取根信息return BT;/返回根结点的指针，若二叉树为空那么返回NULLtemplate bool BinaryTree:Assign(T e,T value)/结点赋值if(SearchNode(e)!=NULL)(SearchNode(e)-data=value;return true;return false;template T BinaryTree:GetParent(T e)/获取双亲信息BTNode*Queue200,*p;int rear,front;rear=front=0;if(BT)Queuerear+=BT;while(rear!=front)p=Queuefront+;if(p-lchild&p-lchild-data=e|p-rchild&p-rchild-data=e)return p-data;elseif(p-lchild) Queuerear+=p-lchild;if(p-rchild) Queuerear+=p-rchild;return NULL;template T BinaryTree:GetRightChild(T e)/如果二叉树存在，e是二叉树中的一个结点，右子树存在那么返回右子树的结点值，否则返回0并提示右子树为空BTNode*p=SearchNode(e);if(p-rchild) return p-rchild-data;/右子树不空，返回右子树根结点的值cout结点e的右子树为空endl;return 0;template T BinaryTree:GetLeftChild(T e)/如果二叉树存在，e是二叉树中的一个结点，左子树存在那么返回左子树的结点值，否则返回0并提示左子树为空BTNode*p=SearchNode(e);if(p-lchild) return p-lchild-data;cout结点e的左子树为空endl;return 0;template T BinaryTree:GetLeftSibling(T e)/获取左兄弟信息if(BT!=NULL)return leftsibling(BT,e);else/二叉树为空cout二叉树为空！endl;return 0;template T leftsibling(BTNode*p,T e)T q=0;if(p=NULL) return 0;elseif(p-rchild)if(p-rchild-data=e)if(p-lchild) return p-lchild-data;elsereturn NULL;q=leftsibling(p-lchild,e);if(q)return q;q=leftsibling(p-rchild,e);if(q)return q;return 0;/-template T BinaryTree:GetRightSibling(T e)/获取右兄弟信息if(BT!=NULL)return rightsibling(BT,e);else/二叉树为空cout二叉树为空！endl;return 0;template T BinaryTree:rightsibling(BTNode*p,T e)BTNode *q=SearchNode(e);BTNode *pp;if(q)pp=SearchNode(GetParent(e);if(pp)if(pp-rchild) return pp-rchild-data;else return 0;else return 0;return 0;template bool BinaryTree:InsertChild(BTNode* p,BTNode* c,int LR)/插入孩子if(p)if(LR=0)c-rchild=p-lchild;p-lchild=c;elsec-rchild=p-rchild;p-rchild=c;return true;return false;/p为空/-template bool BinaryTree:DeleteChild(BTNode* p,int RL) /删除结点if(p)if(RL=0)clear(p-lchild);/释放p右子树的所有结点空间p-lchild=NULL;elseclear(p-rchild);p-rchild=NULL;return true;/删除成功return false;/p为空/-template void BinaryTree:PreTraBiTree()/先序遍历二叉树cout-endl;cout先序遍历二叉树:;BTNode*p;p=BT;/根结点PreTraverse(p); /从根结点开始先序遍历二叉树coutendl;cout-endl;template static int PreTraverse(BTNode*p)if(p!=NULL)coutdatalchild);/递归的调用前序遍历左子树PreTraverse(p-rchild);/递归的调用前序遍历右子树return 0;/-template void BinaryTree:InTraBiTree()/中序遍历二叉树cout-endl;cout中序遍历二叉树:;BTNode*p;p=BT;/根结点InTraverse(p);/从根结点开始中序遍历二叉树coutendl;cout-endl;template static int InTraverse(BTNode*p)if(p!=NULL)InTraverse(p-lchild);/递归的调用中序遍历左子树coutdatarchild);/递归的调用中序遍历右子树return 0;/-template void BinaryTree:PostTraBiTree()/后序遍历二叉树cout-endl;cout后序遍历二叉树:;BTNode*p;p=BT;/根结点PostTraverse(p);/从根结点开始遍历二叉树coutendl;cout-endl;template static int PostTraverse(BTNode*p)if(p!=NULL)PostTraverse(p-lchild);/递归调用后序遍历左子树PostTraverse(p-rchild);/递归调用后序遍历右子树coutdata ;/输出结点上的数据return 0;/-template void BinaryTree:PreTraBiTree_N()/cout-endl;cout先序(非递归)遍历二叉树得：;BTNode *Stack200;/利用指针数组作为栈int top=0;BTNode*p=BT;/将根结点的指针赋值给pwhile(p!=NULL|top!=0)while(p!=NULL)coutdatarchild;p=p-lchild;if(top!=0)p=Stack-top;coutn-endl;/-template void BinaryTree:InTraBiTree_N()/非递归中序遍历二叉树cout-endl;cout中序(非递归)遍历二叉树得：;int top=0;BTNode *Stack200;BTNode *p=BT;while(p|top)while(p)Stacktop+=p;p=p-lchild;if(top)p=Stack-top;coutdatarchild;coutn-endl;/-template void BinaryTree:LevelTraBiTree()/利用队列Queue层次遍历二叉树BTNode *Queue100;/利用一维数组作为队列，存放结点的指针BTNode *b;int front,rear;/指向队列的头和尾下标front=rear=0;/队列初始为空cout-endl;if(BT)/若二叉树不为空。Queuerear+=BT;/二叉树的根结点指针进队列。while(front!=rear)/队列不为空。b=Queuefront+;/队首的元素出队列if(b)coutdatalchild) Queuerear+=b-lchild;/如果左子树不空，进队。if(b-rchild) Queuerear+=b-rchild;/如果右子树不空，进队。coutn-endl;template int BinaryTree:LeafCount()/计算叶子的个数int count=0;return Leaf(BT,count);template static int Leaf(BTNode* p,int &count)/static int count=0;/静态变量，存放叶子结点的个数if(p)if(p-lchild=NULL&p-rchild=NULL) count+;/判断是否为叶子结点Leaf(p-lchild,count);/递归遍历左子树Leaf(p-rchild,count);/递归遍历右子树return count;template BTNode* BinaryTree:SearchNode(T e)/结点查询BTNode*t;if(BT)if(BT-data=e)return BT;t=search(BT-lchild,e);/在左子树中查找if(t)return t;t=search(BT-rchild,e);/在右子树查找if(t) return t;return NULL;template static BTNode* search(BTNode*bn,T e)BTNode*t;if(bn)if(bn-data=e)return bn;t=search(bn-lchild,e);/递归查找左子树if(t) return t;t=search(bn-rchild,e);/递归查找右子树if(t) return t;return NULL;/-(2).#includeBinaryTree.cpp#includewindows.hint main()int MainMenu=-1;BinaryTree T;BinaryTree t;while(MainMenu!=6)system(cls);cout-主菜单-endl;cout1-创建二叉树(元素类型为整数) endl;cout2-树形显示二叉树endl;cout【进入子菜单】endl;cout【进入子菜单】endl;cout【进入子菜单】endl;cout6-退出endl;cout-endl;cout请选择操作： ;coutMainMenu;switch(MainMenu)case 1:T.CreateBiTree(-1);break;case 2:cout下面显示的是一棵左转了90度的树!endl;T.DisplayBTreeShape(T.GetRoot();/第一个参数是根结点指针，第二个参数为默认的1 coutop;do/system(cls);cout -3-获取二叉树信息-endl;cout0. 返回主菜单endl;cout1. 获取树根结点值endl;cout2. 判断树是否为空endl;cout3. 求树的深度endl;cout4. 双亲结点值endl;cout5. 左孩子值endl;cout6. 右孩子值endl;cout7. 左兄弟值endl;cout8. 右兄弟值endl;cout9. 叶子结点的个数endl;cout10.树形显示二叉树endl;cout -endl;cout请选择操作： ;coutop;switch(op)case 1:int root;if(T.RootValue(root)=true)cout树根结点的值为：rootendl;elsecout二叉树为空endl;system(pause);break;case 2:if(T.IsEmpty()=true)cout二叉树为空！endl;else cout二叉树不空！endl;system(pause);break;case 3:cout二叉树的深度为：T.BiTreeDepth()endl;system(pause);break;case 4:coutnode1;cout该结点的双亲结点为：T.GetParent(node1)endl;system(pause);break;case 5:coutnode2;cout该结点的左孩子结点值为：T.GetLeftChild(node2)endl;system(pause);break;case 6:coutnode3;cout该结点的右孩子结点值为：T.GetRightChild(node3)endl;system(pause);break;case 7:coutnode4;cout该结点的左兄弟结点值为：T.GetLeftSibling(node4)endl;system(pause);break;case 8:coutnode5;cout该结点的右兄弟结点值为：T.GetRightSibling(node5)endl;system(pause);break;case 9:cout二叉树的叶子结点个数为：T.LeafCount()endl;system(pause);break;case 10:cout下面显示的是一棵左转了90度的二叉树!endl;T.DisplayBTreeShape(T.GetRoot();/第一个参数是根结点指针，第二个参数为默认的1 coutendl;system(pause);break;default:break;while(op!=0);break;case 4:int op2;docout -4 对二叉树进行操作-endl;cout0. 返回主菜单endl;cout1. 销毁二叉树endl;cout2. 给指定结点赋值endl;cout3. 插入endl;cout4. 删除endl;cout5. 显示二叉树endl;cout -endl;cout请选择操作： ;coutop2;switch(op2)case 0:break;case 1:T.ClearBiTree();cout已经将二叉树销毁！endl;system(pause);break;case 2:int ChangeValue;/要改变的结点值int NewValue;/修改之后的结点值coutChangeValue;cout请输入修改之后的结点值：NewValue;if(T.SearchNode(ChangeValue) (T.SearchNode(ChangeValue)-data=NewValue;cout修改成功！endl;elsecout修改失败！endl;system(pause);break;case 3:cout请创建一棵没有右子树的二叉树：endl;t.CreateBiTree(-1);cout请输入要插入的二叉树的结点值invalue;coutlr;if(T.SearchNode(invalue)&t.GetRoot()&(t.GetRoot()-rchild)=NULL)t.InsertChild(T.SearchNode(invalue),t.Get