二叉树 原

二叉树和树的根本区别

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

二叉树的特性

特性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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏编程理解

数据结构(三):二叉树遍历

前序遍历的方式,也就是对每一棵子树,按照根节点、左子树、右子树的顺序进行访问,也就是根-左-右的访问顺序。因为每一棵非空子树,又可拆分为根节点、左子树和右子树,...

1882
来自专栏决胜机器学习

PHP数据结构(六) ——树与二叉树之概念及存储结构

PHP数据结构(六)——树与二叉树之概念及存储结构 (原创内容,转载请注明来源,谢谢) 一、树的含义 1、树为非线性结构,是n(n>=0)个节点的有限集,非空树...

52410
来自专栏IT可乐

Java数据结构和算法(十)——二叉树

  接下来我们将会介绍另外一种数据结构——树。二叉树是树这种数据结构的一员,后面我们还会介绍红黑树,2-3-4树等数据结构。那么为什么要使用树?它有什么优点? ...

3456
来自专栏ACM算法日常

Binary Tree Traversals(二叉树) - HDU 1710

A binary tree is a finite set of vertices that is either empty or consists of a ...

821
来自专栏开发之途

Java集合框架源码解析之ArrayList

1874
来自专栏日常分享

Java 实现二叉树的构建以及3种遍历方法

大二下学期学习数据结构的时候用C介绍过二叉树,但是当时热衷于java就没有怎么鸟二叉树,但是对二叉树的构建及遍历一直耿耿于怀,今天又遇见这个问题了,所以花了一下...

2811
来自专栏架构之路

Java 集合系列03之 ArrayList详细介绍(源码解析)和使用示例

概要 上一章,我们学习了Collection的架构。这一章开始,我们对Collection的具体实现类进行讲解;首先,讲解List,而List中ArrayLis...

2924
来自专栏用户2442861的专栏

List、Set、Map、数组之间各种转换

刚学Java不久的时候,接到一个电面,然后问了一些java的知识,比如说Java的编码,Unicode等,但是最让我蛋疼的是怎么吗map转为set,那个时候对...

3302
来自专栏算法修养

HOJ 2148&POJ 2680(DP递推,加大数运算)

Computer Transformation Time Limit: 1000MS Memory Limit: 65536K Total S...

29712
来自专栏Java呓语

迭代器模式(控制访问集合中的元素)

现在我们需要思索,JDK是怎么做到这一切的?现在让我们先利用迭代器实现一个数组类型Array,这个类型需要支持添加、移除、遍历操作。

1052

扫码关注云+社区

领取腾讯云代金券