传媒公司网站如何建设手机版网站

当前位置： 首页 > news >正文

传媒公司网站,如何建设手机版网站,seo管理,wordpress怎么中文字体Java学习面试指南#xff1a;https://javaxiaobear.cn 1、树的相关概念 1、树的基本定义 树是我们计算机中非常重要的一种数据结构#xff0c;同时使用树这种数据结构#xff0c;可以描述现实生活中的很多事物#xff0c;例如家谱、单位的组织架构、等等。 树是由n#…Java学习面试指南https://javaxiaobear.cn 1、树的相关概念 1、树的基本定义 树是我们计算机中非常重要的一种数据结构同时使用树这种数据结构可以描述现实生活中的很多事物例如家谱、单位的组织架构、等等。 树是由nn1个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树也就是说它是根朝上而叶朝下的。 树具有以下特点 每个结点有零个或多个子结点没有父结点的结点为根结点每一个非根结点只有一个父结点每个结点及其后代结点整体上可以看做是一棵树称为当前结点的父结点的一个子树 2、相关术语 1、结点的度 一个结点含有的子树的个数称为该结点的度 2、叶子结点 度为0的结点称为叶结点也可以叫做终端结点 3、分支结点 度不为0的结点称为分支结点也可以叫做非终端结点 4、结点的层次 从根结点开始根结点的层次为1根的直接后继层次为2以此类推 5、结点的层序编号 将树中的结点按照从上层到下层同层从左到右的次序排成一个线性序列把他们编成连续的自然数。 6、树的度 树中所有结点的度的最大值 7、树的高度(深度) 树中结点的最大层次 8、森林 mm0个互不相交的树的集合将一颗非空树的根结点删去树就变成一个森林给森林增加一个统一的根结点森林就变成一棵树 9、孩子结点 一个结点的直接后继结点称为该结点的孩子结点 10、双亲结点(父结点) 一个结点的直接前驱称为该结点的双亲结点 11、兄弟结点 同一双亲结点的孩子结点间互称兄弟结点 2、二叉树 二叉树就是度不超过2的树(每个结点最多有两个子结点) 1、相关二叉树 1、满二叉树 一个二叉树如果每一个层的结点树都达到最大值则这个二叉树就是满二叉树。 2、完全二叉树 叶节点只能出现在最下层和次下层并且最下面一层的结点都集中在该层最左边的若干位置的二叉树 2、创建二叉查找树 1、API设计 结点类 类名NodeKey,Value构造方法Node(Key key, Value value, Node left, Node right)创建Node对象成员变量1.public Node left:记录左子结点2.public Node right:记录右子结点3.public Key key:存储键4.public Value value:存储值 二叉树 类名BinaryTreeKey,value构造方法BinaryTree()创建BinaryTree对象成员变量1.private Node root:记录根结点2.private int N:记录树中元素的个数成员方法1. public void put(Key key,Value value):向树中插入一个键值对2.private Node put(Node x, Key key, Value val)给指定树x上添加键一个键值对并返回添加后的新树3.public Value get(Key key):根据key从树中找出对应的值4.private Value get(Node x, Key key):从指定的树x中找出key对应的值5.public void delete(Key key):根据key删除树中对应的键值对6.private Node delete(Node x, Key key):删除指定树x上的键为key的键值对并返回删除后的新树7.public int size():获取树中元素的个数 1、put方法实现思路 如果当前树中没有任何一个结点则直接把新结点当做根结点使用 如果当前树不为空则从根结点开始 如果新结点的key小于当前结点的key则继续找当前结点的左子结点 如果新结点的key大于当前结点的key则继续找当前结点的右子结点 如果新结点的key等于当前结点的key则树中已经存在这样的结点替换该结点的value值即可。 /*** 给指定树x上添加键一个键值对并返回添加后的新树* param x 树节点* param key 键* param val 值* return Node/ public NodeKey, Value put(NodeKey,Value x, Key key, Value val){//当树为空时该节点为根节点if(null x){size;return new Node(key, val, null, null);}int compare key.compareTo(x.key);//如果compare 0 ,则 key x.key;继续x的右子节点if(0 compare){x.right put(x.right,key,val);}else if(0 compare){//如果compare 0 ,则 key x.key;继续x的左子节点x.left put(x.left,key,val);}else {//如果compare 0 ,则 key x.key;替换x.value的值x.value val;}return x; }2、get方法实现思路 从根节点开始 如果要查询的key小于当前结点的key则继续找当前结点的左子结点如果要查询的key大于当前结点的key则继续找当前结点的右子结点如果要查询的key等于当前结点的key则树中返回当前结点的value。 /** 从指定的树x中找出key对应的值* param x 节点* param key 键* return 节点/ public Value getNode(NodeKey,Value x, Key key){if (null x){return null;}int compare key.compareTo(x.key);if(0 compare){return getNode(x.right,key);}else if(0 compare){return getNode(x.left, key);}else {return x.value;} }3、delete方法的实现思路 找到被删除结点找到被删除结点右子树中的最小结点minNode删除右子树中的最小结点让被删除结点的左子树称为最小结点minNode的左子树让被删除结点的右子树称为最小结点minNode的右子树让被删除结点的父节点指向最小结点minNode /** 删除指定树x中的key对应的value并返回删除后的新树* param x* param key* return/ public NodeKey,Value delete(NodeKey, Value x, Key key){if (null x){return null;}int compare key.compareTo(x.key);if(0 compare){x.right delete(x.right,key);}else if(0 compare){x.left delete(x.left,key);}else {//个数-1size–;//新结点的key等于当前结点的key,当前x就是要删除的结点if(x.right null){return x.left;}if(x.left null){return x.right;}//左右子结点都存在的情况下找右子树最小的节点NodeKey, Value minRight x.right;while (null ! minRight.left){minRight minRight.left;}NodeKey, Value node x.right;while (node.left ! null) {if (node.left.left null) {node.left null;} else {node node.left;}}//让被删除结点的左子树称为最小结点minNode的左子树让被删除结点的右子树称为最小结点minNode的右子树minRight.left x.left;minRight.right x.right;//让被删除结点的父节点指向最小结点minNodex minRight;}return x; }4、完整代码 package com.xiaobear.BinaryTree;/** Author xiaobear* date 2021年07月30日 13:50* Description 二叉树/ public class BinaryTreeKey extends ComparableKey,Value {/** 根节点/private NodeKey,Value root;/** 节点数量/private int size;public void put(Key key, Value val){root put(root,key,val);}/** 给指定树x上添加键一个键值对并返回添加后的新树* param x 树节点* param key 键* param val 值* return Node/public NodeKey, Value put(NodeKey,Value x, Key key, Value val){//当树为空时该节点为根节点if(null x){size;return new Node(key, val, null, null);}int compare key.compareTo(x.key);//如果compare 0 ,则 key x.key;继续x的右子节点if(0 compare){x.right put(x.right,key,val);}else if(0 compare){//如果compare 0 ,则 key x.key;继续x的左子节点x.left put(x.left,key,val);}else {//如果compare 0 ,则 key x.key;替换x.value的值x.value val;}return x;}/** 根据key从树中找出对应的值* param key 键/public Value getNode(Key key){return getNode(root,key);}/** 从指定的树x中找出key对应的值* param x 节点* param key 键* return 节点/public Value getNode(NodeKey,Value x, Key key){if (null x){return null;}int compare key.compareTo(x.key);if(0 compare){return getNode(x.right,key);}else if(0 compare){return getNode(x.left, key);}else {return x.value;}}public void delete(Key key){root delete(root, key);}/** 删除指定树x中的key对应的value并返回删除后的新树* param x* param key* return/public NodeKey,Value delete(NodeKey, Value x, Key key){if (null x){return null;}int compare key.compareTo(x.key);if(0 compare){x.right delete(x.right,key);}else if(0 compare){x.left delete(x.left,key);}else {//个数-1size–;//新结点的key等于当前结点的key,当前x就是要删除的结点if(x.right null){return x.left;}if(x.left null){return x.right;}//左右子结点都存在的情况下找右子树最小的节点NodeKey, Value minRight x.right;while (null ! minRight.left){minRight minRight.left;}NodeKey, Value node x.right;while (node.left ! null) {if (node.left.left null) {node.left null;} else {node node.left;}}//让被删除结点的左子树称为最小结点minNode的左子树让被删除结点的右子树称为最小结点minNode的右子树minRight.left x.left;minRight.right x.right;//让被删除结点的父节点指向最小结点minNodex minRight;}return x;}public int size(){return size;}/** 节点类* param Key* param Value/private class NodeKey,Value{public Key key;public Value value;public NodeKey,Value left;public NodeKey, Value right;public Node(Key key, Value value, Node left, NodeKey, Value right) {this.key key;this.value value;this.left left;this.right right;}} }测试代码 public class BinaryTreeTest {public static void main(String[] args) {BinaryTreeInteger, String binaryTree new BinaryTree();binaryTree.put(1,yhx);binaryTree.put(2,love);binaryTree.put(3,lwh);System.out.println(binaryTree.size());binaryTree.delete(2);String node binaryTree.getNode(2);System.out.println(node);System.out.println(binaryTree.size());} }3、查找二叉树中最大/最小的键 1、最小的键 方法描述public Key min()找出树中最小的键private Node min(Node x)找出指定树x中最小键所在的结点 /** 查找树中最小的键* return/ public Key minKey(){return minKey(root).key; }/** 根据二叉树的特点左子树 右子树 so最小的键肯定是位于左边* param x* return/ public NodeKey,Value minKey(NodeKey,Value x){if (x.left ! null){return minKey(x.left);}else {return x;} }2、最大的键 方法描述public Key max()找出树中最大的键public Node max(Node x)找出指定树x中最大键所在的结点 /** 查询树中最大的键* return/public Key maxKey(){return maxKey(root).key;}/** 根据二叉树的特点右子树 左子树 so最大的键肯定是位于右边* param x* return/public NodeKey,Value maxKey(NodeKey,Value x){if(x.right ! null){return maxKey(x.right);}else {return x;}}3、二叉树的遍历 我们把树简单的画作上图中的样子由一个根节点、一个左子树、一个右子树组成那么按照根节点什么时候被访 问我们可以把二叉树的遍历分为以下三种方式 前序遍历 先访问根结点然后再访问左子树最后访问右子树 中序遍历 先访问左子树中间访问根节点最后访问右子树 后序遍历 先访问左子树再访问右子树最后访问根节点
1、前序遍历 前序遍历的API 方法描述public Queue preErgodic()使用前序遍历获取整个树中的所有键private void preErgodic(Node x,Queue keys)使用前序遍历把指定树x中的所有键放入到keys队列中 /** 前序遍历* return/ public QueueKey preErgodic(){QueueKey queue new Queue();preErgodic(root,queue);return queue; }/** 前序遍历操作 先访问根结点然后再访问左子树最后访问右子树* param x 根节点* param queue 队列/ private void preErgodic(NodeKey,Value x, QueueKey queue){if (x null) {return;}//把当前结点的key放入到队列中queue.enqueue(x.key);//访问左子树if(x.left ! null){preErgodic(x.left,queue);}//访问右子树if(x.right ! null){preErgodic(x.right,queue);} }2、中序遍历 中序遍历的API 方法描述public Queue midErgodic()使用中序遍历获取整个树中的所有键private void midErgodic(Node x,Queue keys)使用中序遍历把指定树x中的所有键放入到keys队列中 /** 中序遍历* return/public QueueKey midErgodic(){QueueKey queue new Queue();midErgodic(root,queue);return queue;}/** 先访问左子树中间访问根节点最后访问右子树* param x* param queue/private void midErgodic(NodeKey,Value x, QueueKey queue){if (x null) {return;}//访问左子树if(x.left ! null){preErgodic(x.left,queue);}//把当前结点的key放入到队列中queue.enqueue(x.key);//访问右子树if(x.right ! null){preErgodic(x.right,queue);}}3、后序遍历 后序遍历的API 方法描述public Queue afterErgodic()使用后序遍历获取整个树中的所有键private void afterErgodic(Node x,Queue keys)使用后序遍历把指定树x中的所有键放入到keys队列中 /** 后序遍历* return/public QueueKey afterErgodic(){QueueKey queue new Queue();afterErgodic(root,queue);return queue;}/** 先访问左子树再访问右子树最后访问根节点* param x* param queue/private void afterErgodic(NodeKey,Value x, QueueKey queue){if (x null) {return;}//访问左子树if(x.left ! null){preErgodic(x.left,queue);}//访问右子树if(x.right ! null){preErgodic(x.right,queue);}//把当前结点的key放入到队列中queue.enqueue(x.key);}4、测试 public class BinaryTreeErgodicTest {public static void main(String[] args) {BinaryTreeString, String bt new BinaryTree();bt.put(E, 5);bt.put(B, 2);bt.put(G, 7);bt.put(A, 1);bt.put(D, 4);bt.put(F, 6);bt.put(H, 8);bt.put(C, 3);//前序遍历QueueString preErgodic bt.preErgodic();//中序遍历QueueString midErgodic bt.midErgodic();//后序遍历QueueString afterErgodic bt.afterErgodic();for (String key : preErgodic) {System.out.println(key bt.getNode(key));}} }4、层次遍历 所谓的层序遍历就是从根节点第一层开始依次向下获取每一层所有结点的值 层次遍历的结果是EBGADFHC 方法描述public Queue layerErgodic()使用层序遍历获取整个树中的所有键实 实现步骤 创建队列存储每一层的结点使用循环从队列中弹出一个结点 获取当前结点的key如果当前结点的左子结点不为空则把左子结点放入到队列中如果当前结点的右子结点不为空则把右子结点放入到队列中
/** 层次遍历* return/ public QueueKey layerErgodic(){//存储keyQueueKey keys new Queue();//存储nodeQueueNodeKey,Value nodes new Queue();//入队头结点nodes.enqueue(root);while(!nodes.isEmpty()){//出队当前节点NodeKey,Value dequeue nodes.dequeue();//当前节点头入队keys.enqueue(dequeue.key);if(dequeue.left ! null){nodes.enqueue(dequeue.left);}if(dequeue.right ! null){nodes.enqueue(dequeue.right);}}return keys; }5、二叉树的最大深度 最大深度树的根节点到最远叶子结点的最长路径上的结点数 上面这颗树的最大深度为E–B–D–C深度为4 方法描述public int maxDepth()计算整棵树的最大深度private int maxDepth(Node x)计算指定树x的最大深度 实现步骤 如果根结点为空则最大深度为0计算左子树的最大深度计算右子树的最大深度当前树的最大深度左子树的最大深度和右子树的最大深度中的较大者1 /** 计算整棵树的最大深度* return/public int maxDepth(){return maxDepth(root);}/** 计算指定节点的最大深度* param x* return/private int maxDepth(NodeKey,Value x){if (x null) {return 0;}int maxRight 0;int maxLeft 0;int maxDepth;if(x.left ! null){maxLeft maxDepth(x.left);}if (x.right ! null) {maxRight maxDepth(x.right);}maxDepth maxLeft maxRight ? maxLeft 1 : maxRight 1;return maxDepth;}6、折纸问题 请把一段纸条竖着放在桌子上然后从纸条的下边向上方对折1次压出折痕后展开。此时 折痕是凹下去的即折痕突起的方向指向纸条的背面。如果从纸条的下边向上方连续对折2 次压出折痕后展开此时有三条折痕从上到下依次是下折痕、下折痕和上折痕。 给定一 个输入参数N代表纸条都从下边向上方连续对折N次请从上到下打印所有折痕的方向 例如N1时打印 downN2时打印 down down up 分析 我们把对折后的纸张翻过来让粉色朝下这时把第一次对折产生的折痕看做是根结点那第二次对折产生的下折痕就是该结点的左子结点而第二次对折产生的上折痕就是该结点的右子结点这样我们就可以使用树型数据结构来描述对折后产生的折痕。 这棵树有这样的特点 根结点为下折痕每一个结点的左子结点为下折痕每一个结点的右子结点为上折痕 实现步骤 构建节点类构建深度为n的折痕树使用中序遍历打印树中所有节点的内容 构建深度为N的折痕树 第一次对折只有一条折痕创建根节点如果不是第一次对折则使用队列保存根节点循环遍历队列 从队列中拿出一个节点如果当前节点的左节点不为空则把这个左节点加入队列中如果当前节点的右节点不为空则把这个右节点加入队列中判断当前结点的左子结点和右子结点都为空如果是则需要为当前结点创建一个值为down的左子结点一个值为up的右子结点。
public class PaperFolding {/** 创建折痕树* param size 深度/public static Node createTree(int size){Node root null;for (int i 0; i size; i) {//第一次对折只有一条折痕创建根节点if (0 i){root new Node(down,null,null);}else {//如果不是第一次对折则使用队列保存根节点QueueNode nodes new Queue();nodes.enqueue(root);//循环遍历while(!nodes.isEmpty()){//从队列中拿出一个节点Node dequeue nodes.dequeue();//如果当前节点的左节点不为空则把这个左节点加入队列中if(dequeue.left ! null){nodes.enqueue(dequeue.left);}//如果当前节点的右节点不为空则把这个右节点加入队列中if(dequeue.right ! null){nodes.enqueue(dequeue.right);}//判断当前结点的左子结点和右子结点都为空则需要为当前结点创建一个值为down的左子结点一个值为up的右子结点。if(dequeue.left null dequeue.right null){dequeue.left new Node(down,null,null);dequeue.right new Node(up,null,null);}}}}return root;}/** 采用中序遍历* param root/public static void printTree(Node root){if (root null) {return;}printTree(root.left);System.out.print(root.item );printTree(root.right);}/** 节点类*/private static class Node{String item;Node left;Node right;public Node(String item, Node left, Node right) {this.item item;this.left left;this.right right;}}public static void main(String[] args) {Node tree createTree(2);printTree(tree);} }down down up