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

1、word数据结构二叉树根本操作(1)./ 对二叉树的根本操作的类模板封装/-#include<iostream>using namespace std;/-/定义二叉树的结点类型BTNode,其中包含数据域、左孩子，右孩子结点。template <class T>struct BTNodeT data ;/数据域BTNode* lchild;/指向左子树的指针BTNode* rchild;/指向右子树的指针;/-/CBinary的类模板template <class T>class BinaryTreeBTNode<T>* BT;public:

2、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<T>*

3、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<T>*p,T e);T GetRightSibling(T e);/ 获取右孩子的结

4、点值bool InsertChild(BTNode<T>* p,BTNode<T>* c,int RL);/ 插入操作bool DeleteChild(BTNode<T>* p,int RL); /删除操作void PreTraBiTree();/ 递归算法：先序遍历二叉树void InTraBiTree();/ 递归算法：中序遍历二叉树void PostTraBiTree();/ 递归算法：后序遍历二叉树void PreTraBiTree_N();/ 非递归算法：先序遍历二叉树void InTraBiTree_N();/ 非递归算法：中序遍历二叉树void

5、 LevelTraBiTree(); / 利用队列层次遍历二叉树int LeafCount();/ 计算叶子结点的个数BTNode<T>* SearchNode(T e);/ 寻找到结点值为e的结点，返回指向结点的指针void DisplayBTreeShape(BTNode<T>*bt,int level=1);/二叉树的树形显示算法template <class T>void BinaryTree<T>:DisplayBTreeShape(BTNode<T>*bt,int level) if(bt)/空二叉树不显示 Display

6、BTreeShape(bt->rchild,level+1);/显示右子树 cout<<endl; /显示新行 for(int i=0;i<level-1;i+) cout<<" " /确保在第level列显示节点 cout<<bt->data; /显示节点 DisplayBTreeShape(bt->lchild,level+1);/显示左子树 /if/DisplayBTreetemplate <class T>static int clear(BTNode<T>*bt) /销毁一棵二叉树

7、if(bt)/根结点不空 clear(bt->lchild); /递归调用Clear()函数销毁左子树clear(bt->rchild); /递归调用Clear()函数销毁右子树cout<<"释放了指针"<<bt<<"所指向的空间。"<<endl;delete bt; /释放当前访问的根结点 return 0;template <class T>void BinaryTree<T>:CreateBiTree(T end)/创立一棵二叉树：先序序列的顺序输入数据，end为结

8、束的标志cout<<"请按先序序列的顺序输入二叉树,-1为空指针域标志："<<endl;BTNode<T>*p;T x;cin>>x;/输入根结点的数据if(x=end) return ;/end 表示指针为空，说明树为空p=new BTNode<T>/申请内存if(!p)cout<<"申请内存失败！"<<endl;exit(-1);/申请内存失败退出p->data=x;p->lchild=NULL;p->rchild=NULL;BT=p;/根结点cre

9、ate(p,1,end);/创立根结点左子树，1为标志，表示左子树create(p,2,end);/创立根结点右子树，2为标志，表示右子树template <class T>static int create(BTNode<T>*p,int k,T end)/静态函数，创立二叉树，k为创立左子树还是右子树的标志，end为空指针域的标志BTNode<T>*q;T x;cin>>x;if(x!=end)/先序顺序输入数据q=new BTNode<T>q->data=x;q->lchild=NULL;q->rchild=N

10、ULL;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 <class T>bool BinaryTree<T>:IsEmpty()/判断二叉树是否为空if(BT=NULL) return true;/树根结点为空，说明树为空return false;template <class T>int BinaryTree<T>:BiTreeDepth()/利

11、用递归算法计算树的深度BTNode<T>*bt=BT;/树根结点int depth=0;/开始的时候数的深度初始化为0if(bt)/如果树不为空Depth(bt,1,depth);return depth;template <class T>static int Depth(BTNode<T>* p,int level,int &depth)/这个函数由BiTreeDepth()函数调用完成树的深度的计算/其中p是根结点，Level 是层，depth用来返回树的深度if(level>depth) depth=level;if(p->lch

12、ild) Depth(p->lchild,level+1,depth);/递归的遍历左子树，并且层数加1if(p->rchild) Depth(p->rchild,level+1,depth);/递归的遍历右子树，并且层数加1return 0;template <class T>bool BinaryTree<T>:RootValue(T &e)/假设二叉树不为空用e返回根结点的值，函数返回true，否那么函数返回falseif(BT!=NULL)/判断二叉树是否为空e=BT->data;/假设不空，那么将根结点的数据赋值给ereturn

13、 true;/操作成功，返回truereturn false;/二叉树为空，返回falsetemplate <class T>BTNode<T>*BinaryTree<T>:GetRoot()/获取根信息return BT;/返回根结点的指针，假设二叉树为空那么返回NULLtemplate <class T>bool BinaryTree<T>:Assign(T e,T value)/结点赋值if(SearchNode(e)!=NULL)(SearchNode(e)->data=value;return true;return

14、false;template <class T>T BinaryTree<T>:GetParent(T e)/获取双亲信息BTNode<T>*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

15、(p->lchild) Queuerear+=p->lchild;if(p->rchild) Queuerear+=p->rchild;return NULL;template <class T>T BinaryTree<T>:GetRightChild(T e)/如果二叉树存在，e是二叉树中的一个结点，右子树存在那么返回右子树的结点值，否那么返回0并提示右子树为空BTNode<T>*p=SearchNode(e);if(p->rchild) return p->rchild->data;/右子树不空，返回右子树根结

16、点的值cout<<"结点"<<e<<"的右子树为空"<<endl;return 0;template <class T>T BinaryTree<T>:GetLeftChild(T e)/如果二叉树存在，e是二叉树中的一个结点，左子树存在那么返回左子树的结点值，否那么返回0并提示左子树为空BTNode<T>*p=SearchNode(e);if(p->lchild) return p->lchild->data;cout<<"结点&

17、quot;<<e<<"的左子树为空"<<endl;return 0;template <class T>T BinaryTree<T>:GetLeftSibling(T e)/获取左兄弟信息if(BT!=NULL)return leftsibling(BT,e);else/二叉树为空cout<<"二叉树为空！"<<endl;return 0;template <class T>T leftsibling(BTNode<T>*p,T e)T q=0;

18、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 <class T>T BinaryTree<T>:GetRightSibling(T e)/获取右兄弟

19、信息if(BT!=NULL)return rightsibling(BT,e);else/二叉树为空cout<<"二叉树为空！"<<endl;return 0;template <class T> T BinaryTree<T>:rightsibling(BTNode<T>*p,T e)BTNode<T> *q=SearchNode(e);BTNode<T> *pp;if(q)pp=SearchNode(GetParent(e);if(pp)if(pp->rchild) return

20、pp->rchild->data;else return 0;else return 0;return 0;template <class T>bool BinaryTree<T>:InsertChild(BTNode<T>* p,BTNode<T>* 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为空/

21、-template <class T>bool BinaryTree<T>:DeleteChild(BTNode<T>* 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 <class T>void BinaryTree<T>:PreTraBiTree()

22、/先序遍历二叉树cout<<"-"<<endl;cout<<"先序遍历二叉树:"BTNode<T>*p;p=BT;/根结点PreTraverse(p); /从根结点开始先序遍历二叉树cout<<endl;cout<<"-"<<endl;template <class T>static int PreTraverse(BTNode<T>*p)if(p!=NULL)cout<<p->data<<'

23、; '/输出结点上的数据PreTraverse(p->lchild);/递归的调用前序遍历左子树PreTraverse(p->rchild);/递归的调用前序遍历右子树return 0;/-template <class T>void BinaryTree<T>:InTraBiTree()/中序遍历二叉树cout<<"-"<<endl;cout<<"中序遍历二叉树:"BTNode<T>*p;p=BT;/根结点InTraverse(p);/从根结点开始中序遍历二叉树

24、cout<<endl;cout<<"-"<<endl;template <class T>static int InTraverse(BTNode<T>*p)if(p!=NULL)InTraverse(p->lchild);/递归的调用中序遍历左子树cout<<p->data<<' '/输出结点上的数据InTraverse(p->rchild);/递归的调用中序遍历右子树return 0;/-template <class T>void Bina

25、ryTree<T>:PostTraBiTree()/后序遍历二叉树cout<<"-"<<endl;cout<<"后序遍历二叉树:"BTNode<T>*p;p=BT;/根结点PostTraverse(p);/从根结点开始遍历二叉树cout<<endl;cout<<"-"<<endl;template <class T>static int PostTraverse(BTNode<T>*p)if(p!=NULL)Post

26、Traverse(p->lchild);/递归调用后序遍历左子树PostTraverse(p->rchild);/递归调用后序遍历右子树cout<<p->data<<' '/输出结点上的数据return 0;/-template <class T>void BinaryTree<T>:PreTraBiTree_N()/cout<<"-"<<endl;cout<<"先序(非递归)遍历二叉树得："BTNode<T> *Stack2

27、00;/利用指针数组作为栈int top=0;BTNode<T>*p=BT;/将根结点的指针赋值给pwhile(p!=NULL|top!=0)while(p!=NULL)cout<<p->data<<" "Stacktop+=p->rchild;p=p->lchild;if(top!=0)p=Stack-top;cout<<"n-"<<endl;/-template <class T>void BinaryTree<T>:InTraBiTree_N()/

28、非递归中序遍历二叉树cout<<"-"<<endl;cout<<"中序(非递归)遍历二叉树得："int top=0;BTNode<T> *Stack200;BTNode<T> *p=BT;while(p|top)while(p)Stacktop+=p;p=p->lchild;if(top)p=Stack-top;cout<<p->data<<' 'p=p->rchild;cout<<"n-"<<

29、endl;/-template <class T>void BinaryTree<T>:LevelTraBiTree()/利用队列Queue层次遍历二叉树BTNode<T> *Queue100;/利用一维数组作为队列，存放结点的指针BTNode<T> *b;int front,rear;/指向队列的头和尾下标front=rear=0;/队列初始为空cout<<"-"<<endl;if(BT)/假设二叉树不为空。Queuerear+=BT;/二叉树的根结点指针进队列。while(front!=rear)/

30、队列不为空。b=Queuefront+;/队首的元素出队列if(b)cout<<b->data<<' '/输出结点的值if(b->lchild) Queuerear+=b->lchild;/如果左子树不空，进队。if(b->rchild) Queuerear+=b->rchild;/如果右子树不空，进队。cout<<"n-"<<endl;template <class T>int BinaryTree<T>:LeafCount()/计算叶子的个数int co

31、unt=0;return Leaf(BT,count);template <class T>static int Leaf(BTNode<T>* 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 <

32、class T>BTNode<T>* BinaryTree<T>:SearchNode(T e)/结点查询BTNode<T>*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 <class T>static BTNode<T>* search(BTNode<T>*bn

33、,T e)BTNode<T>*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).#include"BinaryTree.cpp"#include"windows.h"int main()int MainMenu=-1;BinaryTree<int> T;BinaryTree<i

34、nt> t;while(MainMenu!=6)system("cls");cout<<"-主菜单-"<<endl;cout<<"1-创立二叉树(元素类型为整数) "<<endl;cout<<"2-树形显示二叉树"<<endl;cout<<"3-获取二叉树信息 >>【进入子菜单】"<<endl;cout<<"4-对二叉树操作 >>【进入子菜单】&qu

35、ot;<<endl;cout<<"5-遍历二叉树 >>【进入子菜单】"<<endl;cout<<"6-退出"<<endl;cout<<"-"<<endl;cout<<"请选择操作： "cout<<"bb"cin>>MainMenu;switch(MainMenu)case 1:T.CreateBiTree(-1);break;case 2:cout<<&

36、quot;下面显示的是一棵左转了90度的树!"<<endl;T.DisplayBTreeShape(T.GetRoot();/第一个参数是根结点指针，第二个参数为默认的1 cout<<endl;system("pause");break;case 3:int op;/cin>>op;do/system("cls");cout<<" -3-获取二叉树信息-"<<endl;cout<<"0. 返回主菜单"<<endl;cout

37、<<"1. 获取树根结点值"<<endl;cout<<"2. 判断树是否为空"<<endl;cout<<"3. 求树的深度"<<endl;cout<<"4. 双亲结点值"<<endl;cout<<"5. 左孩子值"<<endl;cout<<"6. 右孩子值"<<endl;cout<<"7. 左兄弟值"&

38、lt;<endl;cout<<"8. 右兄弟值"<<endl;cout<<"9. 叶子结点的个数"<<endl;cout<<"10.树形显示二叉树"<<endl;cout<<" -"<<endl;cout<<"请选择操作： "cout<<"bbb"cin>>op;switch(op)case 1:int root;if(T.RootValu

39、e(root)=true)cout<<"树根结点的值为："<<root<<endl;elsecout<<"二叉树为空"<<endl;system("pause");break;case 2:if(T.IsEmpty()=true)cout<<"二叉树为空！"<<endl;else cout<<"二叉树不空！"<<endl;system("pause");break;ca

40、se 3:cout<<"二叉树的深度为："<<T.BiTreeDepth()<<endl;system("pause");break;case 4:cout<<"请输入结点值："int node1;cin>>node1;cout<<"该结点的双亲结点为："<<T.GetParent(node1)<<endl;system("pause");break;case 5:cout<<"

41、请输入结点值："int node2;cin>>node2;cout<<"该结点的左孩子结点值为："<<T.GetLeftChild(node2)<<endl;system("pause");break;case 6:cout<<"请输入结点值："int node3;cin>>node3;cout<<"该结点的右孩子结点值为："<<T.GetRightChild(node3)<<endl;system

42、("pause");break;case 7:cout<<"请输入结点值："int node4;cin>>node4;cout<<"该结点的左兄弟结点值为："<<T.GetLeftSibling(node4)<<endl;system("pause");break;case 8:cout<<"请输入结点值："int node5;cin>>node5;cout<<"该结点的右兄弟结点值为：&q

43、uot;<<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();/第一个参数是根结点指针，第

44、二个参数为默认的1 cout<<endl;system("pause");break;default:break;while(op!=0);break;case 4:int op2;docout<<" -4 对二叉树进行操作-"<<endl;cout<<"0. 返回主菜单"<<endl;cout<<"1. 销毁二叉树"<<endl;cout<<"2. 给指定结点赋值"<<endl;cout

45、<<"3. 插入"<<endl;cout<<"4. 删除"<<endl;cout<<"5. 显示二叉树"<<endl;cout<<" -"<<endl;cout<<"请选择操作： "cout<<"bb"cin>>op2;switch(op2)case 0:break;case 1:T.ClearBiTree();cout<<"

46、;已经将二叉树销毁！"<<endl;system("pause");break;case 2:int ChangeValue;/要改变的结点值int NewValue;/修改之后的结点值cout<<"请输入要修改的结点值："cin>>ChangeValue;cout<<"请输入修改之后的结点值："<<endl;cin>>NewValue;if(T.SearchNode(ChangeValue) (T.SearchNode(ChangeValue)->

47、;data=NewValue;cout<<"修改成功！"<<endl;elsecout<<"修改失败！"<<endl;system("pause");break;case 3:cout<<"请创立一棵没有右子树的二叉树："<<endl;t.CreateBiTree(-1);cout<<"请输入要插入的二叉树的结点值"<<endl;int invalue;cin>>invalue;cout&

48、lt;<"请选择插入左子树0还是右子树1"int lr;cin>>lr;if(T.SearchNode(invalue)&&t.GetRoot()&&(t.GetRoot()->rchild)=NULL)t.InsertChild(T.SearchNode(invalue),t.GetRoot(),lr);cout<<"操作成功！"<<endl;cout<<"操作以后的二叉树为："<<endl;t.PreTraBiTree();elsecout<<"操作失败！"<&l