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

《数据结构——二叉树基本操作源代码》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构二叉树基本操作(1).//对二叉树的基本操作的类模板封装//------------------------------------------------------------------------------------------------------------------------#includeusingnamespacestd;//------------------------------------------------------------------------------

2、------------------------------------------//定义二叉树的结点类型BTNode,其中包含数据域、左孩子，右孩子结点。templatestructBTNode{Tdata;//数据域BTNode*lchild;//指向左子树的指针BTNode*rchild;//指向右子树的指针};//---------------------------------------------------------------------------------------------------

3、---------------------//CBinary的类模板templateclassBinaryTree{BTNode*BT;public:BinaryTree(){BT=NULL;}//构造函数,将根结点置空~BinaryTree(){clear(BT);}//调用Clear()函数将二叉树销毁voidClearBiTree(){clear(BT);BT=NULL;};//销毁一棵二叉树voidCreateBiTree(Tend);//创建一棵二叉树，end为空指针域标志boolIsEmpty();/

4、/判断二叉树是否为空intBiTreeDepth();//计算二叉树的深度boolRootValue(T&e);//若二叉树不为空用e返回根结点的值，函数返回true，否则函数返回falseBTNode*GetRoot();//二叉树不为空获取根结点指针，否则返回NULLboolAssign(Te,Tvalue);//找到二叉树中值为e的结点，并将其值修改为value。TGetParent(Te);//若二叉树不空且e是二叉树中的一个结点那么返回其双亲结点值TGetLeftChild(Te);//获取左孩子结点值TGetRigh

5、tChild(Te);//获取右孩子结点值TGetLeftSibling(Te);//获取左兄弟的结点值Trightsibling(BTNode*p,Te);TGetRightSibling(Te);//获取右孩子的结点值boolInsertChild(BTNode*p,BTNode*c,intRL);//插入操作boolDeleteChild(BTNode*p,intRL);//删除操作voidPreTraBiTree();//递归算法：先序遍历二叉树voidInTraBiTree();//递归算法：中序遍历

6、二叉树voidPostTraBiTree();//递归算法：后序遍历二叉树voidPreTraBiTree_N();//非递归算法：先序遍历二叉树voidInTraBiTree_N();//非递归算法：中序遍历二叉树voidLevelTraBiTree();//利用队列层次遍历二叉树intLeafCount();//计算叶子结点的个数BTNode*SearchNode(Te);//寻找到结点值为e的结点，返回指向结点的指针voidDisplayBTreeShape(BTNode*bt,intlevel=1);};//二叉树

7、的树形显示算法templatevoidBinaryTree::DisplayBTreeShape(BTNode*bt,intlevel){if(bt)//空二叉树不显示{DisplayBTreeShape(bt->rchild,level+1);//显示右子树cout<data;//显示节点DisplayBTreeShape(bt->lchild,level+1);

8、//显示左子树}//if}//DisplayBTreetemplatestaticintclear(BTNode*bt){//销毁一棵二叉树if(bt)//根结点不空{clear(bt->lchil