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

1、数据结构二叉树基本操作(1)./-对二叉树的基本操作的类模板封装#in cludeusing n amespace std;/-II定义二叉树的结点类型 BTNode,其中包含数据域、左孩子，右孩子结点。template struct BTNodeT data ;/数据域BTNode* Ichild;指向左子树的指针BTNode* rchild;指向右子树的指针；/- /CBinary 的类模板template class Bin aryTreeBTNode* BT;public:BinaryTree()BT=NULL;/构造函数，将根结点置空BinaryTree()clear(BT);/ 调

2、用 Clear()函数将二叉树销毁void ClearBiTree()clear(BT);BT=NULL; / 销毁一棵二叉树void CreateBiTree(T end);/ 创建一棵二叉树，end 为空指针域标志bool lsEmpty();/判断二叉树是否为空int BiTreeDepth();/计算二叉树的深度bool RootValue(T &e);/若二叉树不为空用e 返回根结点的值，函数返回 true,否则函数返回 falseBTNode*GetRoot();/二叉树不为空获取根结点指针，否则返回 NULLbool Assign(T e,T value);/找到二叉树中

3、值为 e 的结点，并将其值修改为 value。T GetLeftChild(T e);II获取左孩子结点值T GetRightChild(T e);II 获取右孩子结点值T GetLeftSibling(T e);II 获取左兄弟的结点值T rightsibli ng(BTNode*p,T e);T GetRightSibling(T e);II 获取右孩子的结点值bool In sertChild(BTNode* p,BTNode* c,int RL);II 插入操作 bool DeleteChild(BTNode* p,i nt RL);II删除操作void DisplayBTreeSha

4、pe(BTNode*bt,int level=1);二叉树的树形显示算法template void Bin aryTree:DisplayBTreeShape(BTNode*bt,i nt level) if(bt)II 空二叉树不显示 DisplayBTreeShape(bt-rchild,level+1); 显示右子树 coutvve ndl; 显示新行for(int i=0;ilevel-1;i+)cout; II 确保在第 level 列显示节点coutdata; /I 显示节点DisplayBTreeSh ape(bt-lchild,level+1);II 显示左子树IIifIIDi

5、splayBTree template static in t clear(BTNode*bt)销毁一棵二叉树if(bt)II 根结点不空clear(bt-lchild); 递归调用 Clear()函数销毁左子树 clear(bt-rchild); 递归调用 Clear()函数销毁右子树 coutvv释放了指针vvbtvv所指向的空间。endl; delete bt; 释放当前访问的根结点return 0;T GetPare nt(T e);中的一个结点那么返回其双亲结点值/若二叉树不空且e 是二叉树void PreTraBiTree();void In TraBiTree();void Po

6、stTraBiTree();void PreTraBiTree_N();void In TraBiTree_N();void LevelTraBiTree(); intLeafCou nt();BTNode* SearchNode(T e);点，返回指向结点的指针II 递归算法：先序遍历二叉树II 递归算法：中序遍历二叉树II 递归算法：后序遍历二叉树II 非递归算法：先序遍历二叉树II 非递归算法：中序遍历二叉树II 利用队列层次遍历二叉树II 计算叶子结点的个数II 寻找到结点值为 e 的结template vclass Tvoid Bin aryTree:CreateBiTree(T e

7、nd)创建一棵二叉树：先序序列的顺序输入数据， end 为结束的标志coutvv请按先序序列的顺序输入二叉树，-1 为空指针域标志：e ndl; BTNode*p;T x;cin x;输入根结点的数据if(x=e nd) return ;/end 表示指针为空，说明树为空p=new BTNode; / 申请内存if(!p)cout申请内存失败！ data=x; p-lchild=NULL; p-rchild=NULL;BT=p;根结点create(p,1,e nd);/创建根结点左子树，1 为标志，表示左子树 create(p,2,end);/创建根结点右子树，2 为标志，表示右子树templ

8、ate static int create(BTNode*p,i nt k,T end)/静态函数，创建二叉树，k 为创建左子树还是右子树的标志，end 为空指针域 的标志BTNode*q;T x;cin x;if(x!=e nd)先序顺序输入数据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,e nd);/递归创建左子树create(q,2,e nd);/递归创建右子树return 0;template

9、 vclass Tbool Bi naryTree:lsEmpty()/判断二叉树是否为空 if(BT=NULL) return true;/树根结点为空，说明树为空 return false;template int Bin aryTree:BiTreeDepth()/利用递归算法计算树的深度BTNode*bt=BT; 树根结点int depth=O;开始的时候数的深度初始化为 0if(bt)/如果树不为空 Depth(bt,1,depth); return depth;template static int Depth(BTNode* p,int level,int &depth)

10、这个函数由 BiTreeDepth()函数调用完成树的深度的计算其中 p 是根结点，Level 是层，depth 用来返回树的深度 if(leveldepth) depth=level;if(p-lchild) Depth(p-lchild,level+1,depth); 递归的遍历左子树，并且层数加 1 if(p-rchild)Depth(p-rchild,level+1,depth);/递归的遍历右子树，并且层数加1return 0;template bool Bin aryTree:RootValue(T &e)/若二叉树不为空用 e 返回根结点的值，函数返回 true,否则函数

11、返回 false if(BT!=NULL)判断二叉树是否为空e=BT-data; /若不空，则将根结点的数据赋值给ereturn true;/操作成功，返回 true return false; 二叉树为空，返回 falsetemplate BTNode*Bi naryTree:GetRoot()/获取根信息return BT;返回根结点的指针，若二叉树为空那么返回NULL template vclass Tbool Bin aryTree:Assig n(T e,T value) /结点赋值if(SearchNode(e)!=NULL)(SearchNode(e)-data=value;re

12、turn true; return false;template T Bin aryTree:GetPare nt(T e)/获取双亲信息BTNode*Queue200,*p; int rear,fr ont;rear=fr on t=0;if(BT)Queuerear+=BT; while(rear!=fro nt)p=Queuefr on t+;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)

13、 Queuerear+=p-rchild;return NULL; template T Bin aryTree:GetRightChild(T e)/如果二叉树存在，e 是二叉树中的一个结点，右子树存在那么返回右子树的结 点值，否则返回 0 并提示右子树为空BTNode*p=SearchNode(e);if(p-rchild) return p-rchild-data;/右子树不空，返回右子树根结点的值cout结点e的右子树为空endl; return 0;template T Bin aryTree:GetLeftChild(T e)/如果二叉树存在，e 是二叉树中的一个结点，左子树存在那

14、么返回左子树的结 点值，否则返回 0 并提示左子树为空BTNode*p=SearchNode(e);if(p-lchild) return p-lchild-data;cout结点e的左子树为空endl;return 0; template T Bin aryTree:GetLeftSibl in g(T e)/获取左兄弟信息if(BT!=NULL)return leftsibli ng(BT,e);else/二叉树为空cout二叉树为空！ e ndl; return 0; template T leftsibling(BTNode*p,T e)T q=0;if(p=NULL) retur n

15、 0;elseif(p-rchild)if(p-rchild-data=e)if(p-lchild) return p-lchild-data;elsereturn NULL; q=leftsibli ng(p-lchild,e); if(q)return q;q=leftsibli ng(p-rchild,e);if(q)return q;return 0;/- template T BinaryTree:GetRightSibling(T e)/获取右兄弟信息if(BT!=NULL)return rightsibli ng(BT,e);else/二叉树为空cout二叉树为空！ e ndl;

16、return 0;template T BinaryTree:rightsibling(BTNode*p,T e)BTNode *q=SearchNode(e);BTNode *pp;if(q)pp=SearchNode(GetPare nt(e);if(pp)if(pp-rchild) return pp-rchild-data; else return 0;else return 0;return 0;template bool Bin aryTree:l nsertChild(BTNode* p,BTNode* c,int LR) /插入孩子if(P)if(LR=O)c-rchild=p

17、-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 Bin ar

18、yTree:PreTraBiTree()/先序遍历二叉树cout- e ndl;coutvv先序遍历二叉树:;BTNode*p;p=BT;根结点PreTraverse(p); /从根结点开始先序遍历二叉树 coute ndl;cout- e ndl;template static int PreTraverse(BTNode*p)if(p!=NULL)coutdatalchild); 递归的调用前序遍历左子树 PreTraverse(p-rchild); 递归的调用前序遍历右子树 return 0;/- template void Bin aryTree:l nTraBiTree()/中序遍历

19、二叉树cout- e ndl;coutvv中序遍历二叉树:;BTNode*p;p=BT;/根结点In Traverse(p);/从根结点开始中序遍历二叉树 coute ndl;cout- e ndl;template static int In Traverse(BTNode*p)if(p!=NULL)In Traverse(p-lchild);递归的调用中序遍历左子树coutdatarchild);递归的调用中序遍历右子树return 0;/- template void BinaryTree:PostTraBiTree()/后序遍历二叉树cout- e ndl;coutvv后序遍历二叉树:

20、;BTNode*p;p=BT;/根结点PostTraverse(p);/从根结点开始遍历二叉树coute ndl;cout- e ndl;template static int PostTraverse(BTNode*p)if(p!=NULL)PostTraverse(p-lchild);/递归调用后序遍历左子树PostTraverse(p-rchild);/递归调用后序遍历右子树 coutdata;输出结点上的数据return 0;/- template void Bin aryTree:PreTraBiTree_N()/ _cout- e ndl;coutvv先序(非递归)遍历二叉树得：;

21、BTNode *Stack200;利用指针数组作为栈 int top=0;BTNode*p=BT;/将根结点的指针赋值给 p while(p!=NULL|top!=0)while(p!=NULL) coutdatarchild; p=p-lchild;if(top!=0)p=Stack-top;coutn /-void Bin aryTree:l nTraBiTree_N()/非递归中序遍历二叉树一cout- e ndl;coutvv中序(非递归)遍历二叉树得：;int top=0;BTNode *Stack200;BTNode *p=BT;while(p|top)while(p)Stackt

22、op+=p; p=p-lchild; if(top) p=Stack-top; coutdatarchild;coutn- e ndl;/- template void Bin aryTree:LevelTraBiTree()/利用队列 Queue 层次遍历二叉树BTNode *Queue100;利用一维数组作为队列，存放结点的指针BTNode *b;endl;int fron t,rear;/指向队列的头和尾下标fron t=rear=0;/队列初始为空cout- e ndl;if(BT)/若二叉树不为空。Queuerea 叶+=BT; /二叉树的根结点指针进队列while(fro nt!=

23、rear)/ 队列不为空。b=Queuefro nt+;/队首的元素出队列if(b)coutdatavv; /输出结点的值 if(b-lchild) Queuerear+=b-lchild; 如果左子树不空，进队。if(b-rchild) Queuerear+=b-rchild; 如果右子树不空，进队。 coutn template int Bin aryTree:LeafC oun t()/计算叶子的个数int coun t=0;return Leaf(BT,co un t);template static int Leaf(BTNode* p,i nt & cou nt)/stat

24、ic int cou nt=O;静态变量，存放叶子结点的个数if(p) if(p-lchild=NULL&p-rchild=NULL)cou nt+; 判断是否为叶子结占八、Leaf(p-lchild,cou nt);/ 递归遍历左子树Leaf(p-rchild,cou nt);/ 递归遍历右子树retur n count;template BTNode* Bin aryTree:SearchNode(T e) /结点查询BTNode*t;if(BT)if(BT-data=e) retur n BT; t=search(BT-lchild,e);在左子树中查找 if(t)retur n

25、 t;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(b n-lchild,e);递归查找左子树 if(t) return t;t=search(b n-rchild,e);/递归查找右子树 if(t) return t;return NULL;/-(2) .#i ncludeBi naryTree.cpp #i ncludewi ndows.h int main(

26、)int Mai nMenu=-1;Bin aryTree T;Bin aryTree t; while(Mai nMen u!=6)system(cls);cout- 主菜单-e ndl;coutvv 1-创建二叉树（元素类型为整数）endlcout 2-树形显示二叉树 coutvv 3-获取二叉树信息 cout 4-对二叉树操作 coutvv 5-遍历二叉树 coutvv 6-退出endl;coutvv- vve ndl;coutvv 请选择操作：;coutMainMenu;switch(Mai nMenu)case 1:T.CreateBiTree(-l);break;case 2:coutvv下面显示的是一棵左转了 90 度的树!endl;【进入子菜单】【进入子菜单】【进入子菜单】vve ndl;vve ndl;vve ndl;T.DisplayBTreeShape(T.GetRoot();/第一个参数是根结点指针，第个参数为默认的 1coute ndl;system(pause);break;case 3: