二叉树原

青木

发布于 2018-10-09 16:00:41

4500

发布于 2018-10-09 16:00:41

文章被收录于专栏：我是业余自学C/C++的我是业余自学C/C++的

二叉树和树的根本区别

二叉树的每个元素都恰好有两棵子树（其中一个或两个可能为空）。而树的每个元素可有任意数量的子树。
在二叉树中，每个元素的子树都是有序的。也就是说，有左子树和右子树之分。而树的子树是无序的.

二叉树的特性

特性1 一棵二叉树有n个元素，n>=0，它有n-1条边。
证明二叉树的每个元素（除了根节点）有且仅有一个父节点。在子节点与父节点间有且只有一条边，因此边数为n-1。

特性2 一棵二叉树的高度为h，h>=0,它最少有h个元素，最多有2^h-1个元素。
证明二叉树每一级最少有1个元素，因此元素的个数最少为h。每个元素最多有2个子节点，则第i层元素最多为2^（i-1）个，i>0.则2^0+2^1+2^2+……+2^h=2^h-1.所以h层元素的总数最大为2^h-1.

特性3 一棵二叉树有n个元素，n>0，它的高度最大为n，最小高度为log2(n+1)向上取整。
证明因为每层至少有一个元素，因此高度不不会超过n。高度为h的二叉树最多有2^h-1个元素。因为n<=2^h-1，所以，h>=log2(n+1)。由于h是整数，所以log2(n+1)要向上取整。及最小高度为log2(n+1)向上取整。

当高度为h的二叉树恰好有2^h-1个元素时，称其为满二叉树。

对高度为h的满二叉树的元素，从第一层到最后一层，在每一次中从左至右，顺序编号，从1到2^h-1.假设从满二叉树中删除k个其编号为2^h-i元素，1<=i<=k<2^h，所得到的二叉树被称为完全二叉树。

满二叉树是完全二叉树的一个特例。

特性4 设完全二叉树的某一元素编号为i,1<=i<=n。有以下关系成立：

如果i=1，则该元素为二叉树的根。若i>1，则其父亲节点的编号为i/2向下取整。
如果2i>n，则该元素无左孩子。否则，其左孩子的编号为2i
如果2i+1>n,则该元素无右孩子。否则，其右孩子的编号为2i+1.

二叉树的常用操作

二叉树的常用操作有：

确定高度
确定元素数目
复制
显示或打印二叉树
确定两棵二叉树是否一样
删除整棵树

所有的这些操作都可以通过二叉树的遍历来完成。在二叉树的遍历中，每个元素仅被访问一次。

二叉树的遍历

二叉树的遍历常用的有如下四种方法：

前序遍历
中序遍历
后序遍历
层次遍历

**二叉树的中序遍历和先序遍历、中序遍历和后序遍历可以唯一确定一棵二叉树。**除此之外，任意两种遍历方式结合都无法唯一确定一棵树。

先序遍历、中序遍历、后序遍历可以方便的使用栈来实现，所以可以使用递归实现。但是，层次遍历的本质其实是队列，所以用递归实现会比较困难。

二叉树的描述

二叉树可以用两种方式来描述：数组和链表

数组描述将二叉树中的元素从上到下、从左到右顺序编号。
一个有n个元素的二叉树可能最多需要2^n-1个空间来存储。最坏的情况是，每层只有一个元素，n个元素的二叉树就有n层。n层二叉树存储需要的空间个数即为满二叉树的元素个数。用数组来表示二叉树的时候，空节点也是要存储在数组中的，因为数组不仅要存储元素，还要存储元素的相对关系。二叉树的数组表示如下：

链表描述二叉树最常用的表示方法是指针。每个元素用一个节点表示，节点有两个指针域，分别称为leftChild（左孩子）和rightChild（右孩子）.除此之外，还有一个用来element域，用来存储当前节点的值。 n个节点，每个节点有2个指针，则一棵二叉树共有2n个指针。父节点的每一个指向孩子的指针表示一条边，则n个元素的二叉树共有n-1条边。所以，二叉树一共会有2n-(n-1)=n+1个指针域没有值，它们被置为NULL。

如下图，二叉树的链表表示：

从根节点开始，沿着leftChild和rightChild指针域，可以访问二叉树的所有节点。二叉树的链式表示没有指向父节点的指针，因为大部分函数不需要这样的指针。若某些应用需要这种指针，可以在每个节点再添加一个指针域。

下面是二叉树的具体代码实现：

/*
 * 二叉树遍历操作
 *binaryTreeTraversals.cpp
*/
#include<iostream>
#include"arrayqueue.h"
#include"binarytreenode.h"
#include"myexceptions.h"

using namespace std;

//访问二叉树节点的元素
template <class T>
void visit(binaryTreeNode<T> *x)
{
    cout << x->element <<' ';
}

//先序遍历
template <class T>
void preOrder(binaryTreeNode<T> *t)
{
    if( t != NULL)
    {
        visit(t);
        preOrder(t->leftChild);
        preOrder(t->rightChild);
    }
}

//中序遍历
template <class T>
void inOrder(binaryTreeNode<T> *t)
{
    if(t != NULL)
    {
        inOrder(t->leftChild);
        visit(t);
        inOrder(t->rightChild);
    }
}

//后序遍历
template <class T>
void postOrder(binaryTreeNode<T>* t)
{
    if(t != NULL)
    {
        postOrder(t->leftChild);
        postOrder(t->rightChild);
        visit(t);
    }
}

//层次遍历
/*
 * 层次遍历跟前面三种遍历不同，用递归比较难实现，适合用队列来实现
*/
template <class T>
void levelOrder(binaryTreeNode<T>* t)
{
    arrayQueue<binaryTreeNode<T>*> q;
    while( t != NULL)
    {
        visit(t);

        if(t->leftChild != NULL)//坐孩子入队
            q.push(t->leftChild);
        if(t->rightChild != NULL)//右孩子入队
            q.push((t->rightChild));

        try{ t = q.front();}//出队操作
        catch(queueEmpty){return;}
        q.pop();
    }
}


int main(void)
{
    binaryTreeNode<int> *x,*y,*z;
    y = new binaryTreeNode<int> (2);
    z = new binaryTreeNode<int> (3);
    x = new binaryTreeNode<int> (1,y,z);

    //中序遍历的输出结果
    cout<<"Inorder sequence is ";
    inOrder(x);
    cout <<endl;

    //先序遍历的结果
    cout<<"Preorder sequence is";
    preOrder(x);
    cout <<endl;

    //后序遍历
    cout<<"Postorder sequence is";
    postOrder(x);
    cout<<endl;

    //层次遍历
    cout<<"Level order sequence is";
    levelOrder(x);
    cout<<endl;

    cout <<"Hello World!"<<endl;
    return 0;

}

/*
 * 二叉树节点定义
 * binaryTreeNode.h
*/
#ifndef BINARYTREENODE_H
#define BINARYTREENODE_H

#include<iostream>
using namespace std;

template <class T>
struct binaryTreeNode
{

    T element;
    binaryTreeNode<T> *leftChild,
                      *rightChild;

    binaryTreeNode()
    {
        leftChild = rightChild = NULL;
    }

    binaryTreeNode(const T& theElement):element(theElement)
    {
        leftChild = rightChild = NULL;
    }

    binaryTreeNode(const T& theElement,
                   binaryTreeNode *theLeftChild,
                   binaryTreeNode *theRightChild):element(theElement)
    {
        leftChild = theLeftChild;
        rightChild = theRightChild;
    }
};


#endif // BINARYTREENODE_H

/*
 * 二叉树的定义
 * 二叉树主要的操作是遍历，这个在搜索、排序算法中很常用
 * binaryTree.h
 *
*/
#ifndef BINARYTREE_H
#define BINARYTREE_H

#include<functional>

using namespace std;

template <class T>
class binaryTree
{
public:
    virtual ~binaryTree() {}
    virtual bool empty() const = 0;
    virtual int size() const = 0;
    virtual void preOrder(void(*) (T *)) = 0;//先序遍历
    virtual void  inOrder(void(*)(T *)) = 0;//中序遍历
    virtual void postOrder(void(*)(T *)) = 0;//后序遍历
    virtual void levelOrder(void(*)(T *)) = 0;//层次遍历
};

#endif // BINARYTREE_H

/*
 * 队列的定义
 * queue.h
*/
#ifndef QUEUE_H
#define QUEUE_H

#include<iostream>
using namespace std;

template <class T>
class queue
{
public:
    virtual ~queue(){}
    virtual bool empty() const = 0;
    virtual int size() const = 0;
    virtual T& front() = 0;//队首
    virtual T& back() = 0;//队尾
    virtual void pop() = 0;//出队
    virtual void push(const T& theElement) = 0;//入队
};


#endif // QUEUE_H

/*
 * 用数组表示队列
 * arrayQueue.h
*/
#ifndef ARRAYQUEUE_H
#define ARRAYQUEUE_H

#include"queue.h"
#include"myexceptions.h"
#include<sstream>

using namespace std;

template <class T>
class arrayQueue:public queue<T>
{
public:
    arrayQueue(int initialCapacity = 10);
    ~arrayQueue(){delete [] queue;}

    bool empty() const{return theFront == theBack;}//当队首和队尾相等时，表示队空
    int size() const
    {
        return (theBack - theFront + arrayLength)%arrayLength;//
    }

    T& front()//队首元素
    {
        if(theFront == theBack)
            throw queueEmpty();//判断队空
        return queue[(theFront+1)%arrayLength];
    }

    T& back()//队尾元素
    {
        if(theFront == theBack)
            throw queueEmpty();
        return queue[theBack];
    }

    void pop()//出队
    {
        if(theFront == theBack)
            throw queueEmpty();
        theFront = (theFront+1)%arrayLength;
        queue[theFront].~T();
    }

    //入队的实现比较复杂一些，考虑的情况比较多
    void push(const T& theELement)//入队
    {
        //如果队满的时候，队列的容量扩充一倍
        if((theBack + 1) % arrayLength == theFront)
        {
            T* newQueue = new T[2*arrayLength];

            int start = (theFront + 1)%arrayLength;
            if(start < 2)
                copy(queue+start,queue+arrayLength,newQueue);
            else
            {
                copy(queue + start,queue + arrayLength,newQueue);
                copy(queue,queue+theBack+1,newQueue+arrayLength - start);
            }

            theFront = 2 * arrayLength - 1;
            theBack = arrayLength - 2;
            arrayLength *=2;
            queue = newQueue;
        }
        theBack = (theBack + 1)%arrayLength;
        queue[theBack] = theELement;
    }


private:
    int theFront;//队首
    int theBack;//队尾
    int arrayLength;//数组长度
    T* queue;//存储元素的数组
};

template <class T>
arrayQueue<T>::arrayQueue(int inititalCapacity)
{
    if(inititalCapacity < 1)
    {
        ostringstream s;
        s <<"Initial capacty = "<<inititalCapacity<<"Must be > 0";
        throw illegalParameterValue(s.str());
    }
    arrayLength = inititalCapacity;
    queue = new T[arrayLength];
    theFront = 0;
    theBack = 0;
}

#endif // ARRAYQUEUE_H

/*
 * 异常类的定义
 * myExceptions.h
*/
#ifndef MYEXCEPTIONS_H
#define MYEXCEPTIONS_H

#include<string>
#include<iostream>
using namespace std;

class illegalParameterValue
{
public:
    illegalParameterValue(string theMessage =
            "Illegal parameter value")
    {
        message = theMessage;
    }

    void outputMessage()
    {
        cout <<message<<endl;
    }
private:
    string message;
};


class queueEmpty
{
public:
    queueEmpty(string theMesssage =
            "Invalid operation on empty queue")
    {
        message = theMesssage;
    }
    void outpuMessaget()
    {
        cout<< message<<endl;
    }
private:
    string message;
};


#endif // MYEXCEPTIONS_H

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树