Java数据结构6（队列和二叉树初步）
目录
1，队列的性质
2，循环队列
3，队列链式存储
4，树的性质
5，二叉树的遍历
6，代码实现
一，队列的性质
同样是线性表，队列有线性表的相关操作，不过不同的是队列的性质为先进先出，类似为排队一样
队列的主要方法如下
| 方法 | 作用 | 特点 |
|---|---|---|
offer(E e) | 入队（添加元素到队尾） | 成功返回 true，失败返回 false（不抛异常） |
poll() | 出队（删除并返回队首元素） | 队列为空时返回null |
peek() | 查看队首元素（不删除） | 队列为空时返回null |
add(E e) | 入队 | 失败时直接抛出异常 |
remove() | 出队 |
队列为空时直接抛出异常 |
Queue<Integer> queue=new ArrayDeque<>();
queue.offer(1);
queue.offer(2);
queue.offer(3);
System.out.println(queue);
queue.poll();
System.out.println(queue);
System.out.println(queue.peek());
System.out.println(queue.isEmpty());
二，循环队列
因为队列顺序存储存在不足，当你出元素的时候是从头开始出，你的头就会顺着延续给下一个元素，头的指向就会不断往后走，所以你前面的位置就空出来了，会造成空间的浪费，所以我们可以使用循环的方式来实现空间的利用
类似这样的结构，当我们删除元素的时候，front往后走，rear也往后走，当我们加元素的时候，front和rear都往前走，当rear下下一个元素就是front的时候，我们就放满了，为什么这样就满了而不是放满呢，因为当放满的时候，rear就会和front重合，但是当一个元素没有的时候，rear和front也是重合的，就不太好区分，所以选择牺牲一个空间
在代码的实现中有几个注意的点（rear和front都是下标，capacity是总长度，比最多能放的元素多一）
1,队列满的条件是（rear+1）%capacity==front，也就是要rear的下一个元素是front，因为小%大=小，所以+1再%大就是rear+1，当这时候两者相等了，就可以说明满了
2，（rear+1）%capacity也是入队时的rear的循环语句
3，计算长度：在计算长度的时候会出现以下两种情况，第一种情况被分为了两部分，一个1和一个4，分别为rear+1（1）以及capacity-front（6-2），所以图一的个数为rear-front+capacity，图二就是rear-front（5-0），所以综合下来的公式就是（rear-front+capacity）%capacity
这样我们的代码就如下
public class CircleQueue {
private int arr[];
private int front;
private int rear;
private int capacity;
public CircleQueue(int maxSize) {
// maxSize为最多放的元素，预留一个空闲元素，所以+1
capacity = maxSize + 1;
arr = new int[capacity];
front = 0;
rear = 0;
}
public boolean isEmpty() {
return front == rear;
}
public boolean isFull() {
return (rear + 1) % capacity == front;
}
//入队，相当于offer
public void enQueue(int val){
if (isFull()){
return;
}
arr[rear]=val;
rear=(rear+1)%capacity;
}
//出队，相当于pop
public void deQueue(){
if (isEmpty()){
throw new RuntimeException("队列为空");
}
front=(front+1)%capacity;
}
//拿头元素，相当于peek
public int getFront(){
if (isEmpty()){
throw new RuntimeException("队列为空");
}
return arr[front];
}
//遍历
public void showQueue(){
if (isEmpty()) {
System.out.println("队列为空");
return;
}
// 从front开始遍历，遍历有效元素个数
for (int i = front; i != rear; i = (i + 1) % capacity) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
CircleQueue circleQueue=new CircleQueue(5);
circleQueue.enQueue(1);
circleQueue.enQueue(2);
circleQueue.enQueue(3);
circleQueue.enQueue(4);
circleQueue.enQueue(5);
circleQueue.showQueue();
circleQueue.deQueue();
circleQueue.showQueue();
System.out.println(circleQueue.getFront());
}
}
三，队列的链式存储
因为上面的方法会牺牲一个空间，并且规定了总空间，不够灵活，所以我们可以通过链式存储，也就是简单的单项链表，使用尾插法，并且删除时候是删除前面，以下是代码，和我前面一篇自己实现单项链表的文章内容差不多
public class Node {
static class ListNode {
public int val;
public ListNode prev;
public ListNode next;
public ListNode(int val) {
this.val = val;
}
}
public ListNode first;
public ListNode last;
//入队
public void offer(int val){
ListNode listNode=new ListNode(val);
if (first==null){
first=last=listNode;
}
last.next=listNode;
listNode.prev=last;
last=listNode;
}
//获取头元素并且删除
public int poll(){
if (first==null){
throw new RuntimeException("为空");
}
int val= first.val;
if (first==last){
first=null;
last=null;
}
first=first.next;
first.prev=null;
return val;
}
//获取头元素
public int peek(){
if (first==null){
throw new RuntimeException("为空");
}
return first.val;
}
public int size(){
ListNode cur=first;
int count=0;
while (cur!=null){
cur=cur.next;
count++;
}
return count;
}
public boolean empty(){
return first==null;
}
public void showQueue(Node node){
ListNode cur=first;
while (cur!=null){
System.out.print(cur.val+" ");
cur=cur.next;
}
System.out.println();
}
public static void main(String[] args) {
Node node=new Node();
node.offer(1);
node.offer(2);
node.offer(3);
System.out.println(node.peek());
node.showQueue(node);
node.poll();
node.showQueue(node);
}
}
四，树的相关性质
（1）、树的定义
树（Tree） 是n（n≥0）个结点的有限集合，满足：
- 若 n=0：称为空树；
- 若 n>0：
- 有且仅有一个根结点；
- 其余结点可分为互不相交的有限集合，每个集合本身又是一棵树，称为根的子树。
- 特点：层次结构、一对多；区别于线性表（一对一）、图（多对多）
我们根据上图来引出相关定义
结点的度：一个结点含有子树的个数，如上图：A的度为3；
树的度：一棵树中节点度的最大值，如上图：树的度为3；
叶子结点或终端结点：度为0的结点称为叶结点；
双亲结点或父结点：若一个结点含有子结点，那么称为这个子结点的父结点；
根结点：没有父结点的结点，图中为A;
结点的层次：从根开始定义，根为第一层，根的子结点为第二层；
树的高度：树中结点的最大层次，图中为4；
非终端结点：度不为0的结点；
二叉树
（1）、基本定义特点
- 每个节点最多有两个子节点，分别叫左孩子、右孩子。
- 子节点有左右次序，不能随意互换，是有序树。
- 可以是空二叉树；单个节点也是二叉树。
（2）、特殊二叉树特点
-
满二叉树每层节点都满，所有叶子在最底层，非叶子都有左右两个孩子。
-
完全二叉树除最后一层外，其余层节点全满；最后一层节点靠左连续排列。
- 叶子只出现在最下两层
- 度为 1 的节点最多只有 1 个
（3）、二叉树的性质
1，二叉树的第i层上至多有2^(i-1)个结点
2，如果有k层，二叉树至多有2^k-1个结点
3，对于任何一颗二叉树，如果终端结点树4为n0，度为2的结点数为n2，则n0=n2+1
4，具有n个结点的完全二叉树的深度为【log2n】+1
5，如果有n个结点的完全二叉树，对任意结点i有：
（1）如果i=1，则结点i是二叉树的根；如果i>1，则其双亲结点为i/2
（2）如果2i>n，则结点i无左孩子，否则其左孩子结点为2i
（3）如果2i+1>n，则结点i无右孩子，否则其右孩子结点为2i+1
以这个完全二叉树为例（上图为完全二叉树）
（1）1是其根结点，当i=3>1的时候，其双亲结点为3/2=1
（2）当i=6的时候，没有左孩子，当i=5，2i=10不大于n，左孩子结点为10
（3）当i=5的时候，没有右孩子，当i=3的时候右孩子为7
（4）、二叉树相关练习
1.某⼆叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该⼆叉树中的叶⼦结点数为（ ）
A 不存在这样的⼆叉树 B 200 C 198 D 199
2.在具有 2n 个结点的完全⼆叉树中，叶⼦结点个数为（ ）
A n B n+1 C n-1 D n/2
3.⼀个具有767个节点的完全⼆叉树，其叶⼦节点个数为（）
A 383 B 384 C 385 D 386
4.⼀棵完全⼆叉树的节点数为531个，那么这棵树的⾼度为（ ）
A 11 B 10 C 8 D 12
答案： 1.B 2.A 3.B 4.B
答：题1：根据性质3可知，n0=n2+1，所以叶子结点也就是n0，就等于200
题2：以上面图片的完全二叉树可以知道，当总结点数为偶数的时候，是有一个单独的左结点的，也就是有一个单独的度为1的结点，所以2n=1+n0+n2，然后又因为n0=n2+1,所以n0=n
题3：第3题也和第2题一样
题4：根据性质4可以计算出来，并且深度是要取大的
五，二叉树的遍历
（1）遍历方式：
二叉树的遍历主要是以前中后遍历（主要是看根的位置在哪）
前序遍历：根-->左-->右
中序遍历：左-->根-->右
后序遍历：左-->右-->根
在我们从根或者左右到达一个新的结点的时候，我们都要把它看成一个完整的二叉树来再看它的左右，就如同递归一样，我们还是以这一颗二叉树为例
前序遍历1 → 2 → 4 → 8 → 9 → 5 → 10 → 3 → 6 → 7
我们以前序遍历为例：先是根1，打印1，然后遍历1的左边，然后把左边看成新树，以此类推，打印2，打印4，打印8，然后就是4的右边，打印9，打印5，然后打印10，再到1的右边，打印3，打印6最后打印7
（2）例题：
设⼀课⼆叉树的中序遍历序列：badce，后序遍历序列：bdeca，则⼆叉树前序遍历序列为()
A: adbce B: decab C: debac D: abcde
答：根据后序遍历的特点，可以知道根为a，所以再根据中序遍历根在中间的特点，所以b在a的左边，dce在a的右边，然后单独看后续遍历中的dec，可以知道，dec这颗完整的树中，c是根，d是左，e是右，最终会如下图
六，代码实现
我们先纯手搓一个二叉树，二叉树还是这个图中的，代码如下
public class BinaryTree {
static class TreeNode{
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val) {
this.val = val;
}
}
public TreeNode CrateTree(){
TreeNode treeNode1=new TreeNode(1);
TreeNode treeNode2=new TreeNode(2);
TreeNode treeNode3=new TreeNode(3);
TreeNode treeNode4=new TreeNode(4);
TreeNode treeNode5=new TreeNode(5);
TreeNode treeNode6=new TreeNode(6);
TreeNode treeNode7=new TreeNode(7);
TreeNode treeNode8=new TreeNode(8);
TreeNode treeNode9=new TreeNode(9);
TreeNode treeNode10=new TreeNode(10);
treeNode1.left=treeNode2;
treeNode2.left=treeNode4;
treeNode4.left=treeNode8;
treeNode4.right=treeNode9;
treeNode2.right=treeNode5;
treeNode5.left=treeNode10;
treeNode1.right=treeNode3;
treeNode3.left=treeNode6;
treeNode3.right=treeNode7;
return treeNode1;
}
然后我们通过递归来实现前中后序遍历
public void preorder(TreeNode root){
if (root==null){
return;
}
System.out.print(root.val+" ");
preorder(root.left);
preorder(root.right);
}
//中
public void inorder(TreeNode root){
if (root==null){
return;
}
inorder(root.left);
System.out.print(root+" ");
inorder(root.right);
}
public void postorder(TreeNode root){
if (root==null){
return;
}
postorder(root.left);
postorder(root.right);
System.out.print(root+" ");
}
public class Test {
public static void main(String[] args) {
BinaryTree binaryTree=new BinaryTree();
BinaryTree.TreeNode ROOT=binaryTree.CrateTree();
binaryTree.preorder(ROOT);
}
}
更多推荐
12
0- 0
已为社区贡献2条内容
所有评论(0)