企业网站推广工具,做彩票网站代理,wordpress 简历主题,微信服务号可以做万网站么1. 二叉树入门
符号表的增删查改操作#xff0c;随着元素个数N的增多#xff0c;其耗时也是线性增多的。时间复杂度都是O(n)#xff0c;为了提高运算效率#xff0c;下面将学习 树 这种数据结构
1.1 树的基本定义
树是我们计算机中非常重要的一种数据结构#xf…1. 二叉树入门
符号表的增删查改操作随着元素个数N的增多其耗时也是线性增多的。时间复杂度都是O(n)为了提高运算效率下面将学习 树 这种数据结构
1.1 树的基本定义
树是我们计算机中非常重要的一种数据结构同时使用树这种数据结构可以描述现实生活中的很多事务例如家谱、单位的组织架构等等
树是由n(n1)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像是一颗倒挂的树也就是说它是根朝上而叶是朝下的 树具有以下特点 每个节点有零个或多个子节点没有父节点的节点为根节点每一个非根节点只有一个父节点每个节点及其后代节点整体上可以看作是一棵树称为当前节点的父节点的一个子树。
1.2 树的相关术语
节点的度
一个节点含有的子树的个数称为该节点的度
叶节点
度为0的节点称为叶节点也可以叫做终端节点
分支节点
度不为0的节点称为分支节点也可以叫做非终端节点
节点的层次
从根节点开始根节点的层次为1根的直接后继层次为2依次类推
节点的层序编号
将树种的节点按照从上层到下层同层从左到右的次序排成一个线性序列把他们编成连续的自然数
树的度
树种所有节点的度的最大值
树的高度深度
树种节点的最大层次
森林 m(m0)个互不相交的树的集合将一颗非空树的根节点删除树就变成了一个森林给森林增加一个统一的根节点森林就变成了一棵树
孩子节点
一个节点的直接后继节点称为该节点的孩子节点
双亲节点父节点
一个节点的直接前驱称为该节点的双亲节点
兄弟节点
同一双亲节点的孩子节点间互称兄弟节点
1.3 二叉树的基本定义
二叉树就是度不超过2的树每个节点最多有两个子节点 满二叉树
一个二叉树如果每一层的节点数都达到最大值那么这个二叉树就是满二叉树2^k-1 完全二叉树
叶节点只能出现在最下层和次下层并且最下面一层的节点但都集中在该层最左边的若干位置的二叉树 2. 二叉查找树的创建
2.1 二叉树的节点类
根据对图的观察我们发现二叉树其实就是由一个一个的节点及其之间的关系组成的按照面向对象的思想我们设计一个系欸但来描述系欸但那这个事物
类名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存储值
2.2 二叉查找树API设计
类名BinaryTreeKey extends Comparable,Value value构造方法BinaryTree()创建BinaryTree对象成员变量1. private Node root记录根节点2. private int N记录树中元素的个数成员方法1. public void put(Key key,Value value)向树种插入一个键值对2. public Node put(Node x,Key key,Value value)给指定树x上
2.3 二叉查找树的实现
2.3.1 插入方法put实现思想
如果当前树种没有任何一个节点则直接把新节点当作根节点使用如果当前树不为空则从根节点开始 如果新节点的key小于当前节点的key则继续找当前节点的左子节点如果新节点的key大于当前节点的key则继续找当前节点的右子节点如果新节点的key等于当前节点的key则树种已经存在这样的节点替换掉该节点的value值。 2.3.2 查找方法get的实现思想 从根节点开始 如果新节点的key小于当前节点的key则继续找当前节点的左子节点如果新节点的key大于当前节点的key则继续找当前节点的右子节点如果新节点的key等于当前节点的key则数中返回当前节点的value
2.3.3 删除方法delete实现思想
找到被删除的节点找到被删除节点右子数的最小节点删除右子数中的最小节点让被删除节点的左子树成为最小节点的左子树让被删除节点的右子数成为最小节点的右子树让被删除节点的父节点指向最小节点 2.4 二叉查找树源码
package com.renexdemo.tree;// 二叉查找树
public class BinaryTreeKey extends ComparableKey ,Value {private Node root;// 根节点private int N;// 节点类private class Node{public Key key;public Value value;public Node left;public Node right;public Node(Key key, Value value, Node left, Node right) {this.key key;this.value value;this.left left;this.right right;}}public int size(){return N;}/*** 例如 key1 value张三 rootnull node1* key2 value李四 rootnode1node2* node1——key12李四 node1.left node2* tree —— 1_张三** key3 value王五 rootnode1 root.rightnode2** param key* param value*/// 向树中添加元素public void put(Key key, Value value){// node12李四// node13王五root put(root, key, value);}// 向某个树添加元素public Node put(Node x,Key key, Value value){// 如果x为空if (xnull){N;return new Node(key,value,null,null);}// 如果x不为空// 比较x节点的键和key的大小int cmp key.compareTo(x.key);if (cmp0){// x.right null2李四// 如果子树的键要大于key则继续找x节点的右子树x.right put(x.right,key,value);// x.right —— node2// 经过回调重新赋予了子树节点// x.rightnode2key2 value李四// 再次调用直到找到子树为null重新赋予该子树的节点键和值}else if (cmp0){// 如果子树的键要小于key则继续找x节点的左子树x.left put(x.left,key,value);}else {// 如果子树的键要等于key则替换valuex.value value;}return x;}// 根据对应的key查找到对应的值public Value get(Key key){return get(root,key);}public Value get(Node x,Key key){// x为nullif (xnull){return null;}else {// x不为null// 比较键的大小int cmp key.compareTo(x.key);if (cmp0){// 如果子树的键要大于key则继续找x节点的右子树return get(x.right,key);}else if (cmp0){// 如果子树的键要小于key则继续找x节点的左子树return get(x.left,key);}else {// 如果子树的键要等于key则替换valuereturn x.value;}}}// 删除树种key对应的valuepublic void delete(Key key){delete(root,key);}public Node delete(Node x,Key key){// 1 找到被删除的节点if (xnull){// 1.1 x树为nullreturn null;}// 1.2 x树不为nullint cmp key.compareTo(x.key);if (cmp0){// 1.2.1 如果子树的键要大于key则继续找x节点的右子树x.right delete(x.right,key);}else if (cmp0){// 1.2.2 如果子树的键要小于key则继续找x节点的左子树x.left delete(x.left,key);}else {// 2 删除x节点的键完成真正的删除操作// 6 元素个数-1N--;// 2.1 找到右子数中最小的节点if (x.right null){return x.left;}// 2.2 找到左子树中最大节点if (x.left null){return x.right;}// 2.3 找到最小节点Node minNode x.right;while (minNode.left ! null){minNode minNode.left;}// 2.4 删除右子数中最小的节点Node n x.right;while (n.left ! null){if (n.left.leftnull){n.left null;}else{n n.left;}}// 3 让x节点的左子树成为minNode的左子树minNode.left x.left;// 4 让x节点的右子树成为minNode的右子树minNode.right x.right;// 5 让x节点的父节点指向minNodex minNode;}return x;}// 查找整个树种最小的键public Key min(){return min(root).key;}// 在指定树中找出最小键所在的节点public Node min(Node x){if (x.left ! null){return min(x.left);}else {return x;}}// 查找整个树种最大的键public Key max(){return min(root).key;}// 在指定树中找出最大键所在的节点public Node max(Node x){if (x.right ! null){return min(x.right);}else {return x;}}}2.5 二叉查找树其他便捷方法
2.5.1 查找二叉树中最小的键
在某些情况下我们需要查找出树中存储所有元素的键的最小值。
方法说明public Key min()找出树中最小的键public Node min(Node x)找出指定树x中最小键所在的节点
2.5.2 查找二叉树中最大的键
在某些情况下我们需要查找出树中存储所有元素的键的最小值。
方法说明public Key max()找出树中最大的键public Node max(Node x)找出指定树x中最大键所在的节点
2.6 二叉树的基础遍历
很多情况下我们可能需要像遍历数组一样遍历树从而拿到数中存储的每一个元素由于树状结构和线性结构不一样它没有办法从头开始依次向后遍历所以存在如何遍历也就是按照什么样的搜索路径进行遍历的问题。 我们把树简单的画作上图中的样子由一个根节点一个左子数一个右子树组成那么按照根节点什么时候被访问我们可以把二叉树的遍历分为以下三种方式 前序遍历 先访问根节点如何再访问左子树最后访问右子树 中序遍历 先访问左子树中间访问根节点最后访问右子树 后续遍历 先访问左子树再访问右子树最后访问根节点
如果我们分别对下面的树使用三种遍历方式进行遍历得到结果如下 2.6.1 前序遍历
我们在4.4中创建的树上添加前序遍历的API
方法说明public Queue preErgodic()使用前序遍历获取整个树中的所有键public void preErgodic(Node x,Queue keys)使用前序遍历把指定树x中的所有键放入到keys队列中
实现过程中我们通过前序遍历把每个节点的键取出放入到队列中返回即可
2.6.1.1实现步骤
把当前节点的key放入到队列中找到当前节点的左子树如果不为空递归遍历左子树找到当前节点的右子树如果不为空递归遍历右子树
2.6.2 中序遍历
我们在4.4中创建的树上添加中序遍历的API
方法说明public Queue midErgodic()使用中序遍历获取整个树中的所有键public void midErgodic(Node x,Queue keys)使用中序遍历把指定树x中的所有键放入到keys队列中
2.6.2.1实现步骤
找到当前节点的左子树如果不为空递归遍历左子树把当前节点的key放入到队列中找到当前节点的右子树如果不为空递归遍历右子树
2.6.3 后序遍历
我们在4.4中创建的树上添加后序遍历的API
方法说明public Queue afterErgodic()使用后序遍历获取整个树中的所有键public void afterErgodic(Node x,Queue keys)使用后序遍历把指定树x中的所有键放入到keys队列中
2.6.2.1实现步骤
找到当前节点的左子树如果不为空递归遍历左子树找到当前节点的右子树如果不为空递归遍历右子树把当前节点的key放入到队列中
2.7 二叉树的层序遍历
所谓的层序遍历就是从根节点第一层开始依次往下获取每一层的所有节点的值有二叉树如下 那么层序遍历的结果是EBGADFHC
我们在4.4中创建的树上添加层序遍历的API
方法说明public Queue layerErgodic()使用层序遍历获取整个数中的所有键
2.7.1 实现步骤
创建队列存储每一层的节点使用循环从队列中弹出一个节点 获取当前节点的key如果当前节点的左子节点不为空则把左子节点放入到队列中如果当前节点的右子节点不为空则把右子节点放入到队列中 2.8 二叉树的最大深度
需求
给定一棵树请计算树的最大深度树的最远叶子节点的最长路径上的节点数 上面这棵树的最大深度为4
实现
在原有API的基础上添加如下API求最大深度
方法说明public int maxDepth()计算整个树的最大深度private int maxDepth(Node x)计算指 定树x的最大深度
实现步骤
如果根节点为空则最大深度为0计算左子树的最大深度计算右子树最大深度当前树的最大深度左子树的最大深度和右子树的最大深度中的较大者1
3. 折纸问题
需求:
请把一段纸条竖着放在桌子上如何从纸条的下边向上方对折1次压出折痕后展开。此时折痕是凹下去的即折痕突起的方向指向纸条的背面。
如果纸条的下边向上方连续对着2次压出折痕后展开此时有三条折痕从上到下依次是下折痕、下折痕和上折痕。
给定一个输入参数N代表纸条都从下边向上方连续对着N次请从上到下打印所有折痕的方向例如N1时打印downN2时打印down down up 如图粉色为正面黑色为背面。向粉色面折一次代表down向黑色面折一次代表up
分析
我们把对着后的纸张翻过来让粉色朝下这时把第一次对着产生的折痕看作是根节点那第二次对着产生的下折痕就是该节点的左子节点而第二次对着产生的折痕就是该节点的右子节点这样我们就可以使用数据结构来描述对着后产生的折痕。
这棵树有这样的特点 根节点为下折痕每一个节点的左子节点为下折痕每一个节点的右子节点为上折痕 实现步骤
定义节点类构建深度为N的折痕树使用中序遍历打印出数中所有节点的内容
构建深度为N的折痕树
第一次对折只有一条折痕创建根节点如果不是第一次对着则使用队列保存根节点循环遍历队列 从队列中弹出一个节点如果这个节点的左子节点不为空则把这个左子节点添加到队列中如果这个节点的右子节点不为空则把这个右子节点添加到队列中判断当前节点的左子节点和右子节点都不为空如果是则需要为当前节点创建一个值为down的左子节点一个值为up的右子节点
实现代码
/**
* 模拟对折过程产生树
* param n 对折次数
* return
*/
public static NodeString createTree(int n){// 定义根节点NodeString root null;for (int i 0; i n; i) {// 1. 当前树为空if (i0){root new Node(down,null,null);continue;}// 2. 当前树不为空// 定义一个辅助队列通过层序遍历思想找到叶子节点给叶子节点添加子节点QueueNode queue new Queue();queue.enqueue(root);// 3. 循环遍历队列while (!queue.isEmpty()){// 从队列中弹出节点NodeString tmp queue.dequeue();// 如果有左子节点则把左子系欸但放入到队列中if (tmp.left ! null){queue.enqueue(tmp.left);}// 如果有右子节点则把左子系欸但放入到队列中if (tmp.right ! null){queue.enqueue(tmp.right);}// 如果左右两个子节点都没有那么该节点为叶子节点只需要给该节点添加左子节点和右子节点if (tmp.right null tmp.left null){tmp.left new NodeString(down,null,null);tmp.right new NodeString(up,null,null);}}}return root;
}// 打印树中的全部节点
public static void printTree(NodeString root){// 使用中序遍历if (rootnull){return;}// 打印左子树的每个节点if(root.left!null){printTree(root.left);}// 打印当前节点System.out.print(root.item );// 打印右子树的每个节点if(root.right!null){printTree(root.right);}
}// 节点类
public static class NodeT{public T item;public Node left;public Node right;public Node(T item, Node left, Node right) {this.item item;this.left left;this.right right;}
}
