文章链接

https://gitee.com/fakerlove/Data-Structure

2022 考研数据结构复习

1. 数据结构绪论

1.1 什么是数据结构？

数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。

1.2 数据结构起源

​ 1968年，美国的高德纳教授开创了数据结构的课程体系。

​ 数据结构是一门研究非数值计算的程序设计问题中的操作对象，以及它们之间的关系和操作等相关问题的学科。

​ 程序设计的实质是对确定的问题选择一种好的结构，加上设计一种好的算法。数据结构在程序设计当中占据了重要的地位。

1.3 程序设计=数据结构+算法

1.4基本概念和术语

​ 说到数据结构是什么，我们得先来谈谈什么叫做数据。

​ 正所谓“巧妇难为无米之炊”，在强大的计算机，也要有“米”下锅才可以干活的，否则就是一堆破铜烂铁。这个“米”就是数据。

1.4.1数据

*数据：是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。*数据不仅仅包括整型、实型等数值类型，还包括字符及声音、图像、视频等非数值类型。

​ 例如平时我们所用的搜索中会有网页、MP3、图片、视频等分类。MP3就是声音数据，图片就是图像数据，而网页其实指的就是全部数据的搜索，包括最重要的数字和文字等文字数据。

​ 也就是说我们所说的数据就是符号，而且这些符号必须具备两个前提：

​ 1.可以输入到计算机中

​ 2.能被计算机程序处理

​ 对于整型、实型等数值类型，可以进行数值计算。

​ 对于字符型数据类型，就需要进行非数值的处理。而声音、图像、视频等其实是可以通过编码的手段变成字符数据来处理的。

1.4.2 数据元素

​ 数据元素：是组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理。也被称为记录。

​ 例如，在人类中，人就是数据元素。畜类中，牛、马、羊、鸡、猪、狗等动物就是禽类的数据元素。

1.4.3 数据项

​ 数据项：一个数据元素可以由若干个数据项组成。

​ 例如，人作为一个数据元素，可以有眼、耳、鼻、嘴、手、脚这些数据项，也可以有姓名、年龄、性别、出生地址、联系电话等数据项，具体有哪些数据项，要视你做的系统来决定。

​ *数据项是不可分割的最小单位。*记住数据项是数据的最小单位。但在真正讨论问题时，数据元素才是数据结构中建立数据模型的着眼点。例如讨论电影时，是讨论电影角色这样的“数据元素”，而不是针对这个角色的姓名或者年龄这样的“数据项”去研究分析。

1.4.4 数据对象

​ 数据对象：是性质相同的数据元素的集合，是数据的子集。

​ 性质相同就是指数据元素具有相同数量和类型的数据项，例如，人都有姓名、生日、性别等相同的数据项。

​ 在实际运用中，在不产生混淆的情况下，我们将数据对象简称为数据。

1.4.5 数据结构

​ 结构，简单的理解就是关系，比如分子结构，就是说组成分子的原子之间的排列方式。严格来说，结构是指各个组成部分相互搭配和排列的方式。在现实世界中，不同元素之间不是独立的，而是存在特定的关系，我们将这些关系称为结构。

数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。

在计算机中，数据元素并不是孤立、杂乱无序的，而是具有内在联系的数据集合。数据元素之间存在的一种或者多种特定关系，也就是数据的组织形式。编写一个“好”的程序，必须分析待处理对象的特性及各处理对象之间存在的关系。这也就是研究数据结构的意义所在。

1.5 逻辑结构与物理结构

​ 根据视点的不同，数据结构可以分为逻辑结构和物理结构两大类。

1.5.1 逻辑结构

​ *逻辑结构：是指数据对象中元素之间的相互关系。这是最需要关注的问题。*逻辑结构分为以下四种：

1. 集合结构

​ *集合结构：集合结构中的数据元素除了同属于一个集合外，他们之间没有其他关系。*各个数据元素是“平等”的，共同属性是“同属于一个集合”。类似于数学中的集合（如图所示）。

2. 线性结构

​ 线性结构：线性结构中的数据元素之间是一对一的关系（如图所示）。

3. 树形结构

​ 树形结构：树形结构中的数据元素之间存在一种一对多的层次关系（如图所示）。

4. 图形结构

​ 图形结构：图形结构的数据元素是多对多的关系（如图所示）。

​ 示意图表示数据的逻辑结构时，1.将每个元素看做一个结点，用圆圈表示。2.元素之间的逻辑关系用结点之间的连线表示，如果关系是有方向的，那么用带箭头的连线表示。

​ 由以上例子可以看出，逻辑结构是针对具体问题的，是为了解决某个问题在对问题理解的基础上，选择合适的数据结构表示数据元素之间的逻辑关系。

1.5.2 物理结构

​ 物理结构也叫做存储结构。

​ 物理结构：是指数据的逻辑结构在计算机中的存储形式。

​ 数据是数据元素的集合，根据物理结构的定义，实际上就是如何将数据元素存储到计算机的存储器中。存储器主要针对内存而言的，像硬盘、软盘、光盘等外部存储器的数据组织通常用文件结构来描述。

​ 数据的存储结构必须正确反映数据元素之间的逻辑关系，这才是最为关键的，如何存储数据元素之间的逻辑关系，是实现物理结构的难点和重点。

​ 数据元素的存储结构形式有两种：顺序存储和链式存储。

1. 顺序存储结构

​ 顺序存储结构：是把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的（如图所示）。

​ 说白了就是排队占位，大家按顺序排好，每个人占一小段空间，大家谁也别插谁的队。

2. 链式存储结构

​ 在实际中，总有人会插队，也会有人要去上厕所、有人放弃排队，所以这个队伍会有新成员添加，也会去掉老元素，在面对这样要时常变化的结构时，顺序存储是不科学的。

现在在银行、医院等地方，设置了排队系统，也就是每个人先领一个号，等着叫号，叫到时去办理业务或者看病。等待的过程你可以想在哪就在哪待着，你只需要关注的是你前一个号有没有被叫到，叫到了，下一个就轮到你了。

​ *链式存储结构：是把数据元素存放在任意的存储单元里，这组存储单元可以是连续的也可以不是连续的。*数据元素的存储关系并不能反映其逻辑关系，因此需要 用一个指针存放数据元素的地址，这样通过地址就可以找到相关联数据元素的位置（如图所示）。

​ 显然，链式存储就灵活多了，数据存在哪里不重要，只要有一个指针存放相应的地址就能找到它了。

​ 逻辑结构是面向问题的，而物理结构就是面向计算机的，其基本的目标就是将数据及其逻辑关系存储到计算机的内存中。

1.6 抽象数据类型

1.6.1 数据类型

​ 数据类型：是指一组性质相同的值的集合及定义在此集合上的一些操作的总称。

​ 数据类型是按照值的不同进行划分的。在高级语言中，每个变量、常量和表达式都各有各的取值范围。类型就用来说明变量或表达式的取值范围和能进行的操作。

​ 在C语言中，按照取值的不同，数据类型就可以分为两类：

​ 1. 原子类型：是不可以再分解的基本类型，包括整型、实型、字符型等。

​ 2. 结构类型：由若干个类型组合而成，是可以再分解的。例如，整型数组是由若干整型数据组成的。

​ 比如，在C语言中变量声明int a, b，这就意味着，在给变量a和b赋值时不能超出int的取值范围，变量a和b之间的运算只能是int类型所允许的运算。

​ 无论什么计算机、什么计算机语言，大都会面临着如整数运算、实数运算、字符运算等操作，我们可以考虑把它们都抽象出来。

​ *抽象是指抽取出事物具有的普遍性的本质。*它是抽出问题的特征而忽略非本质的细节，是对具体事物的一个概括。抽象是一种思考问题的方式，它隐藏了繁杂的细节，只保留实现目标所必需的信息。

1.6.2 抽象数据类型

​ 对已有的数据类型进行抽象，就有了抽象数据类型。

​ *抽象数据类型（Abstract Data Type , 简称ADT）：是指一个数据模型及定义在该模型上的一组操作。*抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何操作如何标示和实现无关。

​ **“抽象”的意义在于数据类型的数学抽象特性。

​ 抽象数据类型不仅仅指那些已经定义并实现的的数据类型，还可以是编程者在设计程序时自己定义的数据类型。例如，在绘图软件中，坐标x，y，z这三个变量始终一起出现，我们就可以定义一个叫point的数据抽象类型，它有x，y，z三个整型变量，这样就能方便的操作一个point数据变量就能知道这一点的坐标了。

​ 根据抽象将数据类型的定义，它还可以定义在该模型上的一组操作。

​ 一个抽象数据类型定义了：一个数据对象、数据对象中各元素之间的关系及对数据元素的操作。至于，一个抽象数据类型到底需要哪些操作，这就只能由设计者根据实际需要来定。例如，马里奥这个游戏，开始可能只有走和跳两种操作，后来发现应该增加一种打子弹的操作，再后来有玩家希望可以走快一点，就有了按住打子弹键后前进就会“跑”的操作。这都是根据实际情况来设计的。

​ 事实上，*抽象数据类型体现了程序设计中问题分解、抽象和信息隐藏的特性。*抽象数据类型把实际生活中的问题分解为多个规模小且容易处理的问题，然后建立一个计算机能处理的数据模型，并把每个功能模块的实现细节作为一个独立的单元，从而使具体实现过程隐藏起来。

​ 为方便对抽象数据类型进行规范的描述，我们可以按照下面描述的抽象数据类型的标准格式来编写程序：

1.7总结回顾

​ 前面介绍了数据结构的一些相关概念，如图所示：

​ 这些概念给出了数据结构的定义：*数据结构是相互之间存在一种或者多种特定关系的数据元素的集合。*同样是结构，从不同角度来讨论，会有不同的分类，如图所示：

​ 还介绍了抽象数据类型及它的描述方法。

2. 线性表

一、单链表

单链表是链表的基础，链表不同于顺序表，他使用链式结构来关联节点，其示意图如下： 单链表最重要的是需要搞清楚插入、删除操作

• 插入：插入的示意图如下所示，要在p的后面插入e，关键就是找到p，让p的next指向e，再让e的next指向p的原先的next（注意在p.next=e之前保存）。插入时，要判断是否插入到头结点，如果是的话，要记得给成员变量头结点重新赋值。
• 删除：单链表的删除示意图如下，删除节点p,首先找到p的前一个元素q，然后让q的next指向p的next即可。同样删除时需要注意头结点的问题，删除头结点后需要重新给成员变量头结点赋值。 单链表其他的操作都比较简单，我这里不再赘述。下面来看用C++和Java实现单链表的代码。
• Java实现

public class LinkList<T> {

    private Node head=null;//头结点
    private int length=0;//链表的长度


    /**
     * 获取链表长度
     * @return
     */
    public int getLength(){
        return length;
    }

    /**
     * 获取position位置的节点
     * @param position
     * @return
     */
    protected Node getNode(int position)
    {
        if (head==null||position<0||position>=length)
            throw new IndexOutOfBoundsException();
        else {
            Node curNode=head;
            int tmp=0;
            while (tmp<position){
                curNode=curNode.next;
                tmp++;
            }
            return curNode;
        }
    }

    /**
     * 获取position下标下的数据内容
     * @param position
     * @return
     */
    public T get(int position){
        return getNode(position).data;
    }

    /**
     * 在链表末尾插入节点
     * @param data
     */
    public void pushBack(T data){
        insert(this.length,data);
    }

    /**
     * 在position位置插入数据
     * @param position
     * @param data
     */
    public void insert(int position,T data){
        Node newNode=new Node(data);
        if (position==0){
            Node oldFirst=head;
            head=newNode;
            head.next=oldFirst;
        }else {
            Node node= getNode(position-1);
            Node nextNode=node.next;
            node.next=newNode;
            newNode.next=nextNode;
        }
        this.length++;
    }

    /**
     * 移除链表中的position下标的元素，并返回元素值
     * @param position
     * @return
     */
    public T remove(int position){
        T data=null;
        if (position==0){
            data=head.data;
            head=head.next;
        }else if(position<length){
            Node node= getNode(position-1);
            Node positionNode=node.next;
            node.next=node.next.next;
            data=positionNode.data;
        }
        length--;
        return data;
    }

    /**
     * 找到第一个出现data的索引位置
     * @param data
     * @return
     */
    public int indexOf(T data){
        Node curNode=head;
        int position=0;
        while (curNode!=null)
        {
            if (curNode.data.equals(data))
                return position;
            curNode=curNode.next;
            position++;
        }
        return -1;
    }

    @Override
    public String toString() {
        Node curNode=head;
        String outString="";
        while (curNode!=null)
        {
            outString+=curNode.toString()+",";
            curNode=curNode.next;
        }
        return outString;
    }

    public class Node{
        T data;//数据域
        Node next;//后继

        public Node(T data){
            this.data=data;
            next=null;
        }

        @Override
        public String toString() {
            return data.toString();
        }
    }
}
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136

示例用法为：

 LinkList<String> linkList= new LinkList<String>();
 linkList.pushBack("0");
 linkList.insert(0,"1");
 linkList.insert(2,"2");
 System.out.println(linkList);
 System.out.println(linkList.indexOf("2"));
123456

• C++实现

template<class T>
class LinkList
{
	struct Node//节点定义
	{
		T data;
		Node* next;
		Node(T data) {
			this->data = data;
			next = NULL;
		}
	};
private:
	Node* head;
	int length;
protected:
	/**
	* 获取某位置的节点
	*/
	Node* getNode(int position)
	{
		if (!head || position < 0 || position >= length)
			throw std::out_of_range("position is out of range");
		else
		{
			Node* curNode = head;
			int tmp = 0;
			while (tmp<position)
			{
				curNode = curNode->next;
				tmp++;
			}
			return curNode;
		}
	}
public:
	LinkList()
	{
		this->head = NULL;
		this->length = 0;
	}
	/**
	* 析构函数，此处需要释放链表
	*/
	~LinkList()
	{
		Node* curNode = head;
		while (curNode)
		{
			Node* tmp = curNode->next;
			delete curNode;
			curNode = tmp;
		}
	}

	/**
	* 获取链表的长度
	*/
	int getLength()
	{
		return length;
	}

	/**
	* 获取position位置下的数据
	*/
	T get(int position)
	{
		return getNode(position)->data;
	}

	/**
	* 在链表末尾追加元素
	*/
	void pushBack(T data)
	{
		insert(this.length,data);
	}

	/**
	* 在position位置增加data数据
	*/
	void insert(int position, T data)
	{
		Node* newNode = new Node(data);
		if (position == 0) {
			Node* oldFirst = head;
			head = newNode;
			head->next = oldFirst;
		}
		else {
			Node* node = getNode(position - 1);
			Node* nextNode = node->next;
			node->next = newNode;
			newNode->next = nextNode;
		}
		this->length++;
	}

	/*
	*移除链表中的position下标的元素，并返回元素值
	*/
	T remove(int position)
	{
		T data;
		if (position == 0) {
			Node* removeNode;
			removeNode = head;
			data = head->data;
			head = head->next;
			delete removeNode;
		}
		else if (position<length)
		{
			Node* node = getNode(position - 1);
			Node* positionNode = node->next;
			node->next = node->next->next;
			data = positionNode->data;
			delete positionNode;
		}
		length--;
		return data;
	}

	/**
	*找到第一个出现data的索引位置
	*/
	int indexOf(T data) {
		Node* curNode = head;
		int position = 0;
		while (curNode != NULL)
		{
			if (curNode->data == data)
				return position;
			curNode = curNode->next;
			position++;
		}
		return -1;
	}
};
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140

使用示例为：

    LinkList<std::string> link_list;
	link_list.pushBack("0");
	link_list.pushBack("1");
	link_list.pushBack("2");
	link_list.insert(0,"3");
	link_list.remove(0);
	link_list.remove(1);
	std::cout <<"元素0所在的下标为"<< link_list.indexOf("0")<<std::endl;
	for (int i=0;i<link_list.getLength();i++)
	{
		std::cout << link_list.get(i)<<",";
	}
123456789101112

二、循环链表

循环链表就是把最后一个节点的next指向头结点，解决的是如何从某个节点出发，遍历整个链表的问题，上面的单链表如果要遍历，只能从头结点开始，遍历到尾节点，但循环链表则可以从任意一个节点开始，遍历整个链表。存储结构如下图所示： 只有一个节点的循环链如下所示： 因为循环链表和单链表间的变化很小，我这里不单独写循环链表的代码了，在双向链表中，我实现了双向循环链表，可以参考。使用循环链表需要注意的一个问题： 如何判断循环结束：单链表是判断节点p的next是否为空，循环链表从p开始循环遍历，判断条件是当前节点是否回到了p。所以不同于单向链表的实现，在遍历链表时，应该用do while语句，而不用while语句，否则p元素可能会遍历不到（具体见我双向循环链表java代码中的toString方法的实现）。

三、双向链表

双向链表是在单链表的基础上，给节点增设一个指针域，指向节点的前驱节点。这样的话，遍历链表的时候，既可以从前往后遍历，又可以从后往前遍历。双向链表也可以是循环链表，双向循环链表的示意图如下所示： 当只有一个节点时，其示意图为： 因为，单链表和双向链表的操作很多都是重复的，为了节省时间，我这里就只用Java实现双向循环链表，实现其插入、删除、遍历。具体代码如下：

• 双向循环链表Java实现

public class DoublyLinkedList<T> {

    protected class Node{
        T data;//数据域
        Node pre;//前驱节点
        Node next;//后继节点

        Node(T data){
            this.data=data;
            pre=next=null;
        }

        @Override
        public String toString() {
            return data.toString();
        }
    }

    protected Node head=null;//头结点
    protected int length=0;//链表长度

    /**
     * 获取position位置的节点
     * @param position
     * @return
     */
    protected Node getNode(int position)
    {
        if (head==null||position<0||position>=length)
            throw new IndexOutOfBoundsException();
        else {
            /*此处充分利用双向链表的优点，首先判断position和half=length/2的大小关系
            如果position大于half，则从后往前遍历
            如果position小于等于half，则从前往后遍历
            */
            int half=this.length/2;
            Node curNode;
            int tmp;
            if (position<=half){//从前往后遍历
                curNode=head;
                tmp=0;
                while (tmp<position){
                    curNode=curNode.next;
                    tmp++;
                }
                return curNode;
            }else {//从后往前遍历
                curNode=head.pre;
                tmp=length-1;
                while (tmp>position){
                    curNode=curNode.pre;
                    tmp--;
                }
                return curNode;
            }
        }
    }

    /**
     * 在position位置插入数据
     * @param position
     * @param data
     */
    public void insert(int position,T data){
        Node newNode=new Node(data);
        if (position==0){
            Node oldFirst=head;
            head=newNode;
            //头结点的前驱后继
            head.next=oldFirst;
            if (oldFirst!=null) {
                head.pre=oldFirst.pre;
                //让末尾节点的next指向头结点
                oldFirst.pre.next=head;
                //以前头结点的前驱
                oldFirst.pre=head;
            }else {
                newNode.pre=newNode;
                newNode.next=newNode;
            }
        }else {
            Node node= getNode(position-1);
            newNode.pre=node;
            if (node.next==null){//插入位置为空，说明是插入到链表的末尾
                newNode.next=head;
                head.pre=newNode;
            }else {//说明插入到两个结点的中间
                newNode.next=node.next;
                node.next.pre=newNode;
            }
            node.next=newNode;
        }
        this.length++;
    }

    /**
     * 移除position位置处的元素
     * @param position
     * @return
     */
    public T remove(int position){
        T data=null;
        if (position==0){//移除的是头结点
            data=head.data;
            if (this.length==1)//如果只有一个元素，直接置空
                this.head=null;
            else {
                Node oldHead=head;
                head=head.next;
                //头结点的next
                head.pre=oldHead.pre;
                oldHead.pre.next=head;
            }
        }else {//移除是非头结点
            Node node= getNode(position-1);
            if (node.next==null){//移除的节点是最后一个节点
                node.next=head;
                head.pre=node;
            }else {//移除的节点是中间节点
                Node removeNode=node.next;
                node.next=removeNode.next;
                removeNode.next.pre=node;
            }
        }
        this.length--;
        return data;
    }

    public T get(int position){
        return getNode(position).data;
    }

    @Override
    public String toString() {
        Node curNode=head;
        String outString="";
        if (curNode!=null){
            do {
                outString+=curNode.toString()+",";
                curNode=curNode.next;
            }while (curNode!=head);
        }
        return outString;
    }
}
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145

使用示例为：

 DoublyLinkedList<String> list=new DoublyLinkedList<String>();
 list.insert(0,"0");
 list.insert(0,"1");
 list.insert(0,"2");
 list.insert(1,"3");
 list.insert(4,"4");
 list.remove(4);
 System.out.println(list);
12345678

根据上面的代码，需要注意的问题有：

• 遍历：因为是双向循环链表，所以在遍历时，应充分利用双向循环链表的优势，我上面的getNode函数，根据position位置和链表的长度进行判断，设链表长度的一半为half=length/2，访问第position位置时，当position<=half时，从前往后遍历，否则从前往后遍历，这样遍历能提高一倍的性能。 此外，遍历时，应该判断当前节点是否是开始的节点，如果是，则遍历完成。所以，应该使用do while语句而不是while语句，否则会导致循环直接跳出。此外，上面的toString函数是通过从前往后遍历的，双向链表也可以从后往前遍历，遍历代码为：

do {
          curNode=curNode.pre;
          outString+=curNode.toString()+",";
   }while (curNode!=head);
1234

• 插入：双向链表插入时，应该判断插入的位置是头部还是尾部还是中间，根据这三种情况，分别做处理
• 删除：同上，也要根据删除元素在链表头部、尾部还是中间分别做相应的处理。还要注意，如果链表只有一个元素，且移除的是第一个元素，那直接将头结点置空。

3. 栈和队列

3.1 栈

3.1.1 栈的定义

栈是限定仅在表尾进行插入和删除操作的线性表。把允许插入的一端称为栈顶，另一端称为栈底，不含任何元素的栈称为空栈。栈是后进先出的线性表。

3.1.2 栈的实现

栈的实现有数组和链表两种方式。其中，数组方式很简单，就是定义一个数组，然后用一个int类型的变量用来标识栈顶，每次入栈的时候将新元素插入到数组尾处，这里就不实现了。因为在链表一节中已经实现了单链表，以及在其尾部插入（相当于入栈操作）的算法，我们这里直接就继承我们实现的单链表，增加栈的弹栈、是否为空的判断两个方法。实现代码如下：

• Java

public class LinkStack<T> extends LinkList<T> {
    public boolean isEmpty(){
        return length==0;
    }

    /**
     * 弹栈
     * @return
     */
    public T pop(){
        if (this.head!=null){
            return remove(this.length-1);
        }
        return null;
    }
}

1234567891011121314151617

上述代码中，LinkList的实现见链表一节。使用示例如下：

		LinkStack<String> stack=new LinkStack<>();
        stack.pushBack("0");
        stack.pushBack("1");
        stack.pushBack("2");
        System.out.println(stack);
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
12345678

此处的链表是使用的尾插法，但是这样其实在弹栈以及入栈的时候性能并不好，因为每次入栈和弹栈都需要遍历链表，所以应该使用头插法，此处就需要重写单链表中的pushBack方法。重写后的链式存储栈的代码如下：

public class LinkStack<T> extends LinkList<T> {
    public boolean isEmpty(){
        return length==0;
    }

    /**
     * 弹栈
     * @return
     */
    public T pop(){
        if (this.head!=null){
            return remove(0);
        }
        return null;
    }
     /**
     * 获取栈尾元素，但并不弹出
     * @return
     */
    public T peek(){
        if (this.head!=null){
            return get(0);
        }
        return null;
    }
    
    /**
     * 重写pushback方法，使用头插法，每次将节点插入到链表的头部
     * @param data
     */
    @Override
    public void pushBack(T data) {
        insert(0,data);
    }

    /**
     * 重写toString方法，从后往前输出
     * @return
     */
    @Override
    public String toString() {
        String result="";
        Node node=head;
        while (node!=null){
            result=node.getData()+","+result;
            node=node.getNext();
        }
        return result;
    }
}
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950

在重写pushBack和pop方法的同时，还要重写toString，让输出是从后往前输出。使用头插法以后，这个链式栈的性能就好多了。同理，我们用C++来实现头插法的链式栈。其中父类LinkList的实现仍见链表一节。

• C++

#include "../LinkList/LinkedList.h"
template<class T>
class LinkStack:LinkList<T>
{
public:
	/*
	 * 重写插入方法，使用头插法
	 */
	void pushBack(T data)
	{
		insert(0, data);
	}
	T peek(){
        if (this->head!=null){
            return get(0);
        }
        return NULL;
    }
	
	T pop()
	{
		if(this->head)
		{
			return remove(0);
		}
		return NULL;
	}
};

1234567891011121314151617181920212223242526272829

使用示例为：

    LinkStack<string> link_stack;
	link_stack.pushBack("0");
	link_stack.pushBack("1");
	link_stack.pushBack("2");
	cout << link_stack.pop()<<",";
	cout << link_stack.pop()<<",";
	cout << link_stack.pop()<<",";
1234567

3.1.3 栈的应用

栈最最常见的应该是平时软件中用到的撤销或者回退了吧。除此之外，栈还有很多的应用，下面介绍几个应用。

(1)递归

函数自己调用自己，就是递归。递归的调用需要栈的辅助，在每次调用自己之前，都要将当前的变量压栈存储起来，以便回退时恢复。 在这里，我想说一个以前没有搞清楚的应该使用递归解决的例子。

• 问题描述： 求0—n-1这n个数的全排列
• 样例： 输入3，输出012,021,102,120,210,201。
• 分析： 求1—n-1的全排列，过程应是这样的：先将第一个数固定，然后求剩下的n-1个数的全排列。求n-1个数的全排列的时候，还是一样，将第一个数固定，求n-2个数的全排列。直到剩下一个数，那他的全排列就是自己。那这个固定的数字应该有多种取值，比如求0,1,2三个数的全排列，固定的第一个数，应有0,1,2三种取值对吧，当固定第一个数，比如固定了0，那剩下1,2两个数，再固定一个数，这个数有1和2两种取值，有没有发现什么？我们发现，这个固定的数的取值，不就是将固定的位置的数和剩下的数字不断交换的过程么。理解了这个，来写代码看看（此处只写java代码，因为我这里每个例子都是用内部类定义的，所以class前面都有public和static关键字）。
• Java实现

public static class FullArrange{//全排列

        /**
         * 将list中，下标为i和下标为j的两个元素交换
         * @param list
         * @param i
         * @param j
         */
        public void swap(int[] list,int i,int j){
            int tmp=list[i];
            list[i]=list[j];
            list[j]=tmp;
        }

        public void perm(int[] list,int start,int end){
            if (start==end-1){
                String tmp="";
                for (int i=0;i<end;i++)
                   tmp+=list[i]+",";
                System.out.println(tmp);
            }else {
                for (int i=start;i<end;i++){
                    swap(list,start,i);
                    perm(list,start+1,end);
                    swap(list,start,i);
                }
            }
        }

        /**
         * 测试函数，输出0——n的全排列
         * @param n
         */
        public void test(int n){
            int[] list=new int[n];
            for (int i=0;i<n;i++)
                list[i]=i;
            perm(list,0,n);
        }
    }
12345678910111213141516171819202122232425262728293031323334353637383940

上述代码，其他的都很好理解，关键在于下面这三句代码：

swap(list,start,i);
perm(list,start+1,end);
swap(list,start,i);
123

其中，第一句很好理解，就是那个固定的数的所有取值，第二句也好理解，就是求当一个数字固定后，剩下的数的全排列（这里就是递归），那第三句是干啥的呢？其实也比较好理解，第三句的作用是将第一句元素交换后的数组还原，你在第一句代码中将数组中的元素交换过了，求过递归以后，应该把数组还原，不然数组就和原来的不一样了。 使用示例：

 FullArrange arrange=new FullArrange();
 arrange.test(3);
12

输出结果

0,1,2,
0,2,1,
1,0,2,
1,2,0,
2,1,0,
2,0,1,
123456

(2)四则运算表达式求解

四则运算表达式应该是栈的一个最常见的应用了。对于一个四则运算表达式“9+(3-1)×3+10÷2”，要计算其值，首先应该把这个中缀表达式转换为后缀表达式，然后再对后缀表达式进行求解。

①中缀表达式转后缀表达式

有关什么是中缀表达式，什么是后缀表达式我这里就不赘述了，大家自行百度。中缀表达式转后缀表达式的规则为：

• 1)读取到数字，直接输出
• 2)当读取到左括号"("时，直接压栈，当读取到运算符时，分两种情况讨论 a.当运算符栈为空或者栈顶操作符的优先级小于当前运算符优先级时(如+和-的优先级低于 * 和 /)，直接入栈 b.当运算符不为空时且栈顶操作符的优先级大于或等于当前运算符优先级时，循环执行出栈操作并输出，直到遇到优先级小于当前运算符的元素为止。循环执行完后再将当前运算符压栈。另外需要注意的是，只有遇到右括号时，左括号才出栈
• 3)当遇到右括号")"时，循环执行出栈操作并加入到list中，直到遇到左括号为止。并将左括号弹出，但不加入list中
• 4)表达式的值读取完后，将操作符栈中的所有元素弹出并输出

如“9+(3-1)×3+10÷2”，先输出9；加号进栈；左括号进栈；输出3；减号进栈；输出1；遇到右括号，一直输出栈顶元素直到遇到左括号，所以减号和左括号输出；×进栈；输出3；遇到加号，×和-出栈，+入栈；输出10；÷入栈；输出2；栈中元素全部出栈，得到最后结果：9 3 1 - 3 × + 10 2 ÷ +。

②后缀表达式的计算

后缀表达式也会用到栈，其具体规则为：从左到右遍历后缀表达式的每个数字和符号，遇到数字就进栈，遇到符号，就将处于栈顶的两个数字出栈，进行运算，并将运算结果进栈，一直到最终获得结果。 下面仍然用Java来实现中缀表达式转后缀表达式以及后缀表达式的求解（因为我这里每个例子都是用内部类定义的，所以class前面都有public和static关键字），C++的过程和此类似，我这里就不写了。

• Java

public static class CalculateMathExpression{//四则运算表达式求解

        /**
         * 将输入的中缀表达式转换成后缀表达式
         * @param inString 中缀表达式的字符串
         * @return 分离得到的后缀表达式
         */
        public static List<String> inTransPost(String inString) throws Exception {
            ArrayList<String> result=new ArrayList<>();
            LinkStack<String> stack=new LinkStack<>();
            for (int i=0;i<inString.length();i++){
                char item=inString.charAt(i);
                if ((item>='0'&&item<='9')||item=='.'){//如果是数字加入到输出队列
                    //此处进行两位数的处理
                    String tmp=String.valueOf(item);
                    int j=i+1;
                    while (j<inString.length()){
                        char item2=inString.charAt(j);
                        if ((item2>='0'&&item2<='9')||item2=='.')
                        {
                            tmp+=String.valueOf(item2);
                            j++;
                        }
                        else
                            break;
                    }
                    result.add(tmp);
                    if (j!=i+1)//数字是一位数
                        i=j-1;
                    continue;
                }
                else if (item=='(')
                {
                    stack.pushBack(String.valueOf('('));
                    continue;
                }
                else if (item=='+'||item=='-'){
                    while (!stack.isEmpty()&&!stack.peek().equals("("))
                        result.add(stack.pop());
                    stack.pushBack(String.valueOf(item));
                    continue;
                }
                else if (item=='*'||item=='/'){
                    while (!stack.isEmpty()&&(stack.peek().equals("*")||stack.peek().equals("/")))
                        result.add(stack.pop());
                    stack.pushBack(String.valueOf(item));
                    continue;
                }
                else if (item==')'){
                    while (!stack.isEmpty()&&!stack.peek().equals("("))
                        result.add(stack.pop());
                    stack.pop();
                    continue;
                }else
                    throw new Exception("遇到未知操作符");
            }
            while (!stack.isEmpty())
                result.add(stack.pop());
            return result;
        }

        /**
         * 计算中缀表达式的值
         * @param inString
         * @return
         */
        public static float calcExpressionValue(String inString){
            List<String> postStr=null;
            try {
                postStr=inTransPost(inString);
            }catch (Exception e){
                System.out.println("输入数据中有未知字符！");
                return Float.NaN;
            }
            if (postStr!=null){
                String outStr="输入的中缀表达式转换成后缀表达式为：";
                LinkStack<Float> stack=new LinkStack<>();
                for (String str:postStr)
                {
                    outStr+=str+" ";
                    try {
                        if (str.equals("+")||str.equals("-")||str.equals("*")||str.equals("/")){//如果遇到操作符，则弹出两个操作数，将计算结果压栈
                            Float val2=stack.pop();
                            Float val1=stack.pop();
                            float result=operate(val1,val2,str);
                            stack.pushBack(result);

                        }else {//如果遇到数字直接压栈
                            Float val=Float.valueOf(str);
                            stack.pushBack(val);
                        }
                    }
                    catch (NumberFormatException e){//捕获字符串转数字时出现异常
                        System.out.println("字符串转换成数字出错！");
                        return Float.NaN;
                    }
                }
                System.out.println(outStr);
                return stack.pop();
            }
            return Float.NaN;
        }

        /**
         * 根据操作符计算两个数的值
         * @param val1 第一个操作数
         * @param val2 第二个操作数
         * @param operator 操作符，+ - * /中的一个
         * @return
         */
        private static float operate(Float val1,Float val2,String operator){
            if (operator.equals("+"))
                return val1+val2;
            else if (operator.equals("-"))
                return val1-val2;
            else if (operator.equals("*"))
                return val1*val2;
            else
                return (float) (val1*1.0/val2);
        }
    }
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121

上面的例子支持多位数的加减运算，且支持小数。其中，用到的LinkStack类就是本文章上面实现的链式栈。使用示例：

System.out.println(CalculateMathExpression.calcExpressionValue("10.2+((2+3)*4)-5"));
1

输出结果为：

输入的中缀表达式转换成后缀表达式为：10.2 2 3 + 4 * + 5 - 
25.2
12

3.2 队列

3.2.1 队列的定义

队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。是一种先进先出的线性表，允许插入的一端称为队尾，允许删除的一端称为队头。

3.2.2 队列的实现

同理，队列的实现方式也有顺序表和链表两种方式。

• 顺序表：用顺序表实现队列，就是用一个数组和一个指针来实现。每次入队的时插入到数组尾，出队的时将数组第一个元素移除，然后后面的元素整体后移。但是这样效率很低，为了提高效率，可以设置两个指针，一个指针front指向队头，一个指针rear指向队尾，这样队头就不一定在数组下标为0的位置了。使用此种方式时，应该解决假溢出的问题。解决假溢出的方式是使用循环队列，即当队尾满了时，插入到队头。 循环队列当队空和队满时，都是front和rear相等，为了解决此问题，当队满时，我们留一个元素。如下所示： 此时， 队满的条件为： (rear+1)%QueueSize==front 计算队长的公式为： (rear-front+QueueSize)%QueueSize
• 链式结构 队列的链式存储结构，就是在链表的基础上，限制数据的插入和弹出：将链表头部当成队首，尾部当成队尾。因为经常需要在队尾进行入队操作，为了减少链表的遍历次数，提高性能，此处我们的队列的Java代码实现基于双向循环链表实现，而C++结构则基于单链表实现（C++的双向循环链表太懒了没实现，只能用单链表了hhh）。有关双向循环链表的实现，见上一篇博客。具体实现如下：
• Java实现

public class LinkQueue<T> extends DoublyLinkedList<T> {
    /**
     * 入队操作
     * @param data
     */
    public void enQueue(T data){
        insert(this.length,data);
    }

    /**
     * 出队操作
     * @return
     */
    public T deQueue(){
        if (!isEmpty())
            return remove(0);
        return null;
    }

    /**
     * 判断队列是否为空
     * @return 空返回true，非空返回false
     */
    public boolean isEmpty(){
        return this.length==0;
    }
}
123456789101112131415161718192021222324252627

其中，DoublyLinkedList双向循环链表的实现见上一篇博客。使用示例如下：

		LinkQueue<String> queue=new LinkQueue<>();
        queue.enQueue("0");
        queue.enQueue("1");
        queue.enQueue("2");
        System.out.println(queue);
        System.out.println(queue.deQueue());
        System.out.println(queue.deQueue());
        System.out.println(queue.deQueue());
12345678

输出结果为：

0,1,2,
0
1
2
1234

• C++实现

template<class T>
class LinkQueue:LinkList<T>
{
public:
	/**
	 * 入队操作
	 */
	void enQueue(T data)
	{
		insert(length, data);
	}

	/**
	 * 出队操作
	 */
	T deQueue()
	{
		if (!isEmpty())
		{
			return this->remove(0);
		}
		return NULL;
	}

	bool isEmpty()
	{
		return this->length == 0;
	}
};
1234567891011121314151617181920212223242526272829

同理，LinkList的定义见上一篇博客。此处因为使用的是单链表，频繁出队入队的话，效率应该不是很高。使用示例如下：

	LinkQueue<string> queue;
	queue.enQueue("0");
	queue.enQueue("1");
	queue.enQueue("2");
	cout << queue.deQueue() << endl;
	cout << queue.deQueue() << endl;
	cout << queue.deQueue() << endl;
1234567

输出结果为：

0
1
2
123

3.2.2 队列的应用

队列也有很多应用，比如各种排队系统，特别是在网络请求的时候，当有多个请求任务时，不能一下子全部请求，需要排队请求。还有就是树的层次遍历中会用到队列，这个等写到树的时候再详细介绍。

3. 3 应用

3.3.1 表达式

表达式一般分为前缀表达式，中缀表达式和后缀表达式。

其中我们最为熟悉的是中缀表达式，也就是书本上最常用的表示形式。中缀表达式是将运算符放在两个操作数的中间。

语言表示1--中缀转后缀

1.从左到右进行遍历2.运算数,直接输出. 3.左括号,直接压入堆栈,(括号是最高优先级,无需比较)(入栈后优先级降到最低,确保其他符号正常入栈) 4.右括号,(意味着括号已结束)不断弹出栈顶运算符并输出直到遇到左括号(弹出但不输出) 5.运算符,将该运算符与栈顶运算符进行比较, 如果优先级高于栈顶运算符则压入堆栈(该部分运算还不能进行), 如果优先级低于等于栈顶运算符则将栈顶运算符弹出并输出,然后比较新的栈顶运算符. (低于弹出意味着前面部分可以运算,先输出的一定是高优先级运算符,等于弹出是因为同等优先级,从左到右运算) 直到优先级大于栈顶运算符或者栈空,再将该运算符入栈. 6.如果对象处理完毕,则按顺序弹出并输出栈中所有运算符.

语言表述2--中缀转后缀

如何将中缀转后缀思路： 假如表达式是一个字符串

创建一个符号栈和一个字符串队列

遍历各个字符信息

判断该字符是 运算符、括号、数值

• 运算符

  判断当前字符优先级是否小于等于栈顶字符优先级，此时栈顶元素中的左括号(，优先级最小

  • 小于等于 将符号栈栈顶内容弹出且存入到字符串队列中,将当前字符存入到符号栈中
  • 大于将当前字符存入到符号栈中

• 括号

  • 左括号存入到符号栈中
  • 右括号 依次将符号栈中的运算符弹出进入到字符串队列中直到在符号栈中弹出出现左括号停止弹栈 数值 直接进入到字符串队列中

• 数值

  直接输出

遍历结束后 判断符号栈中是否有元素

优先级

运算符	（左括号	+加，-减	*乘，/除，%取模	^幂
优先级	0	1	2	3

代码--中缀转后缀

#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
using namespace std;
#define MAX 1000
char *change(char data[]);
bool compare(char a, char b);
int priority(char a);
// (40  括号在算术上优先级最高，但是在 栈的优先级是最低的，为了其他符号正常入栈 优先级最低
//  /* 优先级最高 , +- 优先级最低

// true 的情况 只有a 是*/ b是+-的情况
int priority(char a)
{
    if (a == '(')
    {
        return  0;
    }
    else if (a == '+' || a == '-')
    {
        return  1;
    }
    else
    {
        return  2;
    }
}
// 比较优先级 ,a 的优先级比b 高，就返回true
bool compare(char a, char b)
{
    return  priority(a) > priority(b);
}
// 中缀表达式--> 后缀表达式(逆波兰表达式)
// 返回字符串数组
char *change(char data[])
{

    char *hou = (char *)malloc(MAX * sizeof(char));
    stack<char> s;
    int index = 0; // 后缀表达式的长度
    int length = strlen(data);
    // 1. 判断类型
    for (int i = 0; i < length; i++)
    {
        // 如果是运算数，直接输出，
        if (data[i] >= '0' && data[i] <= '9')
        {
            hou[index] = data[i];
            index++;
        }
        else if (data[i] == ')')
        {
            // 不断的弹出栈元素并输出直到遇到左括号结束
            while (!s.empty() && s.top() != '(')
            {
                hou[index] = s.top();
                index++;
                s.pop();
            }
            s.pop(); //退出左括号
        }else if(data[i]=='('){
             s.push(data[i]);
        }
        else
        {
            // 表示 运算符优先级小于等于 栈顶元素,就退出栈顶元素，并输出
            // 包含情况data[i]='(',compare 返回false
            
            while (!s.empty() && !compare(data[i], s.top()))
            {
                printf("%c %c %d\n",data[i],s.top(),compare(data[i], s.top()));
                hou[index] = s.top();
                index++;
                s.pop();
            }
            s.push(data[i]);
        }
        printf("此时输出内容 %-20s \t参加运算的符号 %c  \t\t栈的元素个数%d \n", hou, data[i], s.size());
    }

    // 输出栈内所有元素
    while (!s.empty())
    {
        hou[index] = s.top();
        index++;
        s.pop();
    }
    return  hou;
}

// 后缀表达式的计算
int main(int argc, char const *argv[])
{
    // 样例 2*(9+6/3-5)+4
    // 结果 2963/+5-*4+
    char s[MAX] = "2*2*2*2+2";
    char *result;
    result = change(s);
    printf("%s\n", result);
    return  0;
}

4. 串

4.1 模式匹配

1. 暴力算法 bf

从左到右一个个匹配，如果这个过程中有某个字符不匹配，就跳回去，将模式串向右移动一位。这有什么难的？

匹配不成功，i回溯到开始，j 回溯到子串的开头

匹配不成功，i 往后走

时间复杂度O(m*n)

2. KMP 算法

利用已经部分匹配这个有效信息，保持i指针不回溯，通过修改j指针，让模式串尽量地移动到有效的位置

时间复杂度O(m+n)

前缀，后缀，部分匹配值

• 前缀：除去最后一个字符外，字符串的所有头部子串
• 后缀：除去第一个字符外，字符串的所有头部子串
• 部分匹配值：字符串的前缀和后缀最长相等的前后缀长度

字符串	部分匹配值	前缀	后缀
a	0 (空集 空集)	空集	空集
ab	0 {a} {b}	a	b
aba	1 {a,ab} {ba,a}	ab a	ba a
abab	2 {a,ab,aba} {b,ab,bab}	a ab aba	b ab bab
ababa	3 {a,ab,aba,abab} {a,ba,aba,baba}	a ab aba abab	a ba aba baba
ababc	0 {a,ab,aba,abab} {c,bc,abc,babc}	a,ab,aba,abab	c,bc,abc,babc
sssss	4	s,ss,sss,ssss	s,ss,sss,ssss
abca	1 {a,ab,abc} {a,ca,bca}	a,ab,abc	a,ca,bca

next 数组 (子串回溯的位置)

• 匹配的过程 KMP 算法的过程

  移动主串情况

  1. 如果是 j== -1 ,表示就是第一个字符匹配失败，第一个元素匹配失败，不需要移动子串，只需要移动主串

  2. 或者 字符串匹配成功

  

不移动主串的情况

1. 匹配失败，子串回溯
2. 右移的数字 = 已经匹配的字符数-对应的部分匹配值 j=next[j]+1

代码

int kmp(char str[],char temp[])//这个是查找
{
 
	int i = 0;//这个是主字符串的位置
	int j = 0;//这个是子字符串的位置
	int length1 = strlen(str);
	int length2 = strlen(temp);
	while (i<length1&&j<length2) 
	{
		if (j==-1||str[i] == temp[j]) {
			i++;
			j++;
		}
		else {
			j = next[j];
		}
	}
	if (j==length2) {
		return  i - j;
	}
	return  -1;
	
}

• 代码 next 数组怎么求

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int next[1001];//这个是next数组
//函数声明
void getNext(char str[]);
int KMP(char str[],char temp[]);
int main()
{
	int i = 0;
	char str[1001];//这个是主字符串
	char temp[1001];//这个是用来匹配的字符串
	int length = 0;//这个是主字符串的长度。
	int result = -1;
 
	printf("请输入第一个字符串\n");
	gets(str);//在vs中用scanf_s();
	printf("请输入第二个字符串\n");
	gets(temp);//在vs中用scanf_s();
 
	getNext(str);//建立next数组
 
	result = KMP(str,temp);//这个是获取结果
 
        printf("\n");
 
	if (result <= 0) {
		printf("没有找到匹配的字符串");
	}
	else {
		printf("结果在主字符串的位置为 %d",result+1);
	}
	// system("pause");
	return  0;
}
void getNext(char str[])//next数组的建立，这个是关键
{
    // 初始化
	int i=0,j = -1;
	int length1 = strlen(str);
    // 第一个不匹配的话，是主串开始往后加一
	next[0] = -1;
	
	while (i < length1) {

        // -1 表示是第一个字符串，第一个字符串不需要赋值，因为肯定是-1 ,
        // 还有一种情况就是
		if ( j== -1 || str[j] == str[i]) {
			i++;
			j++;
            
			next[i] = j;
 
		}
		else {
			j = next[j];
		}
	}
}
int kmp(char str[],char temp[])//这个是查找
{
 
	int i = 0;//这个是主字符串的位置
	int j = 0;//这个是子字符串的位置
	int length1 = strlen(str);
	int length2 = strlen(temp);
	while (i<length1&&j<length2) 
	{
		if (j==-1||str[i] == temp[j]) {
			i++;
			j++;
		}
		else {
			j = next[j];
		}
	}
	if (j==length2) {
		return  i - j;
	}
	return  -1;
}

5. 树

5.1 概念

5.2 二叉树

5.2.1 树的定义和特征

深度

深度定义是从上往下的，高度定义是从下往上的。

1. 高度就是深度
2. 看层数： 如果根结点第0，层数=深度=高度-1 如果根结点第1，层数=深度=高度

5.2.2 树的遍历

1) 给出中后，输出前序

样例

//中序 GLDHBEIACJFK //后序 LGHDIEBJKFCA

#include <iostream>
#include <string.h>
#include <stdlib.h>
#define MAX 20 /*预定义字符数组的最大长度*/
using namespace std;
typedef struct tnode /*该结构体类型为树结点的类型*/
{
    char data;
    struct tnode* lchild;
    struct tnode* rchild;
} *bt;

void in_post_to_bt(char* in, char* post, int len, bt& T) /*由长度为len的中序序列in和后序序列post唯一确定一棵二叉树T*/
{
    int k;
    if (len <= 0)
    {
        T = NULL;
        return;
    }
    for (char* temp = in; temp < in + len; temp++) /*在中序序列in中找到根节点所在的位置*/
        if (*(post + len - 1) == *temp)
        {
            k = temp - in; /*k为根结点在中序序列中的下标*/
            T = (bt)malloc(sizeof(struct tnode));
            T->data = *temp;
            break;
        }
    in_post_to_bt(in, post, k, T->lchild); /*建立左子树*/
    in_post_to_bt(in + k + 1, post + k, len - k - 1, T->rchild); /*建立右子树*/
}

void in_visit(bt T) /*中序遍历树T*/
{
    if (T)
    {
        in_visit(T->lchild);
        cout << T->data;
        in_visit(T->rchild);
    }
}

void post_visit(bt T) /*后序遍历树*/
{
    if (T)
    {
        post_visit(T->lchild);
        post_visit(T->rchild);
        cout << T->data;
    }
}

int main()
{
    //中序 GLDHBEIACJFK
    //后序 LGHDIEBJKFCA
    char in[MAX + 1], post[MAX + 1];
    cout << "输入中序序列：";
    cin >> in;
    cout << "输入后序序列：";
    cin >> post;
    bt T=(bt)malloc(sizeof(struct tnode));
    int len_in = strlen(in), len_post = strlen(post);
    if (len_in <= MAX && len_post <= MAX)
        in_post_to_bt(in, post, len_in, T);
    cout << endl
        << "输出中序序列：";
    in_visit(T);
    cout << endl
        << "输出后序序列：";
    post_visit(T);
    cout << endl;
    return 0;
}

5.3 树，森林

5.3.1 树的存储结构

5.3.2 森林与二叉树的转换

1) 树转换为二叉树

由于二叉树是有序的，为了避免混淆，对于无序树，我们约定树中的每个结点的孩子结点按从左到右的顺序进行编号。

将树转换成二叉树的步骤是： （1）加线。就是在所有兄弟结点之间加一条连线； （2）抹线。就是对树中的每个结点，只保留他与第一个孩子结点之间的连线，删除它与其它孩子结点之间的连线； （3）旋转。就是以树的根结点为轴心，将整棵树顺时针旋转一定角度，使之结构层次分明。

2) 森林转换为二叉树

森林是由若干棵树组成，可以将森林中的每棵树的根结点看作是兄弟，由于每棵树都可以转换为二叉树，所以森林也可以转换为二叉树。

将森林转换为二叉树的步骤是： （1）先把每棵树转换为二叉树； （2）第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子结点，用线连接起来。当所有的二叉树连接起来后得到的二叉树就是由森林转换得到的二叉树。

森林转换为二叉树的转换过程示意图

3) 二叉树转换为树

二叉树转换为树是树转换为二叉树的逆过程，其步骤是： （1）若某结点的左孩子结点存在，将左孩子结点的右孩子结点、右孩子结点的右孩子结点……都作为该结点的孩子结点，将该结点与这些右孩子结点用线连接起来； （2）删除原二叉树中所有结点与其右孩子结点的连线； （3）整理（1）和（2）两步得到的树，使之结构层次分明。

4) 二叉树转换为森林

二叉树转换为森林比较简单，其步骤如下： （1）先把每个结点与右孩子结点的连线删除，得到分离的二叉树； （2）把分离后的每棵二叉树转换为树； （3）整理第（2）步得到的树，使之规范，这样得到森林。

根据树与二叉树的转换关系以及二叉树的遍历定义可以推知，树的先序遍历与其转换的相应的二叉树的先序遍历的结果序列相同；树的后序遍历与其转换的二叉树的中序遍历的结果序列相同；树的层序遍历与其转换的二叉树的后序遍历的结果序列相同。由森林与二叉树的转换关系以及森林与二叉树的遍历定义可知，森林的先序遍历和中序遍历与所转换得到的二叉树的先序遍历和中序遍历的结果序列相同。

5) 常见考点

• 森林F 中叶子结点的个数= 二叉树T中 左孩子指针为空的结点个数

5.3.3 遍历

某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（）

• 空或只有一个结点
  

• 高度等于其结点数
  

• 任一结点无左孩子
  

• 任一结点无右孩子
  

正确答案：B

B 由于先序遍历是“根――左子树――右子树”，而后序遍历是“左子树――右子树――根”，若某二叉树的先序和后序序列正好相反，则该二叉树每层左、右子树只能有1个，即则该二叉树一定是高度等于其结点数。

1）若先序序列与后序序列相同,则或为空树,或为只有根结点的二叉树. 2）若中序序列与后序序列相同,则或为空树,或为任一结点至多只有左子树的二叉树. （3）若先序序列与中序序列相同,则或为空树,或为任一结点至多只有右子树的二叉树. （4）若中序序列与层次遍历序列相同,则或为空树,或为任一结点至多只有右子树的二叉树

5.3.4 线索二叉树

产生背景

现有一棵结点数目为n的二叉树，采用二叉链表的形式存储。对于每个结点均有指向左右孩子的两个指针域，而结点为n的二叉树一共有n-1条有效分支路径。那么，则二叉链表中存在2n-(n-1)=n+1个空指针域。那么，这些空指针造成了空间浪费。 例如：图所示一棵二叉树一共有10个结点，空指针^有11个。

问题提出

此外，当对二叉树进行中序遍历时可以得到二叉树的中序序列。例如：图所示二叉树的中序遍历结果为HDIBJEAFCG，可以得知A的前驱结点为E，后继结点为F。但是，这种关系的获得是建立在完成遍历后得到的，那么可不可以在建立二叉树时就记录下前驱后继的关系呢，那么在后续寻找前驱结点和后继结点时将大大提升效率。

解答

通过考察各种二叉链表，不管儿叉树的形态如何，空链域的个数总是多过非空链域的个数。准确的说，n各结点的二叉链表共有2n个链域，非空链域为n-1个，但其中的空链域却有n+1个。如下图所示。

因此，提出了一种方法，利用原来的空链域存放指针，指向树中其他结点。这种指针称为线索。

记ptr指向二叉链表中的一个结点，以下是建立线索的规则：

（1）如果ptr->lchild为空，则存放指向中序遍历序列中该结点的前驱结点。这个结点称为ptr的中序前驱；

（2）如果ptr->rchild为空，则存放指向中序遍历序列中该结点的后继结点。这个结点称为ptr的中序后继；

显然，在决定lchild是指向左孩子还是前驱，rchild是指向右孩子还是后继，需要一个区分标志的。因此，我们在每个结点再增设两个标志域ltag和rtag，注意ltag和rtag只是区分0或1数字的布尔型变量，其占用内存空间要小于像lchild和rchild的指针变量。结点结构如下所示。

其中：

（1）ltag为0时指向该结点的左孩子，为1时指向该结点的前驱；

（2）rtag为0时指向该结点的右孩子，为1时指向该结点的后继；

（3）因此对于上图的二叉链表图可以修改为下图的养子。

线索二叉树中某结点 R 没有左孩子的充要条件是（ ）。

• R.lchild=NULL
  

• R.ltag=0
  

• R.ltag=1
  

• R.rchild=NULL
  

正确答案：C

通过考察各种二叉链表，不管儿叉树的形态如何，空链域的个数总是多过非空链域的个数。准确的说，n各结点的二叉链表共有2n个链域，非空链域为n-1个，但其中的空链域却有n。

显然，在决定lchild是指向左孩子还是前驱，rchild是指向右孩子还是后继，需要一个区分标志的。+1个。因此，我们在每个结点再增设两个标志域ltag和rtag。

其中：

​ （1）ltag为0时指向该结点的左孩子，为1时指向该结点的前驱；

​ （2）rtag为0时指向该结点的右孩子，为1时指向该结点的后继；

线索二叉树结构实现

二叉线索树存储结构定义如下：

/* 二叉树的二叉线索存储结构定义*/

typedef enum
{
    Link,
    Thread
} PointerTag; //Link = 0表示指向左右孩子指针；Thread = 1表示指向前驱或后继的线索

typedef struct BitNode

{

    char data; //结点数据

    struct BitNode *lchild, *rchild; //左右孩子指针

    PointerTag Ltag; //左右标志

    PointerTag rtal;

} BitNode, *BiTree;

线索化的实质就是将二叉链表中的空指针改为指向前驱或后继的线索。由于前驱和后继信息只有在遍历该二叉树时才能得到，所以，线索化的过程就是在遍历的过程中修改空指针的过程。

中序遍历线索化的递归函数代码如下：

BiTree pre; //全局变量，始终指向刚刚访问过的结点

//中序遍历进行中序线索化

void InThreading(BiTree p)

{

    if (p)

    {

        InThreading(p->lchild); //递归左子树线索化

        //===

        if (!p->lchild) //没有左孩子

        {

            p->ltag = Thread; //前驱线索

            p->lchild = pre; //左孩子指针指向前驱
        }

        if (!pre->rchild) //没有右孩子

        {

            pre->rtag = Thread; //后继线索

            pre->rchild = p; //前驱右孩子指针指向后继(当前结点p)
        }

        pre = p;

        //===

        InThreading(p->rchild); //递归右子树线索化
    }
}

上述代码除了//===之间的代码以外，和二叉树中序遍历的递归代码机会完全一样。只不过将打印结点的功能改成了线索化的功能。

中间部分代码做了这样的事情：

因为此时p结点的后继还没有访问到，因此只能对它的前驱结点pre的右指针rchild做判断，if(!pre->rchild)表示如果为空，则p就是pre的后继，于是pre->rchild = p，并且设置pre->rtag = Thread，完成后继结点的线索化。如图：

if(!p->lchild)表示如果某结点的左指针域为空，因为其前驱结点刚刚访问过，赋值了pre，所以可以将pre赋值给p->lchild，并修改p->ltag = Thread（也就是定义为1）以完成前驱结点的线索化。

完成前驱和后继的判断后，不要忘记当前结点p赋值给pre，以便于下一次使用。

有了线索二叉树后，对它进行遍历时，其实就等于操作一个双向链表结构。

和双向链表结点一样，在二叉树链表上添加一个头结点，如下图所示，并令其lchild域的指针指向二叉树的根结点（图中第一步），其rchild域的指针指向中序遍历访问时的最后一个结点（图中第二步）。反之，令二叉树的中序序列中第一个结点中，lchild域指针和最后一个结点的rchild域指针均指向头结点（图中第三和第四步）。这样的好处是：我们既可以从第一个结点起顺后继进行遍历，也可以从最后一个结点起顺前驱进行遍历。

遍历代码如下所示。

//t指向头结点，头结点左链lchild指向根结点，头结点右链rchild指向中序遍历的最后一个结点。

//中序遍历二叉线索树表示二叉树t

int InOrderThraverse_Thr(BiTree t)

{

    BiTree p;

    p = t->lchild; //p指向根结点

    while (p != t) //空树或遍历结束时p == t

    {

        while (p->ltag == Link) //当ltag = 0时循环到中序序列的第一个结点

        {

            p = p->lchild;
        }

        printf("%c ", p->data); //显示结点数据，可以更改为其他对结点的操作

        while (p->rtag == Thread && p->rchild != t)

        {

            p = p->rchild;

            printf("%c ", p->data);
        }

        p = p->rchild; //p进入其右子树
    }

    return OK;
}

说明：

（1）代码中，p = t->lchild；意思就是上图中的第一步，让p指向根结点开始遍历； （2）while(p != t)其实意思就是循环直到图中的第四步出现，此时意味着p指向了头结点，于是与t相等（t是指向头结点的指针），结束循环，否则一直循环下去进行遍历操作； （3）while(p-ltag == Link)这个循环，就是由A->B->D->H，此时H结点的ltag不是link（就是不等于0），所以结束此循环； （4）然后就是打印H； （5）while(p->rtag == Thread && p->rchild != t)，由于结点H的rtag = Thread（就是等于1），且不是指向头结点。因此打印H的后继D，之后因为D的rtag是Link，因此退出循环； （6）p=p->rchild；意味着p指向了结点D的右孩子I； （7）.....，就这样不断的循环遍历，直到打印出HDIBJEAFCG，结束遍历操作。

从这段代码可以看出，它等于是一个链表的扫描，所以时间复杂度为O(n)。 由于充分利用了空指针域的空间（等于节省了空间），又保证了创建时的一次遍历就可以终生受用后继的信息（意味着节省了时间）。所以在实际问题中，如果所用的二叉树需要经过遍历或查找结点时需要某种遍历序列中的前驱和后继，那么采用线索二叉链表的存储结构就是非常不错的选择。

#include <stdio.h>
#include <stdlib.h>
#define ERROR 0
#define OK 1

typedef enum
{
    Link,
    Thread
} PointerTag; //link = 0表示指向左右孩子指针

//Thread = 1表示指向前驱或后继的线索

typedef struct BitNode
{
    char data;              //结点数据
    struct BitNode *lchild; //左右孩子指针
    struct BitNode *rchild;
    PointerTag ltag; //左右标志

    PointerTag rtag;

} BitNode, *BiTree;

BiTree pre; //全局变量，始终指向刚刚访问过的结点

//前序创建二叉树

void CreateTree(BiTree *t)

{

    char ch;
    scanf("%c", &ch);
    if (ch == '#')
    {
        *t = NULL;
    }

    else
    {

        (*t) = (BiTree)malloc(sizeof(BitNode));
        if ((*t) == NULL)
        {
            return;
        }
        (*t)->data = ch;
        CreateTree(&((*t)->lchild));
        CreateTree(&((*t)->rchild));
    }
}

//t指向头结点，头结点左链lchild指向根结点，头结点右链rchild指向中序遍历的最后一个结点。

//中序遍历二叉线索树表示的二叉树t

int InOrderThraverse_Thr(BiTree t)
{

    BiTree p;
    p = t->lchild; //p指向根结点
    while (p != t)
    {

        while (p->ltag == Link) //当ltag = 0时循环到中序序列的第一个结点

        {

            p = p->lchild;
        }

        printf("%c ", p->data); //显示结点数据，可以更改为其他对结点的操作
        while (p->rtag == Thread && p->rchild != t)
        {
            p = p->rchild;
            printf("%c ", p->data);
        }

        p = p->rchild; //p进入其右子树
    }
    return OK;
}

//中序遍历进行中序线索化

void InThreading(BiTree p)
{

    if (p)
    {

        InThreading(p->lchild); //递归左子树线索化
        if (!p->lchild)         //没有左孩子
        {

            p->ltag = Thread; //前驱线索

            p->lchild = pre; //左孩子指针指向前驱,这里是第3步
        }

        if (!pre->rchild) //没有右孩子

        {

            pre->rtag = Thread; //后继线索

            pre->rchild = p; //前驱右孩子指针指向后继(当前结点p)
        }

        pre = p;

        InThreading(p->rchild); //递归右子树线索化
    }
}

//建立头结点，中序线索二叉树

int InOrderThread_Head(BiTree *h, BiTree t)

{

    (*h) = (BiTree)malloc(sizeof(BitNode));

    if ((*h) == NULL)

    {

        return ERROR;
    }

    (*h)->rchild = *h;

    (*h)->rtag = Link;

    if (!t) //如果为NULL

    {

        (*h)->lchild = *h;

        (*h)->ltag = Link;
    }

    else

    {

        pre = *h;

        (*h)->lchild = t; //第一步

        (*h)->ltag = Link;

        InThreading(t); //找到最后一个结点

        pre->rchild = *h; //第四步

        pre->rtag = Thread;

        (*h)->rchild = pre; //第二步
    }
}

int main(int argc, char **argv)

{

    BiTree t;

    BiTree temp;

    printf("请输入前序二叉树的内容:\n");

    CreateTree(&t); //建立二叉树

    InOrderThread_Head(&temp, t); //加入头结点，并线索化

    printf("输出中序二叉树的内容:\n");

    InOrderThraverse_Thr(temp);

    printf("\n");

    return 0;
}

5.3.5 二叉排序树（二叉查找树、二叉搜索树）

1) 基本概念

1.二叉排序树

​ 二叉排序树（Binary sort tree，BST），又称为二叉查找树，或者是一棵空树；或者是具有下列性质的二叉树：

​ (1)若它的左子树不为空，则左子树上所有节点的值均小于它的根节点的值；

​ (2)若它的右子树不为空，则右子树上所有节点的值均大于它的根节点的值；

​ (3)它的左、右子树也分别为二叉排序树。

2) 二叉排序树操作

​ 二叉排序树是一种动态树表。它的特点是树的结构不是一次生成的，而是在查找过程中，当树中不存在关键字等于给定值的节点时再进行插入。新插入的节点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个节点的左孩子或右孩子节点，

​ 二叉排序树的操作有插入、删除、查询和遍历等。

注意：二叉排序树中没有值相同的节点

(1)插入

​ a.插入过程比较简单，首先判断当前要插入的值是否已经存在二叉排序树中，如果已经存在，则直接返回；如果不存在，则转b;

​ b.当前要插入的值不存在，则应找到适当的位置，将其插入。注意插入的新节点一定是叶子节点；

(2)删除

​ a.和插入一样，要删除一个给定值的节点，首先要判断这样节点是否存在，如果已经不存在，则直接返回；如果已经存在，则获取给定值节点的位置，根据不同情况进行删除、调整，转b；

​ b.如果待删节点只有左子树（只有右子树），则直接将待删节点的左子树（右子树）放在待删节点的位置，并释放待删节点的内存,否则转c;

​ c.如果待删节点既有左子树又有右子树，此时的删除可能有点复杂，但是也比较好理解。就是在待删节点的左子树中找到值最大的那个节点，将其放到待删节点的位置。

(3)查询

​ 查询过程比较简单，首先将关键字和根节点的关键字比较，如果相等则返回节点的位置(指针)；否则，如果小于根节点的关键字，则去左子树中继续查找；如果大于根节点的关键字，则去右子树中查找；如果找到叶子节点也没找到，则返回NULL。

​ 查询过程的最好情况就是上面的图中那样，节点在左右子树中分布比较均匀，此时查找的时间复杂度为O(logn)；最坏的情况就是在建立二叉排序树时，输入的关键字序列正好是有序的，此时形成的二叉排序树是一棵单支二叉树，此时查找退化成了单链表的查找，时间的复杂度为O(n).如下图：

(4)遍历

​ 由上面二排序树的定义可知，左子树的所有值均小于根节点，右子树的所有值均大于根节点，而这个特点正好和二叉树的中序遍历中--左子树->根节点->右子树不谋而合，所以对二叉排序树进行中序遍历得到的正好是一个有序的

3) 源码实现（C语言代码）

#include <stdio.h>
#include <stdlib.h>
//二叉排序树
 
typedef struct BSTNode
{
	int data;
	BSTNode *lchild;  //左孩子
	BSTNode *rchild;  //右孩子
}BSTNode, *BSTree;
 
bool Search(BSTree bst, int key, BSTree f, BSTree *p);
 
void InOderTraverse(BSTree bst)   //中序递归遍历二叉树
{
	if (NULL != bst)
	{
		InOderTraverse(bst->lchild);
		printf("%d ", bst->data);
		InOderTraverse(bst->rchild);
	}
}
 
static BSTNode* BuyNode(int data)   //生成一个节点并进行初始化
{
	BSTNode *pTmp = (BSTNode*)malloc(sizeof(BSTNode));
	if (NULL == pTmp)
	{
		exit(0);
	}
	pTmp->data = data;
	pTmp->lchild = NULL;
	pTmp->rchild = NULL;
	return pTmp;
}
 
bool Insert(BSTree *bst, int key)
{
	if (NULL == *bst)  //空树
	{
		*bst = BuyNode(key);   //插入根节点
		return true;
	}
	BSTNode *p;
	//先在二叉排序树中查找要插入的值是否已经存在
	if (!Search(*bst, key, NULL, &p))  //如果查找失败，则插入；此时p指向遍历的最后一个节点
	{
		BSTNode *pNew = BuyNode(key);
		if (key < p->data)  //将s作为p的左孩子
		{
			p->lchild = pNew;
		}
		else if (key > p->data)  //将s作为p的右孩子
		{
			p->rchild = pNew;
		}
		return true;  //插入成功
	}
	else
	{
		printf("\nThe node(%d) already exists.\n", key);
	}
	return false;
}
 
/*
删除分三种情况：
(1)被删除的节点无孩子，说明该节点是叶子节点，直接删
(2)被删除的节点只有左孩子或者右孩子，直接删，并将其左孩子或者右孩子放在被删节点的位置
(3)被删除的节点既有右孩子又有右孩子
*/
 
BSTNode* FindParent(BSTree bst, BSTNode *child)
{
	if (NULL == bst)
	{
		return NULL;
	}
 
	if (bst->lchild == child || bst->rchild == child)
	{
		return bst;
	}
	else if(NULL != bst->lchild)
	{
		FindParent(bst->lchild, child);
	}
	else if (NULL != bst->rchild)
	{
		FindParent(bst->rchild, child);
	}
}
 
void Delete(BSTree *bst, int key)
{
	if (NULL == *bst)
	{
		exit(1);  //空树直接报错
	}
	BSTNode *p;
	BSTNode *f = NULL;
	BSTNode *q, *s;
	if (Search(*bst, key, NULL, &p)) //确实存在值为key的节点,则p指向该节点
	{
 
		if (NULL == p->lchild && NULL != p->rchild)  //无左孩子,有右孩子
		{
			q = p->rchild;
			p->data = q->data;    //因为两个节点之间本质的不同在于数据域的不同，而与放在哪个地址没有关系
			p->rchild = q->rchild;
			p->lchild = q->lchild;
			free(q);
		}
		else if (NULL == p->rchild && NULL != p->lchild)  //无右孩子,有左孩子
		{
			q = p->lchild;
			p->data = q->data;
			p->rchild = q->rchild;
			p->lchild = q->lchild;
			free(q);
		}
		else if (NULL != p->rchild && NULL != p->lchild) //既有左孩子，又有右孩子
		{
			q = p;
			s = p->lchild;   //找左孩子的最右孩子
			while (s->rchild)
			{
				q = s;
				s = s->rchild;
			}
			p->data = s->data;
 
			if (q != p)
			{
				q->rchild = p->lchild;
			}
			else
			{
				q->lchild = s->lchild;
			}
			free(s);
		}
		else
		{
			if (*bst == p)   //只有一个根节点
			{
				free(*bst);
				*bst = NULL;
				return;
			}
 
			BSTNode* parent = FindParent(*bst, p);
			if (parent->lchild == p)
			{
				parent->lchild = NULL;
			}
			else
			{
				parent->rchild = NULL;
			}
			free(p);
		}
	}
}
 
bool Search(BSTree bst, int key, BSTree f, BSTree *p)  //查找成功时，p指向值为key的节点。如果查找失败，则p指向遍历的最后一个节点
{
	if (!bst)
	{
		*p = f;
		return false;
	}
	if (bst->data == key)  //查找成功，直接返回
	{
		*p = bst;
		return true;
	}
	else if (bst->data < key)
	{
		return Search(bst->rchild, key, bst, p);
	}
	return Search(bst->lchild, key, bst, p);
}
 
int main(void)
{
	BSTNode *root = NULL;
	Insert(&root, 45);
	Insert(&root, 24);
	Insert(&root, 53);
	Insert(&root, 12);
	Insert(&root, 90);
	InOderTraverse(root);
	printf("\n%d ", Insert(&root, 45));   //输出0表示插入失败，输出1表示插入成功
	printf("%d\n", Insert(&root, 4));
	InOderTraverse(root);
	printf("\n");
	Delete(&root, 4);      //删除节点45
	Delete(&root, 45);      //删除节点45
	Delete(&root, 24);      //删除节点45
	Delete(&root, 53);      //删除节点45
	Delete(&root, 12);      //删除节点45
	Delete(&root, 90);      //删除节点45
	InOderTraverse(root);
	return 0;
}

运行结果：

5.3.6 平衡二叉树

平衡二叉搜索树，又被称为AVL树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

由于普通的二叉查找树会容易失去”平衡“，极端情况下，二叉查找树会退化成线性的链表，导致插入和查找的复杂度下降到 O(n) ，所以，这也是平衡二叉树设计的初衷。那么平衡二叉树如何保持”平衡“呢？根据定义，有两个重点，一是左右两子树的高度差的绝对值不能超过1，二是左右两子树也是一颗平衡二叉树。

如下图所示，左图是一棵平衡二叉树，根节点10，左右两子树的高度差是1，而右图，虽然根节点左右两子树高度差是0，但是右子树15的左右子树高度差为2，不符合定义，所以右图不是一棵平衡二叉树。

由此可以看出平衡二叉树是一棵高度平衡的二叉查找树。所以，要构建跟维系一棵平衡二叉树就比普通的二叉树要复杂的多。在构建一棵平衡二叉树的过程中，当有新的节点要插入时，检查是否因插入后而破坏了树的平衡，如果是，则需要做旋转去改变树的结构。

关于旋转，这东西不拿动态图将还真很难讲明白。所以我就借一下 最容易懂得红黑树 这篇文章中左旋右旋的图来讲。

左旋：

右旋：

不同于顺时针跟逆时针变换这种方式去记忆，上面两个动态图特别方便记忆跟理解：

左旋就是将节点的右支往左拉，右子节点变成父节点，并把晋升之后多余的左子节点出让给降级节点的右子节点；

而右旋就是反过来，将节点的左支往右拉，左子节点变成了父节点，并把晋升之后多余的右子节点出让给降级节点的左子节点。

即左旋就是往左变换，右旋就是往右变换。不管是左旋还是右旋，旋转的目的都是将节点多的一支出让节点给另一个节点少的一支。

举个例子，像上图是否平衡二叉树的图里面，左图在没插入前”19“节点前，该树还是平衡二叉树，但是在插入”19“后，导致了”15“的左右子树失去了”平衡“，所以此时可以将”15“节点进行左旋，让”15“自身把节点出让给”17“作为”17“的左树，使得”17“节点左右子树平衡，而”15“节点没有子树，左右也平衡了。如下图，

由于在构建平衡二叉树的时候，当有新节点插入时，都会判断插入后时候平衡，这说明了插入新节点前，都是平衡的，也即高度差绝对值不会超过1。当新节点插入后，有可能会有导致树不平衡，这时候就需要进行调整，而可能出现的情况就有4种，分别称作左左，左右，右左，右右。

左左：

左左即为在原来平衡的二叉树上，在节点的左子树的左子树下，有新节点插入，导致节点的左右子树的高度差为2，如上即为”10“节点的左子树”7“，的左子树”4“，插入了节点”5“或”3“导致失衡。

左左调整其实比较简单，只需要对节点进行右旋即可，如下图，对节点”10“进行右旋，

注意：如果对左右旋变换还不是很懂或不是很熟练的，可以对照着前面的那两个动图去想象，自己动手变换几次，就明白了。

左右：

左右即为在原来平衡的二叉树上，在节点的左子树的右子树下，有新节点插入，导致节点的左右子树的高度差为2，如上即为”11“节点的左子树”7“，的右子树”9“，插入了节点”10“或”8“导致失衡。

左右的调整就不能像左左一样，进行一次旋转就完成调整。我们不妨先试着让左右像左左一样对”11“节点进行右旋，结果图如下，右图的二叉树依然不平衡，而右图就是接下来要讲的右左，即左右跟右左互为镜像，左左跟右右也互为镜像。

右右跟左左一样，只需要旋转一次就能把树调整平衡，而左右跟右左也一样，都要进行旋转两次才能把树调整平衡，所以，首先上图的这种调整是错误的，正确的调整方式是，将左右进行第一次旋转，将左右先调整成左左，然后再对左左进行调整，从而使得二叉树平衡。

即先对上图的节点”7“进行左旋，使得二叉树变成了左左，之后再对”11“节点进行右旋，此时二叉树就调整完成，如下图，

右左：

右左即为在原来平衡的二叉树上，在节点的右子树的左子树下，有新节点插入，导致节点的左右子树的高度差为2，如上即为”11“节点的右子树”15“，的左子树”13“，插入了节点”12“或”14“导致失衡。

前面也说了，右左跟左右其实互为镜像，所以调整过程就反过来，先对节点”15“进行右旋，使得二叉树变成右右，之后再对”11“节点进行左旋，此时二叉树就调整完成，如下图，

右右：

右右即为在原来平衡的二叉树上，在节点的右子树的右子树下，有新节点插入，导致节点的左右子树的高度差为2，如上即为”11“节点的右子树”13“，的左子树”15“，插入了节点”14“或”19“导致失衡。

右右只需对节点进行一次左旋即可调整平衡，如下图，对”11“节点进行左旋。

平衡二叉树构建的过程，就是节点插入的过程，插入失衡情况就上面4种，算简单了，下面讲下平衡二叉树节点的删除，删除的情况会复杂一点，复杂的原因主要在于删除了节点之后要维系二叉树的平衡，但是删除二叉树节点总结起来就两个判断：①删除的是什么类型的节点？②删除了节点之后是否导致失衡？

节点的类型有三种：1.叶子节点；2.只有左子树或只有右子树；3.既有左子树又有右子树。

针对这三种节点类型，再引入判断②，所以处理思路分别是：

（1）当删除的节点是叶子节点，则将节点删除，然后从父节点开始，判断是否失衡，如果没有失衡，则再判断父节点的父节点是否失衡，直到根节点，此时到根节点还发现没有失衡，则说此时树是平衡的；如果中间过程发现失衡，则判断属于哪种类型的失衡（左左，左右，右左，右右），然后进行调整。

（2）删除的节点只有左子树或只有右子树，这种情况其实就比删除叶子节点的步骤多一步，就是将节点删除，然后把仅有一支的左子树或右子树替代原有结点的位置，后面的步骤就一样了，从父节点开始，判断是否失衡，如果没有失衡，则再判断父节点的父节点是否失衡，直到根节点，如果中间过程发现失衡，则根据失衡的类型进行调整。

（3）删除的节点既有左子树又有右子树，这种情况又比上面这种多一步，就是中序遍历，找到待删除节点的前驱或者后驱都行，然后与待删除节点互换位置，然后把待删除的节点删掉，后面的步骤也是一样，判断是否失衡，然后根据失衡类型进行调整。

最后总结一下，平衡二叉树是一棵高度平衡的二叉树，所以查询的时间复杂度是 O(logN) 。插入的话上面也说，失衡的情况有4种，左左，左右，右左，右右，即一旦插入新节点导致失衡需要调整，最多也只要旋转2次，所以，插入复杂度是 O(1) ，但是平衡二叉树也不是完美的，也有缺点，从上面删除处理思路中也可以看到，就是删除节点时有可能因为失衡，导致需要从删除节点的父节点开始，不断的回溯到根节点，如果这棵平衡二叉树很高的话，那中间就要判断很多个节点。所以后来也出现了综合性能比其更好的树—-红黑树，后面再讲。

单选题

题号	题目	答案
1	AVL树是一种平衡的二叉搜索树，树中任一结点具有下列哪一特性：	左、右子树高度差的绝对值不超过1
2		C
3	在下列所示的平衡二叉树中，插入关键字48后得到一棵新平衡二叉树。在新平衡二叉树中，关键字37所在结点的左、右子结点中保存的关键字分别是：	24、53
4	12个结点的AVL树的最大深度是？	5
5	若AVL树的深度是6（空树的深度定义为-1），则该树的最少结点数是：	33
6	将 8, 9, 7, 2, 3, 5, 6, 4 顺序插入一棵初始为空的AVL树。下列句子中哪句是错的？	C
7	将一系列数字顺序一个个插入一棵初始为空的AVL树。下面哪个系列的第一次旋转是“右-左”双旋？	D
8	将 1, 2, 3, 6, 5, 4 顺序一个个插入一棵初始为空的AVL树，会经历下列哪些旋转？	一个“右-右”旋和两个“右-左”旋
9		A
10	首先将 28, 23, 54, 61, 98, 37 插入一棵初始为空的平衡二叉树（AVL树），然后马上插入下列选项中的一个键值。哪个键值将引起 RL 旋转？	70

选择题题解

2、如图所示 3、转的过程：

• 插入48之后属于右左双旋转的情况，按照图示的方法先做右单旋转，再做左单旋转
• 右单旋转：以37为轴，53顺时针旋转（向下），原本是37左孩子的48成为53的左孩子
• 24的右孩子由53变为37
• 左单旋转：仍然以37为轴，24逆时针旋转（向下），成为37的左孩子 24的左子树高度为1，右字数高度为3，属于RL型，RL型的变化就这么做的，具体RL型解释如下 具体的RL型的旋转规则，大佬说记住就可以了，哎拼命记吧。

总结

高度为h 的最小平衡二叉树的节点数$N_n=N_{n-1}+N_{n-2}+1,N_0=0,N_1=1$

5.3.7 折半查找判定树

长度为n的折半查找判定树的构造方法为：

⑴ 当n=0时，折半查找判定树为空；bai

⑵ 当n＞0时，折半查找判定树的根结点是有序表中序号为mid=(n+1)/2的记录，根结点的左子树是与有序表r[1] ~ r[mid-1]相对应的折半查找判定树，根结点的右子树是与r[mid+1] ~ r[n]相对应的折半查找判定树。

题目中 长度为10的折半查找判定树的具体生成过程为：

⑴ 在长度为10的有序表中进行折半查找，不论查找哪个记录，都必须先和中间记录进行比较，而中间记录的序号为(1+10)/2=5（注意是整除即向下取整），即判定树的根结点是5，如图(a)所示；

⑵ 考虑判定树的左子树，即将查找区间调整到左半区，此时的查找区间是[1，4]，也就是说，左分支上为根结点的值减1，代表查找区间的高端high，此时，根结点的左孩子是(1+4)/2=2，如图(b)所示；

⑶ 考虑判定树的右子树，即将查找区间调整到右半区，此时的查找区间是[6，10]，也就是说，右分支上为根结点的值加1，代表查找区间的低端low，此时，根结点的右孩子是(6+10)/2=8，如图(c)所示；

⑷ 重复⑵⑶步，依次确定每个结点的左右孩子，如图(d)所示。

5.4 应用

1) 哈夫曼树(最优二叉树)

一. 目的：

找出存放一串字符所需的最少的二进制编码

带权路径最短

二. 构造方法：

首先统计出每种字符出现的频率！（也可以是概率）权值

---

​ 例如：频率表 A：60, B:45, C:13 D:69 E:14 F:5 G:3

第一步：找出字符中最小的两个，小的在左边，大的在右边，组成二叉树。在频率表中删除此次找到的两个数，并加入此次最小两个数的频率和。

F和G最小，因此如图，从字符串频率计数中删除F与G，并返回G与F的和 8给频率表**

重复第一步：

---

频率表 A：60, B:45, C:13 D:69 E:14 FG:8

最小的是 FG：8与C：13，因此如图，并返回FGC的和：21给频率表。**

重复第一步：

---

频率表 A：60 B: 45 D: 69 E: 14 FGC: 21

如图

-----------------------------------------------------------------------------------------------------

重复第一步

-----------------------------------------------------------------------------------------------------

频率表 A：60 B: 45 D: 69 FGCE: 35

-----------------------------------------------------------------------------------------------------

重复第一步

-----------------------------------------------------------------------------------------------------

频率表 A：60 D: 69 FGCEB: 80

-----------------------------------------------------------------------------------------------------

重复第一步

-----------------------------------------------------------------------------------------------------

频率表 AD：129 FGCEB: 80

添加 0 和 1，规则左0 右1

频率表 A：60, B:45, C:13 D:69 E:14 F:5 G:3

每个 字符 的 二进制编码 为（从根节点 数到对应的叶子节点，路径上的值拼接起来就是叶子节点字母的应该的编码）

字符	编码
A	10
B	01
C	0011
D	11
E	000
F	00101
G	00100

三. 计算带权路径

哈夫曼树是一种带权路径长度最短的二叉树，也称为最优二叉树。下面用一幅图来说明。

它们的带权路径长度分别为：

图a： WPL=5*2+7*2+2*2+13*2=54

图b： WPL=5*3+2*3+7*2+13*1=48

可见，图b的带权路径长度较小，我们可以证明图b就是哈夫曼树(也称为最优二叉树)。

2) 常见考点

已知完全二叉树总结点数 N，求叶子结点数 n？	如果是偶数个节点，叶子节点等于总节点除以2， 即 N % 2==0， n = N/2 如果是奇数个叶子节点等于(总节点+1)除以2, 即 N % 2 == 1, n = (N+1)/2
已知完全二叉树叶子结点数n, 求总结点数N？	2n
	哈夫曼树是二叉树，所有符合的都是叶子节点，设叶子节点个数为m,则，生成的哈夫曼树结点个数为2m-1

6. 图

6.1 概念

如果路径上的各顶点均不互相重复，称这样的路径为简单路径。如果路径上的第一个顶点与最后一个顶点重合，这样的路径称为回路(cycle)或环或圈。

回路不是简单路径

无向图连通至少需要 n-1

有向图连通至少需要n

无向图任何情况下连通至少 (n-1)(n-2)/2+1

有向图任何情况下连通

6.2 图的存储

6.2.1 邻接表

6.2.2 邻接矩阵

6.3 图的遍历

6.3.1 深度优先遍历

6.3.2 广度优先遍历

6.4 应用

通过前面的学习，对于含有 n 个顶点的连通图来说可能包含有多种生成树，例如图 1 所示：

图 1 连通图的生成树

图 1 中的连通图和它相对应的生成树，可以用于解决实际生活中的问题：假设A、B、C 和 D 为 4 座城市，为了方便生产生活，要为这 4 座城市建立通信。对于 4 个城市来讲，本着节约经费的原则，只需要建立 3 个通信线路即可，就如图 1（b）中的任意一种方式。

在具体选择采用（b）中哪一种方式时，需要综合考虑城市之间间隔的距离，建设通信线路的难度等各种因素，将这些因素综合起来用一个数值表示，当作这条线路的权值。

图 2 无向网

假设通过综合分析，城市之间的权值如图 2（a）所示，对于（b）的方案中，选择权值总和为 7 的两种方案最节约经费。

这就是本节要讨论的最小生成树的问题，简单得理解就是给定一个带有权值的连通图（连通网），如何从众多的生成树中筛选出权值总和最小的生成树，即为该图的最小生成树。

6.4.1 最小生成树

1) Prim 算法 (普里姆算法)

普里姆算法在找最小生成树时，将顶点分为两类，一类是在查找的过程中已经包含在树中的（假设为 A 类），剩下的是另一类（假设为 B 类）。

• 对于给定的连通网，起始状态全部顶点都归为 B 类。
• 在找最小生成树时，选定任意一个顶点作为起始点，并将之从 B 类移至 A 类；
• 然后找出 B 类中到 A 类中的顶点之间权值最小的顶点，将之从 B 类移至 A 类，如此重复，直到 B 类中没有顶点为止。
• 所走过的顶点和边就是该连通图的最小生成树。

样例1

例如，通过普里姆算法查找的最小生成树的步骤为：

假如从顶点A出发，顶点 B、C、D 到顶点 A 的权值分别为 2、4、2，所以，对于顶点 A 来说，顶点 B 和顶点 D 到 A 的权值最小，假设先找到的顶点 B：

继续分析顶点 C 和 D，顶点 C 到 B 的权值为 3，到 A 的权值为 4；顶点 D 到 A 的权值为 2，到 B 的权值为无穷大（如果之间没有直接通路，设定权值为无穷大）。所以顶点 D 到 A 的权值最小：

最后，只剩下顶点 C，到 A 的权值为 4，到 B 的权值和到 D 的权值一样大，为 3。所以该连通图有两个最小生成树：

具体实现代码为：

#include <stdio.h>
#include <stdlib.h>
#define VertexType int
#define VRType int
#define MAX_VERtEX_NUM 20
#define InfoType char   
#define INFINITY 65535
typedef struct {
    VRType adj;                             //对于无权图，用 1 或 0 表示是否相邻；对于带权图，直接为权值。
    InfoType * info;                        //弧额外含有的信息指针
}ArcCell,AdjMatrix[MAX_VERtEX_NUM][MAX_VERtEX_NUM];

typedef struct {
    VertexType vexs[MAX_VERtEX_NUM];        //存储图中顶点数据
    AdjMatrix arcs;                         //二维数组，记录顶点之间的关系
    int vexnum,arcnum;                      //记录图的顶点数和弧（边）数
}MGraph;

//根据顶点本身数据，判断出顶点在二维数组中的位置
int LocateVex(MGraph G,VertexType v){
    int i=0;
    //遍历一维数组，找到变量v
    for (; i<G.vexnum; i++) {
        if (G.vexs[i]==v) {
            return i;
        }
    }
    return -1;
}
//构造无向网
void CreateUDN(MGraph* G){
    scanf("%d,%d",&(G->vexnum),&(G->arcnum));
    for (int i=0; i<G->vexnum; i++) {
        scanf("%d",&(G->vexs[i]));
    }
    for (int i=0; i<G->vexnum; i++) {
        for (int j=0; j<G->vexnum; j++) {
            G->arcs[i][j].adj=INFINITY;
            G->arcs[i][j].info=NULL;
        }
    }
    for (int i=0; i<G->arcnum; i++) {
        int v1,v2,w;
        scanf("%d,%d,%d",&v1,&v2,&w);
        int m=LocateVex(*G, v1);
        int n=LocateVex(*G, v2);
        if (m==-1 ||n==-1) {
            printf("no this vertex\n");
            return;
        }
        G->arcs[n][m].adj=w;
        G->arcs[m][n].adj=w;
    }
}

//辅助数组，用于每次筛选出权值最小的边的邻接点
typedef struct {
    VertexType adjvex;//记录权值最小的边的起始点
    VRType lowcost;//记录该边的权值
}closedge[MAX_VERtEX_NUM];
closedge theclose;//创建一个全局数组，因为每个函数中都会使用到
//在辅助数组中找出权值最小的边的数组下标，就可以间接找到此边的终点顶点。
int minimun(MGraph G,closedge close){
    int min=INFINITY;
    int min_i=-1;
    for (int i=0; i<G.vexnum; i++) {
        //权值为0，说明顶点已经归入最小生成树中；然后每次和min变量进行比较，最后找出最小的。
        if (close[i].lowcost>0 && close[i].lowcost < min) {
            min=close[i].lowcost;
            min_i=i;
        }
    }
    //返回最小权值所在的数组下标
    return min_i;
}
//普里姆算法函数，G为无向网，u为在网中选择的任意顶点作为起始点
void miniSpanTreePrim(MGraph G,VertexType u){
    //找到该起始点在顶点数组中的位置下标
    int k=LocateVex(G, u);
    //首先将与该起始点相关的所有边的信息：边的起始点和权值，存入辅助数组中相应的位置，例如（1，2）边，adjvex为0，lowcost为6，存入theclose[1]中，辅助数组的下标表示该边的顶点2
    for (int i=0; i<G.vexnum; i++) {
        if (i !=k) {
            theclose[i].adjvex=k;
            theclose[i].lowcost=G.arcs[k][i].adj;
        }
    }
    //由于起始点已经归为最小生成树，所以辅助数组对应位置的权值为0，这样，遍历时就不会被选中
    theclose[k].lowcost=0;
    //选择下一个点，并更新辅助数组中的信息
    for (int i=1; i<G.vexnum; i++) {
        //找出权值最小的边所在数组下标
        k=minimun(G, theclose);
        //输出选择的路径
        printf("v%d v%d\n",G.vexs[theclose[k].adjvex],G.vexs[k]);
        //归入最小生成树的顶点的辅助数组中的权值设为0
        theclose[k].lowcost=0;
        //信息辅助数组中存储的信息，由于此时树中新加入了一个顶点，需要判断，由此顶点出发，到达其它各顶点的权值是否比之前记录的权值还要小，如果还小，则更新
        for (int j=0; j<G.vexnum; j++) {
            if (G.arcs[k][j].adj<theclose[j].lowcost) {
                theclose[j].adjvex=k;
                theclose[j].lowcost=G.arcs[k][j].adj;
            }
        }
    }
    printf("\n");
}

int main(){
    MGraph G;
    CreateUDN(&G);
    miniSpanTreePrim(G, 1);
}

样例2

使用普里姆算法找图 3 所示无向网的最小生成树的测试数据为：

6,10
1
2
3
4
5
6
1,2,6
1,3,1
1,4,5
2,3,5
2,5,3
3,4,5
3,5,6
3,6,4
4,6,2
5,6,6
运行结果为：
v1 v3
v3 v6
v6 v4
v3 v2
v2 v5

样例3

普里姆算法的运行效率只与连通网中包含的顶点数相关，而和网所含的边数无关。所以普里姆算法适合于解决边稠密的网，该算法运行的

时间复杂度

为：O(n2)

2) 克鲁斯卡尔算法

1. 将图中的所有边都去掉；

2. 将边按权值从小到大的顺序添加到图中，保证添加的过程中不会形成环 ；

3. 重复上一步直到连接所有顶点，此时就生成了最小生成树。这是一种贪心策略。

#include <bits/stdc++.h>
using namespace std;

struct edge//纪录边的信息
{
    int start;
    int end;
    int weight;
};

//克鲁斯卡尔算法
void Kruskal(int data[10][3])
{
    int data2[10][2] = {0};
    multiset<int> st1;
    vector<edge> vec;//存储所有边的信息
    edge temp;
    for (int j = 0; j < 10; ++j)//初始化所有边的信息
    {
        temp.start = data[j][0];
        temp.end = data[j][1];
        temp.weight = data[j][2];
        vec.push_back(temp);
    }
    //按权值排序
    sort(vec.begin(), vec.end(), [](const edge &e1, const edge &e2) -> bool
    { 
        return e1.weight < e2.weight ? true : false ;
    });
    for (int j = 0; j < 10; ++j)
    {
        //st1存放的是已经加入的边用于判断是否会形成环（如果起点和终点都在st1中则加入该边会形成环）
        if (st1.find(vec[j].start) != st1.end() && st1.find(vec[j].end) != st1.end())
            continue;
        else
        {
            data2[j][0] = vec[j].start;//data2存放的是组成最小生成树的边
            data2[j][1] = vec[j].end;
            st1.insert(vec[j].start);
            st1.insert(vec[j].end);
        }
    }
    for (int j = 0; j < 10; ++j)
    {
        if (data2[j][0] != 0)
            cout << data2[j][0] << " " << data2[j][1] << endl;
    }
}

int main(int argc, char const *argv[])
{
    int data[10][3] = //所有边的信息
    {
        {1,2,6},{1,6,12},
        {1,5,10},{2,3,3},
        {2,4,5},{2,6,8},
        {3,4,7},{4,6,11},
        {4,5,9},{5,6,16}
    };
    Kruskal(data);
    return 0;
}

6.4.2 最短路径

迪杰特斯拉算法

1. 找出最便宜的顶点，即距离出发顶点距离最近的顶点，作为新的出发顶点
2. 更新该顶点的邻居的开销
3. 重复（1）（2）步骤，直到对每个顶点都做了此操作
4. 计算最终路径

用Dijkstra算法求A到图中各点的最短路径

Dijkstral算法伪代码如下：

​ n次循环至n个顶点全部遍历：

​ 1.1从权值数组中找到权值最小的，标记该边端点k

​ 1.2打印该路径及权值

​ 2.1如果存在经过顶点k到顶点i的边比v->i的权值小

​ 2.2更新权值数组及对应路径

源码：

#include<iostream>
#include<iomanip>//控制格式
#include<string>


#define INF 0x3f3f3f3f//定义无穷大
using namespace std;


#define vertexNum 5//源点数
int G[vertexNum][vertexNum];//邻接矩阵
string vertex[]={"A","B","C","D","E"};//源点字符串组
void CreateMGraph()
{
  for(int i=0;i<vertexNum;i++)
    for(int j=0;j<vertexNum;j++)
  {
    G[i][j]=INF;
  }
  G[0][1]=10;G[0][3]=30;G[0][4]=100;
  G[1][2]=50;
  G[2][4]=10;
  G[3][2]=20;G[3][4]=60;
}
void Dijkstra(int v)
{
  int dist[vertexNum],i,num,k,min;//dist为权值存储数组
  string path[vertexNum];
  int s[vertexNum]={0};//初始化标记数组
  cout<<"初始权值数组和路径字符串数组:"<<endl;
  for(i=0;i<vertexNum;i++)
  {
    dist[i]=G[v][i];
    path[i]=vertex[v]+"-->"+vertex[i];
    cout<<path[i]<<" ";
    if(dist[i]!=INF) cout<<dist[i]<<endl;
    else cout<<"∞"<<endl;
  }
  s[v]=1;//标记第一个访问点
  dist[v]=0;
  num=1;//计数器
  cout<<"打印源点A到各点的最短路径及其权值和："<<endl;
  while(num<=vertexNum)//当不取等号时将不会获得A到自身的路径
  {
    min=INF;
    for(k=0,i=0;i<vertexNum;i++)//查找最小值
      {
      if(s[i]==0&&(dist[i]<min)) {min=dist[i];k=i;}
      }
    cout<<path[k]<<" "<<dist[k]<<endl;//打印路径及对应路径长（权值和）
    s[k]=1;num++;
    for(i=0;i<vertexNum;i++)//更新权值数组和字符串数组
      if((dist[i]>dist[k]+G[k][i])&&(G[k][i]!=INF))
    {
      dist[i]=dist[k]+G[k][i];
      path[i]=path[k]+"-->"+vertex[i];
    }
  }
}



int main()
{
  CreateMGraph();//创建邻接矩阵
  cout<<"打印邻接矩阵："<<endl;
   for(int i=0;i<vertexNum;i++)
    for(int j=0;j<vertexNum;j++)
  {
    if(G[i][j]==INF) cout<<setw(4)<<"∞";
    else cout<<setw(4)<<G[i][j];
    if(j==vertexNum-1) cout<<endl;
  }
  Dijkstra(0);//以A为源点
  return 0;

}

示例截图：

Floyd 算法

6.4.3 拓扑排序,关键路径

1. AOV网络

AOV网（Activity On Vertex NetWork）用顶点表示活动，边表示活动（顶点）发生的先后关系。

若网中所有活动均可以排出先后顺序（任两个活动之间均确定先后顺序），则称网是拓扑有序的。

2. 拓扑排序

1) 概念

在图论中，拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。且该序列必须满足下面两个条件：

每个顶点出现且只出现一次。 若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。 有向无环图（DAG）才有拓扑排序，非DAG图没有拓扑排序一说。

时间复杂度

如果AOV网络有n个顶点，e条边，在拓扑排序的过程中，搜索入度为零的顶点所需的时间是O(n)。在正常情况下，每个顶点进一次栈，出一次栈，所需时间O(n)。每个顶点入度减1的运算共执行了e次。所以总的时间复杂为O(n+e)。

2) 算法步骤

• 在网络中选择一个入度为0的顶点输出；
• 在图中删除该顶点及所有以该顶点为起点的边；
• 重复上述过程，直至所有边均被输出。

3) 算法图解

4) 代码

#include <bits/stdc++.h>
using namespace std;

const int  M  = 10001;
int matrix[M][M];
int indegree[M]; //book已排序的顶点个数

int main(int argc, char const *argv[])
{
    int i, j, a, b, k, book = 0, n, m;
    cin >> n >> m;
    for (i = 1; i <= m; ++i)
    {
        cin >> a >> b;
        matrix[a][b]=1;
        indegree[b]++;
    }
    for (i = 1; i <= n; ++i) 
    {
        for (j = 1; j <= n; ++j) 
        {
            if (indegree[j] == 0) 
            { 
                cout << j << " ";
                //遍历所有入度为0的顶点
                indegree[j] = -1;
                book++;
                for (k=1; k <= n; k++)
                {
                   if (matrix[j][k] == 1)
                    {
                        //遍历所有入度为1的顶点
                        matrix[j][k] = 0;
                        indegree[k]--;
                    }
               }
               break;
            }
        }
    }   
    system("pause");
    return 0;
}

5) 应用

拓扑排序通常用来“排序”具有依赖关系的任务。比如，如果用一个DAG图来表示一个工程，其中每个顶点表示工程中的一个任务，用有向边<A,B><A,B>表示在做任务 B 之前必须先完成任务 A。故在这个工程中，任意两个任务要么具有确定的先后关系，要么是没有关系，绝对不存在互相矛盾的关系（即环路）。

3. AOE网络

AOE网的定义：在带权有向图中若以顶点表示事件，有向边表示活动，边上的权值表示该活动持续的时间，这样的图简称为AOE网。

4. 有向无环图——描述表达式

DAG描述表达式

节省存储空间

解题方法

Step1：把各个操作数不重复地排成一排

Step2：标出各个运算符的生效顺序（先后顺序有点出入无所谓）

Step3：按顺序加入运算符，注意“分层“ (利用下面一层的运算结果来进行)

7.查找

8. 排序

十种常见排序算法可以分为两大类：

• 比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
• 非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。

8.0 算法复杂度

相关概念

• 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
• 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
• 时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
• **空间复杂度：**是指算法在计算机

内执行时所需存储空间的度量，它也是数据规模n的函数。

每一趟排序，都会有一个元素在最终的位置上，堆排序，冒泡排序，快速排序，选择排序

和序列初始化状态没有关系的有 简单选择排序和二路归并排序

8.1 冒泡排序（Bubble Sort）

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

1.1 算法描述

• 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
• 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
• 针对所有的元素重复以上的步骤，除了最后一个；
• 重复步骤1~3，直到排序完成。

1.2 动图演示

1.3 代码实现

function bubbleSort(arr)
{
    var  len = arr.length;
    for (var  i = 0; i < len - 1; i++)
    {
        for (var  j = 0; j < len - 1 - i; j++)
        {
            if (arr[j] > arr[j + 1])
            {                         // 相邻元素两两对比
                var  temp = arr[j + 1]; // 元素交换
                arr[j + 1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    return arr;
}

8.2 选择排序（Selection Sort）

选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

2.1 算法描述

n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：

• 初始状态：无序区为R[1..n]，有序区为空；
• 第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
• n-1趟结束，数组有序化了。

2.2 动图演示

2.3 代码实现

function selectionSort(arr)
{
    var len = arr.length;
    var minIndex, temp;
    for (var i = 0; i < len - 1; i++)
    {
        minIndex = i;
        for (var j = i + 1; j < len; j++)
        {
            if (arr[j] < arr[minIndex])
            {                 // 寻找最小的数
                minIndex = j; // 将最小数的索引保存
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;
}

2.4 算法分析

表现最稳定的排序算法之一，因为无论什么数据进去都是O(n2)的时间复杂度，所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。理论上讲，选择排序可能也是平时排序一般人想到的最多的排序方法了吧。

8.3 插入排序（Insertion Sort）

插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

3.1 算法描述

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

• 从第一个元素开始，该元素可以认为已经被排序；
• 取出下一个元素，在已经排序的元素序列中从后向前扫描；
• 如果该元素（已排序）大于新元素，将该元素移到下一位置；
• 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
• 将新元素插入到该位置后；
• 重复步骤2~5。

3.2 动图演示

3.2 代码实现

function insertionSort(arr)
{
    var len = arr.length;
    var preIndex, current;
    for (var i = 1; i < len; i++)
    {
        preIndex = i - 1;
        current = arr[i];
        while (preIndex >= 0 && arr[preIndex] > current)
        {
            arr[preIndex + 1] = arr[preIndex];
            preIndex--;
        }
        arr[preIndex + 1] = current;
    }
    return arr;
}

3.4 算法分析

插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

8.4 希尔排序（Shell Sort）

1959年Shell发明，第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

4.1 算法描述

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

• 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
• 按增量序列个数k，对序列进行k 趟排序；
• 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

希尔排序的组内排序为直接插入排序

4.2 动图演示

4.3 代码实现

// 修改于 2019-03-06
function shellSort(arr)
{
    var len = arr.length;
    for (var gap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2))
    { // 注意：这里和动图演示的不一样，动图是分组执行，实际操作是多个分组交替执行
        for (var i = gap; i < len; i++)
        {
            var j = i;
            var current = arr[i];
            while (j - gap >= 0 && current < arr[j - gap])
            {
                arr[j] = arr[j - gap];
                j = j - gap;
            }
            arr[j] = current;
        }
    }
    return arr;
}

4.4 算法分析

希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法（第4版）》的合著者Robert Sedgewick提出的。

8.5 归并排序（Merge Sort）

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

5.1 算法描述

• 把长度为n的输入序列分成两个长度为n/2的子序列；
• 对这两个子序列分别采用归并排序；
• 将两个排序好的子序列合并成一个最终的排序序列。

5.2 动图演示

5.3 代码实现

function mergeSort(arr) {
    var  len = arr.length;
    if(len < 2) {
        return  arr;
    }
    var  middle = Math.floor(len / 2),
        left = arr.slice(0, middle),
        right = arr.slice(middle);
    return  merge(mergeSort(left), mergeSort(right));
}
 
function merge(left, right) {
    var  result = [];
 
    while(left.length>0 && right.length>0) {
        if(left[0] <= right[0]) {
            result.push(left.shift());
        } else{
            result.push(right.shift());
        }
    }
 
    while(left.length)
        result.push(left.shift());
 
    while(right.length)
        result.push(right.shift());
 
    return  result;
}

5.4 算法分析

归并排序是一种稳定的排序方法。和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(nlogn）的时间复杂度。代价是需要额外的内存空间。

8.6 快速排序（Quick Sort）

快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

6.1 算法描述

快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：

• 从数列中挑出一个元素，称为 “基准”（pivot）；
• 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
• 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

就性能而言，快速排序最快

6.2 动图演示

6.3 代码实现

#include <stdio.h>
#include <stdlib.h>

void display(int array[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
}

int getStandard(int array[], int i, int j) {
    // 基准数据
    int key = array[i];
    while (i < j) {
        // 因为默认基准是从左边开始，所以从右边开始比较
        // 当队尾的元素大于等于基准数据 时,就一直向前挪动 j 指针
        while (i < j && array[j] >= key) {
            j--;
        }
        // 当找到比 array[i] 小的时，就把后面的值 array[j] 赋给它
        if (i < j) {
            array[i] = array[j];
        }
        // 当队首元素小于等于基准数据 时,就一直向后挪动 i 指针
        while (i < j && array[i] <= key) {
            i++;
        }
        // 当找到比 array[j] 大的时，就把前面的值 array[i] 赋给它
        if (i < j) {
            array[j] = array[i];
        }
    }
    // 跳出循环时 i 和 j 相等,此时的 i 或 j 就是 key 的正确索引位置
    // 把基准数据赋给正确位置
    array[i] = key;
    return  i;
}

void QuickSort(int array[], int low, int high) {
    //开始默认基准为 low
    if (low < high) {
        //分段位置下标
        int standard = getStandard(array, low, high);
        //递归调用排序
        //左边排序
        QuickSort(array, low, standard - 1);
        //右边排序
        QuickSort(array, standard + 1, high);
    }
}

// 合并到一起快速排序
// void QuickSort(int array[], int low, int high) {
//     int i   = low;
//     int j   = high;
//     int key = array[i];
//     if (low < high) {
//         while (i < j) {
//             while (i < j && array[j] >= key) {
//                 j--;
//             }
//             if (i < j) {
//                 array[i] = array[j];
//             }
//             while (i < j && array[i] <= key) {
//                 i++;
//             }
//             if (i < j) {
//                 array[j] = array[i];
//             }
//         }
//         array[i]     = key;
//         int standard = i;
//         QuickSort(array, low, standard - 1);
//         QuickSort(array, standard + 1, high);
//     }
// }

int main() {
    int array[] = {49, 38, 65, 97, 76, 13, 27, 49, 10};
    int size    = sizeof(array) / sizeof(int);
    printf("%d \n", size);
    QuickSort(array, 0, size - 1);
    display(array, size);

    // int size      = 20;
    // int array[20] = {0};                 // 数组初始化
    // for (int i = 0; i < 10; i++) {       // 数组个数
    //     for (int j = 0; j < size; j++) { // 数组大小
    //         array[j] = rand() % 1000;    // 随机生成数大小 0~99
    //     }
    //     printf("原来的数组：");
    //     display(array, size);
    //     QuickSort(array, 0, size - 1);
    //     printf("排序后数组：");
    //     display(array, size);
    //     printf("\n");
    // }

    return  0;
}

8.7 堆排序（Heap Sort）

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

7.1 算法描述

• 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
• 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
• 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

7.2 动图演示

7.3 代码实现

var  len;    // 因为声明的多个函数都需要数据长度，所以把len设置成为全局变量
 
function buildMaxHeap(arr) {   // 建立大顶堆
    len = arr.length;
    for(var i = Math.floor(len/2); i >= 0; i--) {
        heapify(arr, i);
    }
}
 
function heapify(arr, i) {     // 堆调整
    var  left = 2 * i + 1,
        right = 2 * i + 2,
        largest = i;
 
    if(left < len && arr[left] > arr[largest]) {
        largest = left;
    }
 
    if(right < len && arr[right] > arr[largest]) {
        largest = right;
    }
 
    if(largest != i) {
        swap(arr, i, largest);
        heapify(arr, largest);
    }
}
 
function swap(arr, i, j) {
    var  temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
 
function heapSort(arr) {
    buildMaxHeap(arr);
 
    for(var  i = arr.length - 1; i > 0; i--) {
        swap(arr, 0, i);
        len--;
        heapify(arr, 0);
    }
    return  arr;
}

*建堆，是从 $\sqrt{n}$ 开始的，然后不停的往上 heapify，所以i-- *

8.8 计数排序（Counting Sort）

计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

8.1 算法描述

• 找出待排序的数组中最大和最小的元素；
• 统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
• 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
• 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。

8.2 动图演示

8.3 代码实现

function countingSort(arr, maxValue) {
    var bucket = newArray(maxValue + 1),
        sortedIndex = 0;
        arrLen = arr.length,
        bucketLen = maxValue + 1;
 
    for(var i = 0; i < arrLen; i++) {
        if(!bucket[arr[i]]) {
            bucket[arr[i]] = 0;
        }
        bucket[arr[i]]++;
    }
 
    for(var j = 0; j < bucketLen; j++) {
        while(bucket[j] > 0) {
            arr[sortedIndex++] = j;
            bucket[j]--;
        }
    }
 
    return arr;
}

8.4 算法分析

计数排序是一个稳定的排序算法。当输入的元素是 n 个 0到 k 之间的整数时，时间复杂度是O(n+k)，空间复杂度也是O(n+k)，其排序速度快于任何比较排序算法。当k不是很大并且序列比较集中时，计数排序是一个很有效的排序算法。

8.9 桶排序（Bucket Sort）

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。

9.1 算法描述

• 设置一个定量的数组当作空桶；
• 遍历输入数据，并且把数据一个一个放到对应的桶里去；
• 对每个不是空的桶进行排序；
• 从不是空的桶里把排好序的数据拼接起来。

9.2 图片演示

9.3 代码实现

function bucketSort(arr, bucketSize) {
    if(arr.length === 0) {
      return arr;
    }
 
    var i;
    var minValue = arr[0];
    var maxValue = arr[0];
    for(i = 1; i < arr.length; i++) {
      if(arr[i] < minValue) {
          minValue = arr[i];                // 输入数据的最小值
      } elseif(arr[i] > maxValue) {
          maxValue = arr[i];                // 输入数据的最大值
      }
    }
 
    // 桶的初始化
    var DEFAULT_BUCKET_SIZE = 5;            // 设置桶的默认数量为5
    bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
    var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;  
    var buckets = newArray(bucketCount);
    for(i = 0; i < buckets.length; i++) {
        buckets[i] = [];
    }
 
    // 利用映射函数将数据分配到各个桶中
    for(i = 0; i < arr.length; i++) {
        buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
    }
 
    arr.length = 0;
    for(i = 0; i < buckets.length; i++) {
        insertionSort(buckets[i]);                      // 对每个桶进行排序，这里使用了插入排序
        for(var j = 0; j < buckets[i].length; j++) {
            arr.push(buckets[i][j]);                     
        }
    }
 
    return arr;
}

9.4 算法分析

桶排序最好情况下使用线性时间O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。

8.10 基数排序（Radix Sort）

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。

10.1 算法描述

• 取得数组中的最大数，并取得位数；
• arr为原始数组，从最低位开始取每个位组成radix数组；
• 对radix进行计数排序（利用计数排序适用于小范围数的特点）；

10.2 动图演示

10.3 代码实现

var counter = [];
function radixSort(arr, maxDigit) {
    var mod = 10;
    var dev = 1;
    for(var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
        for(var j = 0; j < arr.length; j++) {
            var bucket = parseInt((arr[j] % mod) / dev);
            if(counter[bucket]==null) {
                counter[bucket] = [];
            }
            counter[bucket].push(arr[j]);
        }
        var pos = 0;
        for(var j = 0; j < counter.length; j++) {
            var value = null;
            if(counter[j]!=null) {
                while((value = counter[j].shift()) != null) {
                      arr[pos++] = value;
                }
          }
        }
    }
    return arr;
}

10.4 算法分析

基数排序基于分别排序，分别收集，所以是稳定的。但基数排序的性能比桶排序要略差，每一次关键字的桶分配都需要O(n)的时间复杂度，而且分配之后得到新的关键字序列又需要O(n)的时间复杂度。假如待排数据可以分为d个关键字，则基数排序的时间复杂度将是O(d*2n) ，当然d要远远小于n，因此基本上还是线性级别的。

基数排序的空间复杂度为O(n+k)，其中k为桶的数量。一般来说n>>k，因此额外空间需要大概n个左右。

我们一般提到排序都是指内排序，比如快速排序，堆排序，归并排序等，所谓内排序就是可以在内存中完成的排序。RAM的访问速度大约是磁盘的25万倍，我们当然希望如果可以的话都是内排来完成。但对于大数据集来说，内存是远远不够的，这时候就涉及到外排序的知识了。

外部排序指的是大文件的排序，即待排序的记录存储在外存储器上，待排序的文件无法一次装入内存，需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目的。

8.11 多路归并排序

基本思想

外部排序最常用的算法是多路归并排序，即将原文件分解成多个能够一次性装人内存的部分，分别把每一部分调入内存完成排序。然后，对已经排序的子文件进行归并排序。

一般来说外排序分为两个步骤：预处理和合并排序。即首先根据内存的大小，将有n个记录的磁盘文件分批读入内存，采用有效的内存排序方法进行排序，将其预处理为若干个有序的子文件，这些有序子文件就是初始顺串，然后采用合并的方法将这些初始顺串逐趟合并成一个有序文件。

两两归并排序

假设有一个含10000 个记录的文件，首先通过10 次内部排序得到10 个初始归并段R1～R10 ，其中每一段都含1000 个记录。然后两两归并，直至得到一个有序文件为止

如R1与R2归并排序成R12，R3与R4排序成R34，再R12与R34排序从R1234

这种方法要归并排序多次，时间耗费多，不提倡

多路归并排序

由于多路归并，有k路，就要比较k-1次，所以有了减少比较次数的胜者树与败者树，而多路归并常用败者树

多路归并排序算法在常见数据结构书中都有涉及。从2路到多路（k路），增大k可以减少外存信息读写时间，但k个归并段中选取最小的记录需要比较k-1次， 为得到u个记录的一个有序段共需要(u-1)(k-1)次，若归并趟数为s次，那么对n个记录的文件进行外排时，内部归并过程中进行的总的比较次数为 s(n-1)(k-1)，也即(向上取整)(logkm)(k-1)(n-1)=(向上取整)(log2m/log2k)(k-1)(n-1)，而(k- 1)/log2k随k增而增因此内部归并时间随k增长而增长了，抵消了外存读写减少的时间，这样做不行，由此引出了“败者树”tree of loser的使用。在内部归并过程中利用败者树将k个归并段中选取最小记录比较的次数降为(向上取整)(log2k)次使总比较次数为(向上取整) (log2m)(n-1)，与k无关。

败者树是完全二叉树， 因此数据结构可以采用一维数组。其元素个数为k个叶子结点、k-1个比较结点、1个冠军结点共2k个。ls[0]为冠军结点，ls[1]--ls[k- 1]为比较结点，ls[k]--ls[2k-1]为叶子结点（同时用另外一个指针索引b[0]--b[k-1]指向）。另外bk为一个附加的辅助空间，不 属于败者树，初始化时存着MINKEY的值。

多路归并排序算法的过程大致为：

1）：首先将k个归并段中的首元素关键字依次存入b[0]--b[k-1]的叶子结点空间里，然后调用CreateLoserTree创建败者树，创建完毕之后最小的关键字下标（即所在归并段的序号）便被存入ls[0]中。然后不断循环：

2）把ls[0]所存最小关键字来自于哪个归并段的序号得到为q，将该归并段的首元素输出到有序归并段里，然后把下一个元素关键字放入上一个元素本来所 在的叶子结点b[q]中，调用Adjust顺着b[q]这个叶子结点往上调整败者树直到新的最小的关键字被选出来，其下标同样存在ls[0]中。循环这个 操作过程直至所有元素被写到有序归并段里。

伪代码如下：

 void Adjust(LoserTree &ls, int s)
/*从叶子结点b[s]到根结点的父结点ls[0]调整败者树*/
{  int t, temp;
   t=(s+K)/2;          /*t为b[s]的父结点在败者树中的下标，K是归并段的个数*/
   while(t>0)                         /*若没有到达树根，则继续*/
   {     if(b[s]>b[ls[t]])        /*与父结点指示的数据进行比较*/
               {  /*ls[t]记录败者所在的段号，s指示新的胜者，胜者将去参加更上一层的比较*/
                  temp=s;
                  s=ls[t];
                  ls[t]=temp; 
                }
           t=t/2;                     /*向树根退一层，找到父结点*/
   }
  ls[0]=s;                           /*ls[0]记录本趟最小关键字所在的段号*/
}
 
 
void K_merge( int ls[K])
/*ls[0]~ls[k-1]是败者树的内部比较结点。b[0]~b[k-1]分别存储k个初始归并段的当前记录*/
/*函数Get_next(i)用于从第i个归并段读取并返回当前记录*/
{   int b[K+1),i,q;
     for(i=0; i<K;i++)                
     {   b[i]=Get_next(i);           /*分别读取K个归并段的第一个关键字*/  } 
     b[K]=MINKEY;                        /*创建败者树*/
     for(i=0; i<K ; i++)                    /*设置ls中的败者初值*/
           ls[i]=K;
     for(i=K-1 ; i>=0 ; i--)                /*依次从b[K-1]……b[0]出发调整败者*/
          Adjust(ls , i);             /*败者树创建完毕，最小关键字序号存入ls[0]
     while(b[ls[0]] !=MAXKEY )
     {   q=ls[0];                        /*q为当前最小关键字所在的归并段*/
          prinftf("%d",b[q]);
          b[q]=Get_next(q);
          Adjust(ls,q);                /*q为调整败者树后，选择新的最小关键字*/
     }
} 

胜者树

胜者树的一个优点是，如果一个选手的值改变了，可以很容易地修改这棵胜者树。只需要沿着从该结点到根结点的路径修改这棵二叉树，而不必改变其他比赛的结果。

注意：方块，表示最底层要比较的东西，里面的值是要比较的数值，下面的是数值对应的index。

圆圈，表示节点与节点之间比较的结果，里面的值是比较后结果，对应的对象的index，这里是胜利的数的index，旁边的是这个圆圈对应的index。

Fig.1是一个胜者树的示例。规定数值小者胜。

\1. b3 PK b4，b3胜b4负，内部结点ls[4]的值为3；

\2. b3 PK b0，b3胜b0负，内部结点ls[2]的值为3；

\3. b1 PK b2，b1胜b2负，内部结点ls[3]的值为1；

\4. b3 PK b1，b3胜b1负，内部结点ls[1]的值为3。.

当叶子结点b3的值变为11时，重构的胜者树所示。

\1. b3 PK b4，b3胜b4负，内部结点ls[4]的值为3；

\2. b3 PK b0，b0胜b3负，内部结点ls[2]的值为0

\3. b1 PK b2，b1胜b2负，内部结点ls[3]的值为1；

\4. b0 PK b1，b1胜b0负，内部结点ls[1]的值为1。.

败者树

败者树是胜者树的一种变体。在败者树中，用父结点记录其左右子结点进行比赛的败者，而让胜者参加下一轮的比赛。败者树的根结点记录的是败者，需要加一个结点来记录整个比赛的胜利者。采用败者树可以简化重构的过程。

注意：方块，表示最底层要比较的东西，里面的值是要比较的数值，下面的是数值对应的index。

圆圈，表示节点与节点之间比较的结果，里面的值是比较后结果，对应的对象的index，这里是失败的数的index，旁边的是这个圆圈对应的index。

线段上的数字，表示线段下面的圆圈，对应的比较，胜利的数的index。

一棵败者树。规定数大者败。

\1. b3 PK b4，b3胜b4负，内部结点ls[4]的值为4；

\2. b3 PK b0，b3胜b0负，内部结点ls[2]的值为0；

\3. b1 PK b2，b1胜b2负，内部结点ls[3]的值为2；

\4. b3 PK b1，b3胜b1负，内部结点ls[1]的值为1；

\5. 在根结点ls[1]上又加了一个结点ls[0]=3，记录的最后的胜者。

败者树重构过程如下：

将新进入选择树的结点与其父结点进行比赛：将败者存放在父结点中；而胜者再与上一级的父结点比较。

比赛沿着到根结点的路径不断进行，直到ls[1]处。把败者存放在结点ls[1]中，胜者存放在ls[0]中。

图是当b3变为13时，败者树的重构图。

注意，**败者树的重构跟胜者树是不一样的，败者树的重构只需要与其父结点比较。**对照Fig. 3来看，b3与结点ls[4]的原值比较，ls[4]中存放的原值是结点4，即b3与b4比较，b3负b4胜，则修改ls[4]的值为结点3。同理，以此类推，沿着根结点不断比赛，直至结束。

由上可知，败者树简化了重构。败者树的重构只是与该结点的父结点的记录有关，而胜者树的重构还与该结点的兄弟结点有关。

算法的步骤是：每次从k个组中的首元素中选一个最小的数，加入到新组，这样每次都要比较k-1次，故

算法复杂度为O((n-1)*(k-1))，而如果使用败者树，可以在O(logk)的复杂度下得到最小的数，算法复杂

度将为O((n-1)*logk)， 对于外部排序这种数据量超大的排序来说，这是一个不小的提高。

败者树的建立与调整

败者树的java代码

package algorithm.sort.losertreeSort;
 
import java.awt.Adjustable;
import java.util.ArrayList;
import java.util.Arrays;
/* 
*/
import java.util.Iterator;
/**
 * @author xusy
 *
 */
import java.util.List;
public class LoserTree {
	
	//数据源，为叶子节点提供数据，iterator里的是有序的数据，从小到大
	private Iterator<Integer>[] data;
	
	//总共有几个数据源
	private int size;
	
	//叶子节点，数据源中具体的数据,一对一
	private Integer[] leaves;
	
	//非叶子节点,记录叶子节点的下标, 根据节点的值可以定位到叶子节点所指向的数据（就是图里画的败者树）
	//nodes[0]为最小值的索引
	private int[] nodes;
	
	/**根据data，构建败者树
	 * @param data  iterator里的是有序的数据，从小到大
	 */
	public LoserTree(List<Iterator<Integer>> data){
		//因为iterator不能变成迭代器数组，只能变成迭代器列表
		this.data=data.toArray(new Iterator[0]);
		size=data.size();
		leaves=new Integer[size];
		nodes=new int[size];
		
		//为叶子节点，leaves数组赋值
		for(int i=0;i<size;i++){
			setLeavesValueFromData(i);
		}
		
		//找到叶子节点中最小值的下标
		int winner=0;
		for(int i=1;i<size;i++){
			//如果i位元素比winner位元素小
			if(compareLeavesByIndex(i, winner)){
				winner=i;
			}
		}
		
		// 非叶子节点全部初始化为最小值对应的叶子节点下标
        Arrays.fill(nodes, winner);
		
        //从后向前依次调整非叶子节点
        for(int i=size-1;i>=0;i--){
        	adjust(i);
        }
		
	}
	
	/**根据数据源data，设置leaves[i]的值，如果对应的data没有值了，就设置null
	 * @param i 位置
	 */
	public void setLeavesValueFromData(int i){
		Iterator<Integer> iterator=data[i];
		if(iterator.hasNext()){
			leaves[i]=iterator.next();
		}
		else{
			leaves[i]=null;
		}		
	}
	
	/**比较leaves数组中位置为index1的元素是否小于index2的元素（因为是要得到小的）
	 * @param index1
	 * @param index2
	 * @return 
	 */
	public boolean compareLeavesByIndex(int index1,int index2){
		Integer value1=leaves[index1];
		Integer value2=leaves[index2];
		if(value1==null){
			return false;
		}
		if(value2==null){
			return true;
		}
		//当叶节点数据相等时比较分支索引是为了实现排序算法的稳定性
		if(value1==value2){
			return index1<index2;
		}
		if(value1<value2){
			return true;
		}
		else{
			return false;
		}
		
	}
	
	
	/**调整第index个叶子节点的值，在非叶子节点nodes（败者树）中的位置，最后nodes[0]为最小的节点
	 * 具体调整过程为: 叶子节点和父节点比较, 败者（较大值）留在父节点位置, 胜者（较小值）继续和祖父节点比较，直至最终
	 * @param index
	 */
	public void adjust(int index){
		int parent=(index+size)/2;
		//直到parent变成0
		while (parent>0) {
			//如果父节点小于当前值，败者为当前值，败者留在父亲节点，index变成父亲节点的值，相当于父亲节点与祖父节点继续比较
			//如果父节点大于当前值，败者为父节点，父节点不变，继续与祖父节点比较
			if(compareLeavesByIndex(nodes[parent], index)){
				int temp=nodes[parent];
				nodes[parent]=index;
				index=temp;				
			}
			//祖父节点的位置
			parent=parent/2;
			//一套流程下来，index成为胜者，小的
			//parent放置着败者，大的
			//parent最后成为下一个比较的节点（祖父节点）
		}
		//跳出循环后，index成为最小的节点
		nodes[0]=index;		
	}
	
	
	/**返回败者树中data，经过败者树，多路归并排序后的list
	 * @return
	 */
	public List<Integer> mergeSort(){
		List<Integer> list=new ArrayList<>();
		Integer smallest=null;
		while (true) {
			//得到最小值
			smallest=leaves[nodes[0]];
			if(smallest==null){
				break;
			}			
			list.add(smallest);
			//由于leaves数组中的最小值，索引为nodes[0]的元素被拿走了，所以要重新读入一个
			setLeavesValueFromData(nodes[0]);
			// 根据新插入的叶子节点重新调整树
			adjust(nodes[0]); 
		}		
		return list;
	}
	
}

测试

package algorithm.sort.losertreeSort;
 
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
 
public class Main {
	
	public static void main(String[] args) {
		//int[][] testTable = {{1,2,3,0},{1,2,3,4},{1,2567678,3,4,6767,45,12,345,3435,34,66666},
		//{1,1,1,3,3,4,3,2,4,2},{1,6,2,7,1}};
 
		List<Iterator<Integer>> list=new ArrayList<>();
		list.add(createRandomIntArray(-100,100,50));
		list.add(createRandomIntArray(-100,100,40));
		list.add(createRandomIntArray(-100,100,50));
		list.add(createRandomIntArray(-100,100,50));	
		test(list);
	}
		 
	private static void test(List<Iterator<Integer>> ito) {		
		//开始时打印数组
		long begin = System.currentTimeMillis();
		LoserTree tree=new LoserTree(ito);
		List<Integer> result=tree.mergeSort();
		long end = System.currentTimeMillis();	
		
		//System.out.println(ito + ": rtn=" +rtn);
		for (int i = 0; i < result.size(); i++) {
		    System.out.print(result.get(i)+" ");
		}//打印结果几数组
		
		System.out.println();
		System.out.println("耗时：" + (end - begin) + "ms");
		System.out.println("-------------------");
		System.out.println("-------------------");
	}
	public static Iterator<Integer> createRandomIntArray(int min,int max,int length){
		List<Integer> result=new ArrayList<>(length);
		for(int i=0;i<length;i++){
			double rand=Math.random();
			result.add((int)(min+(max-min)*rand));
		}
		Collections.sort(result);
		return result.iterator();
	}
 
}

败者树的效率

败者树可以在log(n)的时间内找到最值。任何一个叶子结点的值改变后，利用中间结点的信息，还是能够在log(n)的时间内找到最值。（n为多路归并的路数）

设，总共有k组，总共n个数据,每组n/k个

一开始对每组进行排序的时间是 k*log(n/k)n/k=nlog(n/k)

进行败者树归并排序的时间为n*log(k)

总共时间为n*(log(n/k)+log(k))=n*log(n) 也就是最好的速度,速度为O(n*log(n))

所需的空间为O(k)

9. VSCode问题

解决VSCode终端中文乱码问题

在终端输入chcp 65001