学习数据结构（10）栈和队列下+二叉树（堆）上

1.关于栈和队列的算法题

（1）用队列实现栈

                                    

解法一：（参考代码）

题目要求实现六个函数，分别是栈初始化，入栈，移除并返回栈顶元素，返回栈顶元素，判空，栈的销毁

栈初始化：首先创建一个数据结构MyStack，包含两个队列q1,q2，先为Mystack申请内存空间，再调用队列初始化函数为q1,q2初始化

入栈：先判断q1队列是否为空，若为空，则将元素入队列q1,否则将元素入队列q2，即将元素入队列进不为空的队列中，但第一次入队列时，尽管q1,q2都为空，元素仍会入队列q2

移除并返回栈顶元素：将不为空队列中前Size-1个元素入队列进另一个为空的队列中，同时将前Size-1个元素从不为空队列中出队列，则原先不为空队列中只剩一个元素，取队头数据，再将此数据出队列，返回队头数据

返回栈顶元素：返回非空队列的队尾元素

判空：若同时满足队列q1为空和队列q2为空，则MyStack为空

栈的销毁：销毁队列q1和队列q2，释放MyStack的内存空间，将指针置空

（2）用栈实现队列

解法一：（参考代码）

题目要求实现的函数有六个，分别是初始化队列，入队列，从队列开头移除并返回元素，返回队头元素，判空，销毁队列

初始化队列：创建一个数据结构MyQueue，包含栈s1以及栈s2，先为MyQueue申请内存空间，再初始化s1,s2

入队列：规定入队列时，元素进入栈s1中，出队列时，元素从s2出。故调用函数入栈至s1

从队列开头移除并返回元素：若s2不为空，则从s2中出栈，否则先通过循环取s1中的栈顶元素，将s1中的元素全部入栈至s2，同时将s1中元素全部出栈，再从s2中取栈顶元素出栈，并返回此栈顶元素

返回队头元素：若s2不为空，则取s2栈顶元素并返回，否则将s1的全部元素出栈并入栈至s2，再取栈顶元素并返回

判空：当s1和s2都为空时，MyQueue为空

销毁队列：销毁s1，s2，再释放MyQueue的内存空间，将指针置空

2.二叉树

（1）树的概念

树是一种非线性的数据结构，它是由 n （ n>=0 ） 个有限节点组成的一个具有层次关系的集合

根结点：没有前驱节点的节点

除根结点外，其余结点被分成 M(M>0) 个互不相交的集合 T1 、 T2 、…… 、 Tm ，其中每⼀个集合 Ti(1 <= i <= m) 又是⼀棵结构与树类似的子树。每棵子树的根结点有且只有⼀个前驱，可以有 0 个或多个后继，因此，树是递归定义的

树形结构中，子树之间不能有交集，否则就不是树形结构，而是图结构

除了根结点外，每个结点有且仅有一个父结点

一棵N个结点的树有N-1条边

（2）相关术语

父节点/双亲节点：若一个节点含有子节点，则这个节点称为其子节点的父节点

子节点/孩子节点：一个节点含有的子树的根节点称为该节点的子节点

节点的度：一个节点有几个孩子，它的度就是多少

树的度：一棵树中，最大的节点的度称为树的度

叶子节点/终端节点：度为 0 的节点称为叶节点

分支节点/非终端节点：度不为 0 的节点

兄弟节点：具有相同父节点的节点互称为兄弟节点

节点的层次：从根开始定义起，根为第 1 层，根的子节点为第 2 层，以此类推

树的高度或深度：树中节点的最大层次

节点的祖先：从根到该节点所经分支上的所有节点

路径：一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列

子孙：以某节点为根的子树中任一节点都称为该节点的子孙

森林：由 m （ m>0 ） 棵互不相交的树组成的集合称为森林

（3）树的表示方法

树结构相对线性表就比较复杂，要存储表示起来比较麻烦，既要保存值，又要保存节点和节点之间的关系，实际上，树有很多种表示方式，如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等，其中最常用的为孩子兄弟表示法：

 struct TreeNode 
{ struct Node* child;   // 左边开始的第⼀个孩⼦结点struct Node* brother; // 指向其右边的下⼀个兄弟结点int data;             
};

（4）二叉树的概念

在树形结构中，最常用的就是二叉树，一棵二叉树是节点的一个有限集合，该集合由一个根节点 加上两棵别称为左子树和右子树的二叉树组成或者为空

二叉树不存在度大于 2 的节点

二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

（5）二叉树的种类

满二叉树：如果一个二叉树每一层的节点数都达到最大值，则这个二叉树就是满二叉树，也就是说，如果一个二叉树的层数为K ，且节点总数是2^k-1 ，则它就是满二叉树

完全二叉树：完全二叉树是效率很高的数据结构，对于深度为 K 的，有 n 个 结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从 1 至 n 的结点一一对应时称之为完全二叉树，要注意的是满二叉树是一种特殊的完全二叉树

（6）二叉树的性质

若规定节结点的层数为 1 ，则一棵非空二叉树的第i层上最多有2^(i-1)个节点

若规定根节点的层数为1，则深度为 h 的二叉树的最大节点数是2^h-1

若规定根节点的层数为 1 ，具有 n 个节点的满二叉树的深度h=log2(n+1)

（7）二叉树的储存结构

1>顺序结构

顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费，完全二叉树更适合使用顺序结构存储

         

实际上，通常把堆（一种二叉树）使同顺序结构的数组来存储

2>链式结构

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系，通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址