数据结构二叉树基本操作
(1).
// 对二叉树的基本操作的类模板封装
//------------------------------------------------------------------------------------------------------------------------
#include //------------------------------------------------------------------------------------------------------------------------ //定义二叉树的结点类型BTNode,其中包含数据域、左孩子,右孩子结点。 template T data ; //数据域 BTNode* lchild; //指向左子树的指针 BTNode* rchild; //指向右子树的指针 }; //------------------------------------------------------------------------------------------------------------------------ //CBinary的类模板 template BTNode 标准 实用文档 T GetParent(T e); // 若二叉树不空且e是二叉树中的一个结点那么返回其双亲结点值 T GetLeftChild(T e); // 获取左孩子结点值 T GetRightChild(T e); // 获取右孩子结点值 T GetLeftSibling(T e); // 获取左兄弟的结点值 T rightsibling(BTNode //二叉树的树形显示算法 template void BinaryTree if(bt)//空二叉树不显示 { DisplayBTreeShape(bt->rchild,level+1);//显示右子树 cout< DisplayBTreeShape(bt->lchild,level+1);//显示左子树 }//if }//DisplayBTree template static int clear(BTNode 实用文档 return 0; } template void BinaryTree { //创建一棵二叉树:先序序列的顺序输入数据,end为结束的标志 cout<<\"请按先序序列的顺序输入二叉树,-1为空指针域标志:\"< if(x==end) return ; //end 表示指针为空,说明树为空 p=new BTNode p->lchild=NULL; p->rchild=NULL; BT=p; //根结点 create(p,1,end);//创建根结点左子树,1为标志,表示左子树 create(p,2,end);//创建根结点右子树,2为标志,表示右子树 } template static int create(BTNode {//静态函数,创建二叉树,k为创建左子树还是右子树的标志,end为空指针域的标志 BTNode return 0; 标准 实用文档 } template bool BinaryTree if(BT==NULL) return true;//树根结点为空,说明树为空 return false; } template int BinaryTree int depth=0;//开始的时候数的深度初始化为0 if(bt)//如果树不为空 Depth(bt,1,depth); return depth; } template static int Depth(BTNode { //这个函数由BiTreeDepth()函数调用完成树的深度的计算 //其中p是根结点,Level 是层,depth用来返回树的深度 if(level>depth) depth=level; if(p->lchild) Depth(p->lchild,level+1,depth);//递归的遍历左子树,并且层数加1 if(p->rchild) Depth(p->rchild,level+1,depth);//递归的遍历右子树,并且层数加1 return 0; } template bool BinaryTree {//若二叉树不为空用e返回根结点的值,函数返回true,否则函数返回false if(BT!=NULL) //判断二叉树是否为空 { e=BT->data; //若不空,则将根结点的数据赋值给e return true;//操作成功,返回true } return false; //二叉树为空,返回false } template BTNode 标准 实用文档 return BT;//返回根结点的指针,若二叉树为空那么返回NULL } template bool BinaryTree if(SearchNode(e)!=NULL) { (SearchNode(e))->data=value; return true; } return false; } template T BinaryTree BTNode return NULL; } template T BinaryTree {//如果二叉树存在,e是二叉树中的一个结点,右子树存在那么返回右子树的结点值,否则返回0并提示右子树为空 BTNode if(p->rchild) return p->rchild->data;//右子树不空,返回右子树根结点的值 标准 实用文档 cout<<\"结点\"< T BinaryTree {//如果二叉树存在,e是二叉树中的一个结点,左子树存在那么返回左子树的结点值,否则返回0并提示左子树为空 BTNode cout<<\"结点\"< T BinaryTree {//二叉树为空 cout<<\"二叉树为空!\"< T leftsibling(BTNode T q=0; if(p==NULL) return 0; else { if(p->rchild) { if(p->rchild->data==e) { if(p->lchild) return p->lchild->data; else return NULL; } } 标准 实用文档 q=leftsibling(p->lchild,e); if(q)return q; q=leftsibling(p->rchild,e); if(q)return q; } return 0; } //------------------------------------------------------------------------------------------------------------------------ template T BinaryTree {//二叉树为空 cout<<\"二叉树为空!\"< T BinaryTree BTNode } return 0; } template bool BinaryTree 标准 实用文档 if(p) { if(LR==0) { c->rchild=p->lchild; p->lchild=c; } else { c->rchild=p->rchild; p->rchild=c; } return true; } return false;//p为空 } //------------------------------------------------------------------------------------------------------------------------ template bool BinaryTree return false;//p为空 } //------------------------------------------------------------------------------------------------------------------------ template void BinaryTree cout<<\"----------------------------------------------\"< 实用文档 BTNode PreTraverse(p); //从根结点开始先序遍历二叉树 cout< static int PreTraverse(BTNode if(p!=NULL) { cout< return 0; } //------------------------------------------------------------------------------------------------------------------------ template void BinaryTree cout<<\"----------------------------------------------\"< InTraverse(p);//从根结点开始中序遍历二叉树 cout< static int InTraverse(BTNode if(p!=NULL) { InTraverse(p->lchild); //递归的调用中序遍历左子树 cout< return 0; } //------------------------------------------------------------------------------------------------------------------------ template 标准 实用文档 void BinaryTree cout<<\"----------------------------------------------\"< PostTraverse(p);//从根结点开始遍历二叉树 cout< static int PostTraverse(BTNode if(p!=NULL) { PostTraverse(p->lchild);//递归调用后序遍历左子树 PostTraverse(p->rchild);//递归调用后序遍历右子树 cout< return 0; } //------------------------------------------------------------------------------------------------------------------------ template void BinaryTree cout<<\"----------------------------------------------\"< BTNode 标准 实用文档 cout<<\"\\n----------------------------------------------\"< void BinaryTree cout<<\"----------------------------------------------\"< cout<<\"\\n----------------------------------------------\"< void BinaryTree BTNode cout<<\"----------------------------------------------\"< 实用文档 while(front!=rear) //队列不为空。 { b=Queue[front++]; //队首的元素出队列 if(b)cout< } cout<<\"\\n----------------------------------------------\"< int BinaryTree int count=0; return Leaf(BT,count); } template static int Leaf(BTNode //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 BTNode 标准 实用文档 t=search(BT->rchild,e);//在右子树查找 if(t) return t; } return NULL; } template static BTNode return NULL; } //------------------------------------------------------------------------------------------------------------------------ (2).#include\"BinaryTree.cpp\" #include\"windows.h\" int main() { int MainMenu=-1; BinaryTree 实用文档 cout<<\"\\b\\b\"; cin>>MainMenu; switch(MainMenu) { case 1: T.CreateBiTree(-1); break; case 2: cout<<\"下面显示的是一棵左转了90度的树!\"< 实用文档 cout<<\"二叉树为空\"< 实用文档 break; case 8: cout<<\"请输入结点值:\"; int node5; cin>>node5; cout<<\"该结点的右兄弟结点值为:\"< 标准 实用文档 标准 break; case 1: T.ClearBiTree(); cout<<\"已经将二叉树销毁!\"< if(T.SearchNode(invalue)&&t.GetRoot()&&(t.GetRoot()->rchild)==NULL) { t.InsertChild(T.SearchNode(invalue),t.GetRoot(),lr); cout<<\"操作成功!\"< } system(\"pause\"); break; case 4: cout<<\"请输入结点的值,\"<