树

data_structure

终于，在半学期过后，跨入了树的学习。

一、简介

之前，我们已经学习了一对一的线性结构，而树，是一种一对多的结构，树的定义，可以理解为递归，每棵树包含了子树，依次类推。

我们这边讨论的是二叉树，较为简单，下面进行讨论。

二、顺序结构存储二叉树

因为二叉树的特性，我们可以用数组来存储，首先，满二叉树的表示非常简单，这边不做解释，一般二叉树，只需要把不逊在的结点设为^，那么存储很简单。
但是，如果我们考虑一种比较极端的情况，树高为K的右斜树，那么缺点显而易见，浪费极大的存储空间，我只需要存k个元素，却开辟了比其多的多的空间。所以，如果想用顺序结构，那么建议用在完全二叉树下面。这边不多做介绍。

三、二叉树的链式存储

既然顺序结构的缺点显而易见，那么我们考虑一种链式存储的方法，二叉树，每个节点最多有2个孩子，所以设计一个数据域和两个指针域，结构如下：

/*二叉树节点结构定义*/
template<class T>
struct BiNode           //节点结构
{
    T data;             //节点数据
    BiNode<T> *lchild;  //左右孩子指针
    BiNode<T> *rchild;
};

四、遍历二叉树

遍历东西，讲究的就是次序，对于一棵树遍历的基本要求，就是，不能漏掉某个节点，让每个节点有且仅被访问一次

看的出来，我们要做的就是，按照某种次序去访问这个树。
我们先考虑下，线性结构的访问，很简单，就是从头到尾依次访问，因为那是一种一对一的结构，而树的每个节点，并不是单一的前驱和后继的关系，所以在访问一个节点以后，我们要考虑下次访问哪个节点下面，我介绍4种访问方式。

4.1、先序遍历

• 若当前二叉树为空，返回；

• 若当前二叉树不为空，

  • 访问根节点，
  • 若存在左子树，先序遍历左子树，否则返回
  • 若存在右子树，先序遍历右子树，否则返回

• 若当前二叉树左右子树已经被访问过，返回

这是一个模拟的树，就着这棵树来介绍下过程：

首先来到树根A，A不是空树，访问根节点（输出A）；
然后遍历A左子树，即来到B，B不是空树，访问根节点（输出B）；
然后遍历B左子树，即来到D，D不是空树，访问根节点（输出D）；
然后遍历D左子树，即来到G，G不是空树，访问根节点（输出G）；
然后遍历G左子树，发现G无左子树，空操作返回，
然后遍历G右子树，发现G无右子树，空操作返回，
当前二叉树G左右子树已经被访问，返回到D，
然后遍历D右子树，即来到H，H不是空树，访问根节点（输出H）；
然后遍历H左子树，发现H无左子树，空操作返回，
然后遍历H右子树，发现H无右子树，空操作返回，
当前二叉树H左右子树已经被访问，返回到D;
当前二叉树D左右子树已经被访问，返回到B;
遍历B右子树，发现H无右子树，空操作返回，
当前二叉树B左右子树已经被访问，返回到A，
遍历A右子树，即来到C，C不是空树，访问根节点（输出C）；
然后遍历C左子树，即来到E，E不是空树，访问根节点（输出E）；
然后遍历E左子树，发现E无左子树，空操作返回，
然后遍历E右子树，即来到I，I不是空树，访问根节点（输出I）；
然后遍历I左子树，发现I无左子树，空操作返回，
然后遍历I右子树，发现I无右子树，空操作返回，
当前二叉树I左右子树已经被访问，返回到E;
当前二叉树E左右子树已经被访问，返回到C;
遍历C右子树，即来到F，F不是空树，访问根节点（输出F）；
然后遍历F左子树，发现F无左子树，空操作返回，
然后遍历F右子树，发现F无右子树，空操作返回，
当前二叉树F左右子树已经被访问，返回到C;
当前二叉树C左右子树已经被访问，返回到A;
当前二叉树A左右子树已经被访问，由于A是树根，遍历结束;

所以这个遍历顺序访问输出的结果:ABDGHCEIF
根据前面所给的一些访问次序，很容易写出C代码

/*先序遍历对外接口*/
template<class T>
void BiTree<T>::PreOrder()
{   
    PreOrder(root); //从顶层开始遍历
}
template<class T>
void BiTree<T>::PreOrder(BiNode<T> *p)
{
    if(p==NULL)             //如果树空，空操作返回
        return;
    cout<<p->data;          //否则访问根节点
    PreOrder(p->lchild);    //前序遍历左子树
    PreOrder(p->rchild);    //前序遍历右子树
}

4.2、中序遍历

• 若当前二叉树为空，返回；

• 若当前二叉树不为空，

  • 若存在左子树，中序遍历左子树，否则返回
  • 访问根节点，
  • 若存在右子树，中序遍历右子树，否则返回

• 若当前二叉树左右子树已经被访问过，返回

还是刚刚那棵树，再次介绍：

首先来到树根A，A不是空树，A存在左子树，前序遍历左子树B；
即来到树B，B不是空树，B存在左子树，前序遍历左子树D；
即来到树D，D不是空树，D存在左子树，前序遍历左子树G；
即来到树G，G不是空树，G不存在左子树，访问G节点（输出G）；
G不存在右子树，返回到D，访问D节点（输出D）；
D存在右子树，遍历D右子树，
即来到树H，H不是空树，H不存在左子树，访问H节点（输出H）；
H不存在右子树，返回到D；
D左右子树均被访问，返回到B，访问B节点（输出B）；
B不存在右子树，此时B的左右子树均访问，返回到A，访问A节点（输出A）；
A存在右子树， 遍历右子树C；
C不空，存在左子树E，遍历左子树E；
E无左子树，返回，访问E节点（输出E）；
遍历E右子树，即来到I，I没有左子树，访问I节点（输出I）；
I没有右子树，此时I左右子树均访问，返回到E；
此时E左右子树均访问，返回到C,访问C节点（输出C）；
访问C右子树，来到F，F没有左子树，访问F节点（输出F）；
F没有右子树，此时F左右子树均访问，返回到C；
此时C左右子树均访问，返回到A；
此时A左右子树均访问，这是树根，完成访问；

所以中序遍历顺序访问输出的结果:GDHBAEICF
代码也很容易：

/*中序遍历对外接口*/
template<class T>
void BiTree<T>::InOrder()
{
    InOrder(root);//从顶层开始遍历
}
template<class T>
void BiTree<T>::InOrder(BiNode<T> *p)
{
    if(p==NULL)
        return ;//如果树空，空操作返回
    InOrder(p->lchild);//中序遍历左子树
    cout<<p->data;//访问根节点
    InOrder(p->rchild);//中序遍历右子树
}

4.3、后序遍历

• 若当前二叉树为空，返回；

• 若当前二叉树不为空，

  • 若存在左子树，中序遍历左子树，否则返回
  • 若存在右子树，中序遍历右子树，否则返回
  • 访问根节点，

• 若当前二叉树左右子树已经被访问过，返回

流程不再介绍，同样一棵树，后续遍历的结果是：GHDBIEFCA；
代码如下：

/*后序遍历对外接口*/
template<class T>
void BiTree<T>::PostOrder()
{
    PostOrder(root);
}
template<class T>
void BiTree<T>::PostOrder(BiNode<T> *p)
{
    if(p==NULL)
        return ;
    PostOrder(p->lchild);
    PostOrder(p->rchild);
    cout<<p->data;
}

4.4、层序遍历

规则相对前面几个好理解，一层层遍历，每层中从左到右遍历，
对于那棵树，很明显遍历序列就是：ABCDEFGHI
下面来介绍下这种遍历的实现：
借由队列，从树根开始，每次输出自己，然后把左右孩子指针入队，
如若队列不空，则重复操作；

template <class T>
void BiTree<T>::LevelOrder()        //非递归
{
    if(root==NULL)
        return;
    queue<BiNode<T> *> Q;
    Q.push(root);                   //队列定义及初始化
    while(!Q.empty())
    {
        BiNode<T>* p=Q.front();
        Q.pop();                    //进队列
        cout<<p->data<<"  ";        //输出
        if(p->lchild)               //左结点进队列
            Q.push(p->lchild);
        if(p->rchild)               //右结点进队列
            Q.push(p->rchild);
    }
}

五、生成二叉树

前面先将了如何去遍历一颗二叉树，但是如果树不能建立，学会了遍历也没用。

5.1、空构造函数

制造一颗空树，根节点为空即可。

template<class T>
BiTree<T>::BiTree()
{
    root=NULL;
}

5.2、先序构造

我们为了建立一棵树，需要补全每棵树的左右孩子，若没有需要用*来代替，代码和遍历差不多，只是把其中的输出部分换成了生成节点的部分。核心思想还是用递归来实现的，用特殊符号来表示返回空指针，否则就串在一起.

template<class T>
BiTree<T>::BiTree(vector<T> &pre)
{
    int i=0;
    root=CreateByPre(pre,i);
}
/*先序构造*/
template <class T>
BiNode<T> * BiTree<T>::CreateByPre(vector<T>&pre,int &i)
{
    T e=pre[i];
    i++;
    if(e=='*')
        return NULL;
    BiNode<T>*p=new BiNode<T>;
    p->data=e;
    p->lchild=CreateByPre(pre,i);
    p->rchild=CreateByPre(pre,i);
    return p;
}

5.3、先序中序构造

这个还是比较好理解的，
假设我得到了先序的结果和中序的结果：
先序：ABDGHCEIF
中序：GDHBAEICF
首先从先序中找到第一个字符A，找到在中序的位置，分为左右子树
先：左：BDGH 右：CEIF
中：左：GDHB 右：EICF

再细分
先：BDGH
中：GDHB
先：左：DGH 右：无
中：左：GDH 右：无
如此类推即可。
代码如下：

template<class T>
BiTree<T>::BiTree(vector<T> &pre ,vector<T> &mid)
{
    n=pre.size();
    root=CreatByPreMid(pre,mid,0,0,n);
}
template<class T>
BiNode<T> * BiTree<T>::CreateByPreMid
(vector<T>&pre ,vector<T> &mid,int ipre,int imid,int n)
{
    if(n==0)
        return NULL;
    BiNode<T> *p=new BiNode<T>;
    p->data=pre[ipre];
    for(int i=0;i<n;i++)            //在中序序列中定位根结点
    {
        if(pre[ipre]==mid[imid+i])
            break;
    }
    p->lchild=CreatByPreMid(pre,mid,ipre+1,imid,i);
    p->rchild=CreatByPreMid(pre,mid,ipre+i+1,imid+i+1,n-i-1);
    return p;
}

5.4、拷贝构造函数

利用递归，大问题化小、

template<class T>
BiTree<T>::BiTree(BiTree<T>&tree)
{   
    root=Copy(tree,root);   
}
template<class T>
BiNode<T>* BiTree<T>::Copy(BiNode<T>*p)
{
    if(p==NULL)
        return NULL;
    BiNode<T> *newTree=new BiNode<T>;
    newTree->data=p->data;
    newTree->lchild=Copy(p->lchild);
    newTree->rchild=Copy(p->rchild);
    return newTree;
}

六、二叉树的一些功能性函数

6.1、计算节点个数

思路很简单，计算当前树左子树节点个数，右子树节点个数，相加起来，最后算上自身就可以了，实为递归过程。

/*计算节点个数*/
template<class T>
int BiTree<T>::Count()
{
    return Count(root);
}
template<class T>
int BiTree<T>::Count(BiNode<T>*p)
{
    if(p==NULL)
        return 0;
    int left =Count(p->lchild);
    int right=Count(p->rchild);
    return left+right+1;
}

6.2、计算树的高度

思路也很简单，记录当前左子树的高度，记录当前右子树的高度，返回较大值+1；

/*计算树高*/
template<class T>
int BiTree<T>::Height()
{
    return Height(root);
}
template<class T>
int BiTree<T>::Height(BiNode<T> *p)
{
    if(p==NULL)
        return 0;
    int left=Height(p->lchild);
    int right=Height(p->rchild);
    if(left>=right)
        return left+1;
    else
        return right+1;
}

6.3、根据值e查找结点

在整棵树中查找，若自身是，返回自身节点，否则查找左子树，左子树能查到，返回，否则查找右子树。

template <class T>
BiNode<T> *BiTree<T>::Search(T e)
{
    return Search(root,e);
}
template<class T>
BiNode<T>* BiTree<T>::Search(BiNode<T> *p,T e)
{
    if(p==NULL)         //整棵树空。查找失败，返回上一层
        return NULL;
    if(p->data==e)      //当前节点值正确，返回当前节点
        return p;
    BiNode <T> *q=Search(p->lchild,e);  //若此节点不空，并且此节点数据不匹配，找左子树
    if(q!=NULLL)            //若左边找到了，返回找到的节点给上一层。
        return q;
    return Search(p->rchild,e); //若左边没找到，返回右子树找到的结果，可以为NULL,可以为节点、
}

6.4、查找父节点

自上而下，深度优先查找。
这边要注意个问题，书上并没有提到，如果我传入的节点是非法节点，或者是树根节点，程序不能相应。

template <class T>
BiNode<T>* BiTree<T>::SearchParent(BiNode<T>*child)
{
    return SearchParent(root,child);
}
template<class T>
BiNode<T>* BiTree<T>::SearchParent(BiNode<T>*p,BiNode<T>*child)
{   //  自上而下查找
    if(p==NULL||child==NULL)            //空--空。
        return NULL;
    if(p->lchild==child||p->rchild==child)  //当前节点是否满足条件？返回当前节点：查找子树;
    {
        return p;
    }
    BiNode<T>*q=SearchParent(p->lchild,child);
    if(q!=NULL)
        return q;
    return SearchParent(p->rchild,child);
}

6.5、释放空间

用于析构时候，释放所有申请的空间。
也是用于递归释放。

template<class T>
BiTree<T>::~BiTree()
{
    Free(root);
}
template<class T>
void BiTree<T>::Free(BiNode<T>* p)
{
    if(p==NULL)
        return ;
    Free(p->lchild);
    Free(p->rchild);
    delete p;
    p=NULL;
}

七、测试

int main()
{
    vector<char> a;
    char b[20]="ab*c**de**f**";
    char c[20]="ABDG**H***CE*I**F**";
    cout<<"树的前序向量："<<c<<endl;
    for (int i = 0; i < 19; i++)
    {
        a.push_back(c[i]);
    }
    BiTree<char> Tree(a);
//  Tree.Print();
    cout<<endl;
    cout<<endl;
    cout<<"先序遍历：";
    Tree.PreOrder();
    cout<<endl;
    cout<<"中序遍历：";
    Tree.InOrder();
    cout<<endl;
    cout<<"后序遍历：";
    Tree.PostOrder();
    cout<<endl;
    cout<<"层序遍历：";
    Tree.LevelOrder();
    cout<<endl;
    cout<<"结点数：";
    cout<<Tree.Count()<<endl;
    cout<<"树高度：";
    cout<<Tree.Height()<<endl;
    cout<<"根据值e查找结点(找不到返回空)：";
    BiNode<char> *tmp;
    tmp=Tree.Search('H');
    cout<<tmp<<endl;
    cout<<"查找上述节点父节点：";
    BiNode<char> *tmp1=Tree.SearchParent(tmp);
    if (tmp1!=NULL)
        cout<<tmp1->data<<endl;
    else
        cout<<tmp1<<endl;
    return 0;
}

测试用的还是那棵树

结果：