VC++2012编程演练数据结构《23》二叉树排序

大灰狼

在计算机科学中，树是一种重要的非线性数据结构，直观地看，它是数据元素（在树中称为结点）按分支关系组织起来的结构。二叉树是每个节点最多有两个子树的有序树。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。值得注意的是，二叉树不是树的特殊情形。在图论中，二叉树是一个连通的无环图，并且每一个顶点的度不大于3。有根二叉树还要满足根结点的度不大于2。有了根结点后，每个顶点定义了唯一的根结点，和最多2个子结点。然而，没有足够的信息来区分左结点和右结点。
　在计算机科学中，二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用作二叉查找树和二叉堆或是二叉排序树。二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2的 i -1次方个结点；深度为k的二叉树至多有2^(k) -1个结点；对任何一棵二叉树T，如果其终端结点数(即叶子结点数)为n0，度为2的结点数为n2，则n0 = n2 + 1。
　尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形。
　　树和二叉树的2个主要差别：
　　1. 树中结点的最大度数没有限制，而二叉树结点的最大度数为2；
　　2. 树的结点无左、右之分，而二叉树的结点有左、右之分。
二叉树
基本形态
　　二叉树也是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态：
　　(1)空二叉树——(a)；
　　  (2)只有一个根结点的二叉树——(b)；
　　(3)只有左子树——(c)；
　　(4)只有右子树——(d)；
　　(5)完全二叉树——(e)
　　注意：尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形。
重要概念
　　(1)完全二叉树——若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。　
　　(2)满二叉树——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树,。
　　(3)深度——二叉树的层数，就是高度。
性质
　　(1) 在二叉树中，第i层的结点总数不超过2^(i-1)；
　　(2) 深度为h的二叉树最多有2^h-1个结点(h>=1)，最少有h个结点；
　　(3) 对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；
　　(4) 具有n个结点的完全二叉树的深度为int（log2n）+1
　　(5)有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：
　　若I为结点编号则 如果I<>1，则其父结点的编号为I/2；
　　如果2*I<=N，则其左儿子（即左子树的根结点）的编号为2*I；若2*I>N，则无左儿子；
　　如果2*I+1<=N，则其右儿子的结点编号为2*I+1；若2*I+1>N，则无右儿子。
　　(6)给定N个节点，能构成h(N)种不同的二叉树。
　　h(N)为卡特兰数的第N项。h(n)=C(n,2*n)/(n+1)。

　　（7）设有i个枝点，I为所有枝点的道路长度总和，J为叶的道路长度总和J=I+2i

打开IDE

我们创建一个工程

类的实现如下

[cpp] view plaincopy

• #if !defined(AFX_BTREE_H__B4CCC36F_6064_4F47_A8BD_7465B0F69EB7__INCLUDED_)  
• #define AFX_BTREE_H__B4CCC36F_6064_4F47_A8BD_7465B0F69EB7__INCLUDED_  
•   
• #if _MSC_VER > 1000  
• #pragma once  
• #endif // _MSC_VER > 1000  
•   
• //二叉树类定义btree.h  
• template<class T>class BTree {  
• private:  
•   BTree<T> *left;//左子树指针  
•   BTree<T> *right;//右子树指针  
• public:  
•      T data;//数据域  
•      //构造函数,初始化二叉树为空  
•      BTree() {left=right=NULL;}  
•      BTree(T item,BTree<T> *left1=NULL,  
•          BTree<T> *right1=NULL):data(item),  
•          left(left1),right(right1){ }  
•      BTree<T> *&Left(){return left;}  
•      BTree<T> *&Right(){return right;}  
•      //根据字符数组a的二叉树广义表建立对应的二叉树存储结构  
•      void CreateBTree(char* a);  
•      //判断二叉树是否为空  
•      bool BTreeEmpty() {return left==NULL;}  
•      //按任一种遍历次序输出二叉树中的所有结点  
•      void TraverseBTree(int mark);  
•      //用于遍历的递归函数  
•      void Traverse(BTree<T> *&BT,int mark);  
•      //求二叉树的深度  
•      int BTreeDepth();  
•      //用于求二叉树深度的递归函数  
•      int Depth(BTree<T> *&BT);  
•      //求二叉树中所有结点数  
•      int BTreeCount();  
•      //用于求二叉树中所有结点数的递归函数  
•      int Count(BTree<T> *&BT);  
•      //求二叉树中所有叶子结点数  
•      int BTreeLeafCount();  
•      //用于求二叉树中所有叶子结点数的递归函数  
•      int LeafCount(BTree<T> *&BT);  
•      //按照二叉树的一种表示方法输出整个二叉树  
•      void PrintBTree();  
•      //用于输出整个二叉树的递归函数  
•      void Print(BTree<T> *&BT);  
•      //用于清除二叉树的递归函数  
•      void Clear(BTree<T> *&BT);  
•      //析构函数，清除二叉树  
•      ~BTree();  
• };  
•   
• //二叉树类的实现  
• //根据字符数组a的二叉树广义表建立对应的二叉树存储结构  
• template<class T>  
• void BTree<T>::CreateBTree(char *a)  
• {BTree<T> *s[80];//s数组作为存储二叉树中根结点指针的栈  
• int top=-1;      //top作为s栈的栈顶指针  
• left=NULL;       //先将left作为树根指针给予置空  
• BTree<T> *p=NULL;//定义p为指向二叉树结点的指针  
• //用k作为处理结点的左子树和右子树的标记,k=1处理左子树,k=2处理右子树  
• int k;  
• istrstream ins(a);//把字符串a定义为输入字符串流对象ins  
• char ch;  
• ins>>ch;//从ins流对象顺序读入一个字符，  
• while (ch!='@')  
• {//每循环一次处理一个读入的字符,直到扫描到'@'字符为止  
•   switch(ch)  
•     {case '(':top++;s[top]=p;k=1;break;  
•      case ')':top--;break;  
•      case ',':top++;k=2;break;  
•      default:p=new BTree<T>;  
•        p->data=ch;p->left=p->right=NULL;  
•        cout<<setw(2)<<p->data;  
•        if(left==NULL) left=p;  
•        else {  
•     if(k==1) s[top]->left=p;  
•         else s[top]->right=p;}  
•     }  
•   ins>>ch;  
• }  
• }  
• //按任一种遍历次序输出二叉树中的所有结点  
• template<class T>  
• void BTree<T>::TraverseBTree(int mark)  
• {Traverse(left,mark);}  
•   
• //用于遍历的递归函数  
• template<class T>  
• void BTree<T>::Traverse(BTree<T> *&BT,int mark)  
• {if(mark==1){ //先序遍历  
•   if(BT!=NULL)  
•    {cout<<BT->data<<' ';  
•     Traverse(BT->left,mark);  
•     Traverse(BT->right,mark);  
•    }}  
• else  
•   if(mark==2)//中序遍历  
•    {if(BT!=NULL)  
•      {Traverse(BT->left,mark);  
•       cout<<BT->data<<' ';  
•       Traverse(BT->right,mark);  
•     }}  
•   else  
•    if(mark==3) {//后序遍历  
•      if(BT!=NULL) {  
•       Traverse(BT->left,mark);  
•       Traverse(BT->right,mark);  
•       cout<<BT->data<<' ';  
•     }}  
•   else  
•    if(mark==4) //按层遍历  
•     {  
•         const int MaxLength=80;  
•      BTree<T> *Q[MaxLength];  
•     //定义存储二叉树结点指针的数组空间作为队列使用  
•      int front=0, rear=0;  
•     //定义队首指针和队尾指针,初始均置0表示空队  
•     BTree<T> *p;  
•     if(BT!=NULL) {  
•      rear=(rear+1)%MaxLength;  //后移队尾指针  
•      Q[rear]=BT;}              //将树根结点指针进队  
•     while(front!=rear)  
•      {//当队列非空时执行循环  
•       front=(front+1)%MaxLength;  
•       //后移队首指针  
•       p=Q[front];  
•       //删除队首结点  
•       cout<<p->data<<' ';  
•       //输出队首结点的值  
•       if(p->left!=NULL)  
•        {//若结点存在左孩子，则左孩子结点指针进队  
•     rear=(rear+1)%MaxLength;  
•         Q[rear]=p->left;  
•        }  
•       if(p->right!=NULL)  
•        {//若结点存在右孩子,则右孩子结点指针进队  
•     rear=(rear+1)%MaxLength;  
•     Q[rear]=p->right;  
•        }  
•       }  
•      }  
•    else  
•     {cerr<<"mark的值无效!遍历失败!"<<endl;exit(1);  
• }}  
• //求二叉树的深度  
• template<class T>  
• int BTree<T>::BTreeDepth()  
• {return Depth(left);}  
•   
• //用于求二叉树深度的递归函数  
• template<class T>  
• int BTree<T>::Depth(BTree<T> *&BT)  
• {if(BT==NULL) return 0;//对于空树,返回0并结束递归  
• else  
•    {//计算左子树的深度  
•     int dep1=Depth(BT->left);  
•     //计算右子树的深度  
•     int dep2=Depth(BT->right);  
•     //返回树的深度  
•     if(dep1>dep2) return dep1+1;  
•     else return dep2+1;  
•    }  
• }  
• //求二叉树中所有结点数  
• template<class T>  
• int BTree<T>::BTreeCount()  
• {return Count(left);}  
•   
• //用于求二叉树中所有结点数的递归函数  
• template<class T>  
• int BTree<T>::Count(BTree<T> *&BT)  
• {if(BT==NULL) return 0;  
• else  
•   return Count(BT->left)+Count(BT->right)+1;  
• }  
• //求二叉树中所有叶子结点数  
• template<class T>  
• int BTree<T>::BTreeLeafCount()  
• {return LeafCount(left);}  
•   
• //用于求二叉树中所有叶子结点数的递归函数  
• template<class T>  
• int BTree<T>::LeafCount(BTree<T> *&BT)  
• {if(BT==NULL) return 0;  
• else if(BT->left==NULL && BT->right==NULL) return 1;  
•   else return LeafCount(BT->left)+LeafCount(BT->right);  
• }  
• //按照二叉树的广义表表示输出整个二叉树  
• template<class T>  
• void BTree<T>::PrintBTree()  
• {Print(left);}  
•   
• //用于输出整个二叉树的递归函数  
• template<class T>  
• void BTree<T>::Print(BTree<T> *&BT)  
• {if(BT==NULL) return;//树为空时返回  
• else {//否则执行如下操作  
•   cout<<BT->data;//输出根结点的值  
•   if(BT->left!=NULL || BT->right!=NULL)  
•    {if(BT->left!=NULL)  
•      cout<<'(';  //输出左括号  
•     Print(BT->left);//输出左子树  
•     if(BT->right!=NULL)  
•      cout<<',';//若右子树不为空则输出逗号分隔符  
•     Print(BT->right);//输出右子树  
•     if(BT->left!=NULL&&BT->right!=NULL)  
•      cout<<')';} //输出右括号  
• }}  
• //析构函数,清除二叉树  
• template<class T>  
• BTree<T>::~BTree()  
• {Clear(left);}  
• //用于清除二叉树的递归函数  
• template<class T>  
• void BTree<T>::Clear(BTree<T> *&BT)  
• {if(BT!=NULL)  
•    { //当二叉树非空时进行如下操作  
•     Clear(BT->left); //删除左子树  
•     Clear(BT->right);//删除右子树  
•     delete BT;       //删除根结点  
•     BT=NULL;}        //置根指针为空  
• }  
•   
•   
• #endif // !defined(AFX_BTREE_H__B4CCC36F_6064_4F47_A8BD_7465B0F69EB7__INCLUDED_)  
  

类的调用如下

[cpp] view plaincopy

• #include "stdafx.h"  
• #include "btree.h"  
•   
• void main()  
• {  
• cout<<"运行结果:\n";  
• int n;  
• char b[80]="(a)(b),c(d),e(f),g(h),i(j),k(l),m(n),o@";  
• BTree<char> B;  
• cout<<"创建的二叉树为:\n";  
• B.CreateBTree(b);cout<<endl;  
• if(!B.BTreeEmpty())  
• cout<<"二叉树非空!\n";  
• else  
• cout<<"二叉树为空!\n";  
• cout<<"先序遍历二叉树:\n";  
• B.TraverseBTree(1);cout<<endl;  
• cout<<"中序遍历二叉树:\n";  
• B.TraverseBTree(2);cout<<endl;  
• cout<<"后序遍历二叉树:\n";  
• B.TraverseBTree(3);cout<<endl;  
• cout<<"按层遍历二叉树:\n";  
• B.TraverseBTree(4);cout<<endl;  
• n=B.BTreeDepth();  
• cout<<"二叉树的深度="<<n<<endl;  
• n=B.BTreeCount();  
• cout<<"二叉树的所有结点数="<<n<<endl;  
• n=B.BTreeLeafCount();  
• cout<<"二叉树的所有叶子结点数="<<n<<endl;  
• cout<<"按二叉树的广义表输出:\n(";  
• B.PrintBTree();cout<<')'<<endl;  
• cin.get();  
• }  
  

效果如下