Java数据结构6（队列和二叉树初步）

目录1队列的性质2循环队列3队列链式存储4树的性质5二叉树的遍历6代码实现一队列的性质同样是线性表队列有线性表的相关操作不过不同的是队列的性质为先进先出类似为排队一样队列的主要方法如下方法作用特点offer(E e)入队添加元素到队尾成功返回 true失败返回 false不抛异常poll()出队删除并返回队首元素队列为空时返回nullpeek()查看队首元素不删除队列为空时返回nulladd(E e)入队失败时直接抛出异常remove()出队队列为空时直接抛出异常QueueInteger queuenew 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,队列满的条件是rear1%capacityfront也就是要rear的下一个元素是front因为小%大小所以1再%大就是rear1当这时候两者相等了就可以说明满了2rear1%capacity也是入队时的rear的循环语句3计算长度在计算长度的时候会出现以下两种情况第一种情况被分为了两部分一个1和一个4分别为rear11以及capacity-front6-2所以图一的个数为rear-frontcapacity图二就是rear-front5-0所以综合下来的公式就是rear-frontcapacity%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(rear1)%capacity; } //出队相当于pop public void deQueue(){ if (isEmpty()){ throw new RuntimeException(队列为空); } front(front1)%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 circleQueuenew 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 listNodenew ListNode(val); if (firstnull){ firstlastlistNode; } last.nextlistNode; listNode.prevlast; lastlistNode; } //获取头元素并且删除 public int poll(){ if (firstnull){ throw new RuntimeException(为空); } int val first.val; if (firstlast){ firstnull; lastnull; } firstfirst.next; first.prevnull; return val; } //获取头元素 public int peek(){ if (firstnull){ throw new RuntimeException(为空); } return first.val; } public int size(){ ListNode curfirst; int count0; while (cur!null){ curcur.next; count; } return count; } public boolean empty(){ return firstnull; } public void showQueue(Node node){ ListNode curfirst; while (cur!null){ System.out.print(cur.val ); curcur.next; } System.out.println(); } public static void main(String[] args) { Node nodenew 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是nn≥0个结点的有限集合满足若n0称为空树若n0有且仅有一个根结点其余结点可分为互不相交的有限集合每个集合本身又是一棵树称为根的子树。特点层次结构、一对多区别于线性表一对一、图多对多我们根据上图来引出相关定义结点的度一个结点含有子树的个数如上图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则n0n214具有n个结点的完全二叉树的深度为【log2n】15如果有n个结点的完全二叉树对任意结点i有1如果i1则结点i是二叉树的根如果i1则其双亲结点为i/22如果2in则结点i无左孩子否则其左孩子结点为2i3如果2i1n则结点i无右孩子否则其右孩子结点为2i1以这个完全二叉树为例上图为完全二叉树11是其根结点当i31的时候其双亲结点为3/212当i6的时候没有左孩子当i52i10不大于n左孩子结点为103当i5的时候没有右孩子当i3的时候右孩子为74、二叉树相关练习1.某⼆叉树共有 399 个结点其中有 199 个度为 2 的结点则该⼆叉树中的叶⼦结点数为 A 不存在这样的⼆叉树 B 200 C 198 D 1992.在具有 2n 个结点的完全⼆叉树中叶⼦结点个数为 A n B n1 C n-1 D n/23.⼀个具有767个节点的完全⼆叉树其叶⼦节点个数为A 383 B 384 C 385 D 3864.⼀棵完全⼆叉树的节点数为531个那么这棵树的⾼度为 A 11 B 10 C 8 D 12答案 1.B 2.A 3.B 4.B答题1根据性质3可知n0n21所以叶子结点也就是n0就等于200题2以上面图片的完全二叉树可以知道当总结点数为偶数的时候是有一个单独的左结点的也就是有一个单独的度为1的结点所以2n1n0n2然后又因为n0n21,所以n0n题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最后打印72例题设⼀课⼆叉树的中序遍历序列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 treeNode1new TreeNode(1); TreeNode treeNode2new TreeNode(2); TreeNode treeNode3new TreeNode(3); TreeNode treeNode4new TreeNode(4); TreeNode treeNode5new TreeNode(5); TreeNode treeNode6new TreeNode(6); TreeNode treeNode7new TreeNode(7); TreeNode treeNode8new TreeNode(8); TreeNode treeNode9new TreeNode(9); TreeNode treeNode10new TreeNode(10); treeNode1.lefttreeNode2; treeNode2.lefttreeNode4; treeNode4.lefttreeNode8; treeNode4.righttreeNode9; treeNode2.righttreeNode5; treeNode5.lefttreeNode10; treeNode1.righttreeNode3; treeNode3.lefttreeNode6; treeNode3.righttreeNode7; return treeNode1; }然后我们通过递归来实现前中后序遍历public void preorder(TreeNode root){ if (rootnull){ return; } System.out.print(root.val ); preorder(root.left); preorder(root.right); } //中 public void inorder(TreeNode root){ if (rootnull){ return; } inorder(root.left); System.out.print(root ); inorder(root.right); } public void postorder(TreeNode root){ if (rootnull){ return; } postorder(root.left); postorder(root.right); System.out.print(root ); }public class Test { public static void main(String[] args) { BinaryTree binaryTreenew BinaryTree(); BinaryTree.TreeNode ROOTbinaryTree.CrateTree(); binaryTree.preorder(ROOT); } }