精华内容
下载资源
问答
  • 数据结构是一门学习数据存储方式的一门学科 存储结构 线性表:还可细分为 顺序表 链表 栈 队列 树结构:包括普通树 二叉树 线索二叉树 图存储结构 线性表:往往依次排序的 具备一对一关系的数据就可以用线性表来...

    数据结构

    数据结构是一门学习数据存储方式的一门学科

    存储结构

    线性表:还可细分为 顺序表 链表 栈 队列
    树结构:包括普通树 二叉树 线索二叉树
    图存储结构

    线性表:往往是依次排序的 具备一对一关系的数据就可以用线性表来存储

    线性表并不是一种具体的存储结构,它包含顺序存储结构和链式存储结构,是顺序表和链表的统称
    顺序表:如常用的数组 由于顺序表结构的底层实现借助的就是数组,因此对于初学者来说,可以把顺序表完全等价为数组,但实则不是这样
    链表 :数据的存储位置是随机的 链表给各数据块增设一个指针,每个数据块的指针都指向下一个数据块(最后一个数据块的指针指向 NULL)
    栈和队列:是特殊的线性表 **对线性表中元素的进出做了明确的要求栈:先入后出 只有一端 队列:先入先出 俩端 **

    树存储结构:多用来存储 一对多关系的数据

    图存储结构:多用来存储 多对多关系的数据

    展开全文
  • 首先要谈一谈线索二叉树为什么会产生,很多东西不是无缘无故的突然出现在书本,那么肯定有他出现的理由,我先举个你们熟悉的案例,比如开始我们使用单链表进行数据的存储和访问,但是访问方法只能从一端跑到顶,...

    首先要谈一谈线索二叉树为什么会产生,很多东西不是无缘无故的突然出现在书本,那么肯定是有他出现的理由,我先举个你们熟悉的案例,比如开始我们是使用单链表进行数据的存储和访问,但是访问方法只能从一端跑到顶,假如我们想要访问最后一个节点元素,我们必须通过首节点开始一一遍历,这个时候循环链双向表就产生了,我们可以快速访问末尾节点,那么线索二叉树也是为了快速访问吗,NO,我们是为了不浪费内存,其实都一样,都是为把数据结构类型设计的更加完美。
    先上图观察一下二叉树浪费的内存。

    这里写图片描述

     我们把节点元素中那么没有孩子节点的指针占的内存都加起来都是浪费的内存。那么我们如果想把这么没有保存节点地址的指针变量保存我们需要的数据是不是非常nice呢,回答是肯定的。
    

    我们如果采用中序遍历输出如下:

    这里写图片描述

    按照中序遍历后得到的节点序列如图,我们仔细发现H节点端的指针都是空的,I节点2端的指针也是空的,E也是,刚好是隔一个就有个节点2端刚好都是浪费的。难道我们不能刚好把那2个坑刚好保存当前序列的前后节点地址么,充分利用。因此线索二叉树在进行中序遍历后每个元素节点可以非常快速的访问其序列的前后节点。但是有个问题这2个地址都是保存节点地址,那么我们是如何区分保存的孩子节点还是前后节点呢。我们是通过浪费内存定义2个标志用来当前保存的是孩子节点还是前后节点。

    先看图
    这里写图片描述

    我们约定ltag = 0时表示该节点指向做孩子,1就说明是保存的节点的前驱 ltag ===leftTag 左标志
    其他就。。。
    typedef char ElemType;

    //线索存储标志位
    //Link(0)表示表示指向左右孩子的指针
    //Thread(1)表示指向前驱后继的线索
    typedef enum {Link, Thread} PointerTag;

    typedef struct BiThrNode
    {
    ElemType data;
    struct BiThrNode *lchild, *rchild;
    PointerTag ltag;
    PointerTag rtag;
    } BiThrNode, *BitThrTree;

    待续代码日后贴上

    展开全文
  • 目录一、什么是线索二叉树二、线索二叉树的存储方式三、二叉树线索化及遍历(一)前序线索化及遍历(二)中序线索化及遍历(三)后序线索化及遍历四、带头结点的中序线索化五、总结 一、什么是线索二叉树 概括来讲,...

    一、什么是线索二叉树

    概括来讲,线索二叉树就是将二叉树中空的指针域利用了起来,用来保存遍历过程中前驱结点和后继结点的信息。其中这样的信息叫做线索。

    二叉树的遍历其实就是一个将非线性结构(树,一对多的关系)转化成一个线性结构(线性表,一对一的关系)的过程。得到的线性序列中除第一个结点和最后一个结点外其它结点都只有一个直接前驱和一个直接后继(简称前驱后继)。

    有了这些前驱后继信息的好处是:在查找某个结点时就可以类似链表那样很方便的从表头遍历到表尾,并且空间复杂度只有O(1)Ο(1)。而前面二叉树的遍历中,无论递归还是非递归,都要用到栈,空间复杂度跟二叉树的具体形态有关。

    二、线索二叉树的存储方式

    使用链式存储,其中:

    (1)首先最容易想到的办法就是直接在每个结点中单独增加两个指针用来指向前驱后继,但这样增加了结点的空间,降低了存储密度。

    (2)因为n个结点必定存在n+1个空指针域,可以利用这些空指针域来存放结点的前驱或后继信息。具体方法是:

    • 对于一个结点,如果它的左子结点非空,那么结点左指针指向左子结点不变,否则左指针指向它的前驱结点;同理如果右子结点非空,结点右指针指向右子树不变,否则指向它的后继结点。

    • 因为指针域指向的可能是子结点,也可能是前驱或后继结点,所以还需要在结点中为左右两个指针增加两个标志位,分别为LTag,RTag。并表示:

    LTag={0结点左指针指向左孩子1结点左指针指向前驱结点 LTag= \begin{cases} 0 & \text {结点左指针指向左孩子} \\ 1 & \text{结点左指针指向前驱结点} \end{cases}
    RTag={0结点右指针指向右孩子1结点右指针指向后驱结点 RTag= \begin{cases} 0 & \text {结点右指针指向右孩子} \\ 1 & \text{结点右指针指向后驱结点} \end{cases}

    关于n个结点存在n+1个空链域:可以这样理解,n个结点一定有2n个指针域,又除根结点外所有结点都被一个指针指向,共占用了n-1个指针域,所以还剩n+1个空指针域。

    三、二叉树线索化及遍历

    首先创建一棵二叉树

    public static TreeNode buildTree(char[] arr, int index) {
    	TreeNode root = null;
    	if (index < arr.length) {
    		if (arr[index] == '#') {
    			return null;
    		}
    		root = new TreeNode(arr[index]);
    		root.lchild = buildTree(arr, 2 * index + 1);
    		root.rchild = buildTree(arr, 2 * index + 2);
    	}
    	return root;
    }
    

    其中结点的结构为

    class TreeNode {
    	char data;
    	TreeNode lchild;
    	TreeNode rchild;
    	int LTag;
    	int RTag;
    
    	public TreeNode(char data) {
    		this.data = data;
    		this.LTag = 0;
    		this.RTag = 0;
    	}
    }
    

    (一)前序线索化及遍历

    前序线索化

    前序线索化就是在前序遍历的过程中动态的为每个结点添加前驱或后继的信息。

    //首先创建一个结点用来保存访问结点的前驱结点
    static TreeNode preNode = null;
    
    public static void preThreading(TreeNode T) {
    	if (T != null) {
    		// 访问结点的左指针为空则指向前驱结点,修改标志位
    		if (T.lchild == null) {
    			T.lchild = preNode;
    			T.LTag = 1;
    		}
    		// 前驱结点存在且右指针为空则右指针指向后继结点也就是访问结点,修改标志位
    		if (preNode != null && preNode.rchild == null) {
    			preNode.rchild = T;
    			preNode.RTag = 1;
    		}
    		// 修改前驱结点
    		preNode = T;
    		
    		// 递归处理左子树
    		if (T.LTag == 0)
    			preThreading(T.lchild);
    		// 递归处理右子树
    		if (T.RTag == 0)
    			preThreading(T.rchild);
    	}
    }
    

    下面是这棵二叉树前序线索化后的结果(虚线表示线索),可以发现前序线索化后可以根据后继线索从前往后遍历,但不能根据前驱线索从后往前遍历。总结就是前序线索化找前驱困难。
    在这里插入图片描述
    要注意前序线索化过程存在死循环,进入递归时必须要有 if 条件限制。以上面二叉树为例,如果没有限制,假设当前访问结点是D,和前驱结点B建立线索也就是左指针指向B,然后递归进入左子树回到了B,B又递归进入左子树回到D,陷入死循环。

    前序线索化的遍历(按后继线索)(ABDEC)

    按后继线索是指遍历过程中用到的线索是指向后继结点的线索,下面同理。

    public static void preThreadTraverse(TreeNode T) {
    	while (T != null) {
    		// 从根结点开始往左一直遍历到最左子结点
    		while (T.LTag == 0) {
    			System.out.print(T.data);
    			T = T.lchild;
    		}
    		System.out.print(T.data);
    
    		// 这里的T.rchild可能是线索,可能是右子结点
    		T = T.rchild;
    	}
    }
    

    (二)中序线索化及遍历

    中序线索化

    中序线索化即在中序遍历的过程中动态的为每个结点添加前驱或后继的信息。

    static TreeNode preNode = null;
    
    public static void inThreading(TreeNode T) {
    	if (T != null) {
    		// 递归处理左子树
    		inThreading(T.lchild);
    
    		// 访问结点的左指针为空则指向前驱结点,修改标志位
    		if (T.lchild == null) {
    			T.lchild = preNode;
    			T.LTag = 1;
    		}
    		// 前驱结点存在且右指针为空则右指针指向后继结点也就是访问结点,修改标志位
    		if (preNode != null && preNode.rchild == null) {
    			preNode.rchild = T;
    			preNode.RTag = 1;
    		}
    		// 修改前驱结点
    		preNode = T;
    
    		// 递归处理右子树
    		inThreading(T.rchild);
    	}
    }
    

    还是上面那棵二叉树中序线索化后的结果,可以发现中序线索化后既可以按照后继线索从前往后遍历也可以按照前驱线索从后往前遍历。
    在这里插入图片描述
    中序线索化的遍历(按后继线索)(DBEAC)

    public static void inThreadTraverse(TreeNode T) {
    	while (T != null) {
    		// 找到开始遍历的结点也就是最左子结点并输出
    		while (T.LTag == 0) {
    			T = T.lchild;
    		}
    		System.out.print(T.data);
    		/*
    		 * 如果存在右线索不断的沿右线索遍历后继结点并输出。 
    		 * 其实个人觉得下面while也可以替换成if,因为中序左根右,线索一定是左子结点指向父结点,
    		 * 那么接下来一定是遍历这个父结点的右子树,即不存在两条连续的后继线索。 如果有不同想法欢迎指出。
    		 */
    		while (T.rchild != null && T.RTag == 1) {
    			T = T.rchild;
    			System.out.print(T.data);
    		}
    		// 不存在右线索时转向这个结点的右子树
    		T = T.rchild;
    	}
    }
    

    (三)后序线索化及遍历

    后序线索化

    后序线索化即在后序遍历的过程中动态的为每个结点添加前驱或后继的信息。

    static TreeNode preNode = null;
    
    public static void postThreading(TreeNode T) {
    	if (T != null) {
    		// 递归处理左子树
    		postThreading(T.lchild);
    		// 递归处理右子树
    		postThreading(T.rchild);
    
    		// 访问结点的左指针为空则指向前驱结点,修改标志位
    		if (T.lchild == null) {
    			T.lchild = preNode;
    			T.LTag = 1;
    		}
    		// 前驱结点存在且右指针为空则右指针指向后继结点也就是访问结点,修改标志位
    		if (preNode != null && preNode.rchild == null) {
    			preNode.rchild = T;
    			preNode.RTag = 1;
    		}
    		// 修改前驱结点
    		preNode = T;
    	}
    }
    

    后序线索化后的结果,可以发现后序线索化后可以按照前驱线索从后往前遍历,但不能根据后继线索从前往后遍历。总结就是后序线索化找后继困难。
    在这里插入图片描述
    后序线索化的遍历(按后继线索)(DEBCA)

    因为后序遍历左右根的次序,所以后序遍历建立线索时必然存在两种情况:
    (1)一个结点与父结点建立线索时因为该结点的右子结点存在右指针域非空导致后继线索建立失败。
    (2)从根结点的左子树往右子树建立线索时因为根结点的左子节点右指针域非空导致后继线索建立失败。

    比如上面这棵树按后继线索遍历时,先找到开始遍历的结点D,然后依次遍历E,B,但结点B的右指针保存的是右子结点而不是线索,无法遍历到结点C。对应上述的情况(2)。

    再来回顾一下前序中序的线索化:因为前序遍历根左右中序遍历左根右的顺序,最后访问的结点一定是左右叶子结点,两个指针域为空线索可以建立。否则在原二叉树中一定存在一条路径可以间接找到后继结点,也就不存在后序线索化中的既后继线索建立失败又无法通过原二叉树中的指向关系找到后继结点。

    无论出现上面两种情况中的哪种情况,都可以通过在原二叉树结点中添加一个指向父结点的指针来解决。比如上面这棵树遍历到结点B时,可以通过先回到父结点A再寻找到结点C。

    对应的结点结构

    class TreeNode {
    	char data;
    	TreeNode lchild;
    	TreeNode rchild;
    	TreeNode parent;					// 添加父结点的指针
    	int LTag;
    	int RTag;
    
    	public TreeNode(char data) {
    		this.data = data;
    		this.LTag = 0;
    		this.RTag = 0;
    	}
    }
    

    带父指针的二叉树初始化

    public static TreeNode buildTree(char[] arr, int index) {
    	TreeNode root = null;
    	if (index < arr.length) {
    		if (arr[index] == '#') {
    			return null;
    		}
    		root = new TreeNode(arr[index]);
    		root.lchild = buildTree(arr, 2 * index + 1);
    		root.rchild = buildTree(arr, 2 * index + 2);
    		
    		// 记录父结点
    		if (root.lchild != null)
    			root.lchild.parent = root;
    		if (root.rchild != null)
    			root.rchild.parent = root;
    	}
    	return root;
    }
    

    线索化过程不变。

    遍历

    public static void postThreadTraverse(TreeNode T) {
    	TreeNode root = T;
    	TreeNode preNode = null;	
    	// 找到后序遍历开始的结点
    	while (T.LTag == 0) {
    		T = T.lchild;
    	}
    
    	while (true) {
    		// 右指针是线索
    		if (T.RTag == 1) {
    			System.out.print(T.data);
    			preNode = T;
    			T = T.rchild;		
    		} else {
    			// 上个访问的结点是右子结点
    			if (T.rchild == preNode) {
    				System.out.print(T.data);
    				if (T == root) {
    					return;
    				}
    				preNode = T;
    				T = T.parent;
    			} else {
    				// 上个访问的结点是左子结点转到右子树
    				T = T.rchild;
    				while (T.LTag == 0) {
    					T = T.lchild;
    				}	
    			}
    		}
    	}
    }
    

    四、带头结点的中序线索化

    因为中序线索化可以根据前驱线索或后继线索双向遍历的特点,所以可以通过添加一个头结点形成类似双向循环链表结构,既可以从头结点从前往后遍历,也可以从头结点从后往前遍历。

    具体步骤为:
    (1)新建一个头结点,头结点左指针指向根节点,左标记LTag=0不变,右标记Rtag初始修改为1表示用来存放线索。preNode初始指向头结点。
    (2)调用中序线索化的算法,调用完毕后preNode会停在最后个结点的位置。
    (3)最后将头结点右指针指向最后一个结点preNode,最后一个结点右指针指向头结点。

    // 注意head是一个data为空的结点而不是null,且LTag默认为0
    public static void inThreadingWithHead(TreeNode head, TreeNode T) {
    	if (T != null) {
    		head.lchild = T;
    		head.RTag = 1;
    		preNode = head;
    
    		inThreading(T);
    
    		preNode.rchild = head;
    		preNode.RTag = 1;
    		head.rchild = preNode;
    	}
    }
    

    线索化后的结果:
    在这里插入图片描述
    遍历

    public static void inThreadWithHeadTraverse(TreeNode head) {
    	TreeNode T = head.lchild;
    	// 此处循环结束条件不再是T!=null
    	while (T != head) {
    		while (T.LTag == 0) {
    			T = T.lchild;
    		}
    		System.out.print(T.data);
    
    		// 此处循环条件要加上T.rchild!=head限制,如果不限制会陷入头结点与最后个结点之间的死循环
    		while (T.RTag == 1 && T.rchild != head) {
    			T = T.rchild;
    			System.out.print(T.data);
    		}
    		T = T.rchild;
    	}
    }
    

    五、总结

    (1)无论有没有线索化,遍历的过程中都只访问了nn个结点,时间复杂度都是O(n)Ο(n)。线索化的空间复杂度除第一次遍历建立线索外,之后遍历都是O(1)Ο(1)
    (2)前序线索化找前驱困难,后序线索化找后继困难。
    (3)因为中序线索化可以双向遍历的原因,所以可以在中序线索化中添加一个头结点构成双向循环链表。
    (4)点击查看后序线索化动态演示过程

    展开全文
  • Skip List(跳跃表)一种支持快速查找的数据结构,插入、查找和删除操作都仅仅只需要O(log n)对数级别的时间复杂度,它的效率甚至可以与红黑树等二叉平衡树相提并论,而且实现的难度要比红黑树简单多了。Skip List...

    5f8b6ccdcf1abd90d0ec80ecaea72c40.png

    Skip List(跳跃表)是一种支持快速查找的数据结构,插入、查找和删除操作都仅仅只需要O(log n)对数级别的时间复杂度,它的效率甚至可以与红黑树等二叉平衡树相提并论,而且实现的难度要比红黑树简单多了。Skip List主要思想是将链表与二分查找相结合,它维护了一个多层级的链表结构(用空间换取时间),可以把Skip List看作一个含有多个行的链表集合,每一行就是一条链表,这样的一行链表被称为一层,每一层都是下一层的”快速通道”,即如果x层和y层都含有元素a,那么x层的a会与y层的a相互连接(垂直)。最底层的链表是含有所有节点的普通序列,而越接近顶层的链表,含有的节点则越少。

    1786b7b4730d4a997bbd2d08852d3de6.png

    对一个目标元素的搜索会从顶层链表的头部元素开始,然后遍历该链表,直到找到元素大于或等于目标元素的节点,如果当前元素正好等于目标,那么就直接返回它。如果当前元素小于目标元素,那么就垂直下降到下一层继续搜索,如果当前元素大于目标或到达链表尾部,则移动到前一个节点的位置,然后垂直下降到下一层。正因为Skip List的搜索过程会不断地从一层跳跃到下一层的,所以被称为跳跃表。Skip List还有一个明显的特征,即它是一个不准确的概率性结构,这是因为Skip List在决定是否将节点冗余复制到上一层的时候(而在到达或超过顶层时,需要构建新的顶层)依赖于一个概率函数,举个栗子,我们使用一个最简单的概率函数:丢硬币,即概率P为0.5,那么依赖于该概率函数实现的Skip List会不断地”丢硬币”,如果硬币为正面就将节点复制到上一层,直到硬币为反。

    f1de6aa0100a02b1bfbb2d9004bf92f5.png

    理解Skip List的原理并不困难,下面我们将使用Java来动手实现一个支持基本需求(查找,插入和删除)的Skip List。# 节点与基本实现对于一个普通的链表节点一般只含有一个指向后续节点的指针(双向链表的节点含有两个指针,一个指向前节点,一个指向后节点),由于Skip List是一个多层级的链表结构,我们的设计要让节点拥有四个指针,分别对应该节点的前后左右,为了方便地将头链表永远置于顶层,还需要设置一个int属性表示该链表所处的层级。
    protected static class Node, V> {        private K key;        private V value;        private int level; // 该节点所处的层级        private Node up, down, next, previous;        public Node(K key, V value, int level) {            this.key = key;            this.value = value;            this.level = level;        }        @Override        public String toString() {            StringBuilder sb = new StringBuilder();            sb.append("Node[")                    .append("key:");            if (this.key == null)                sb.append("None");            else                sb.append(this.key.toString());            sb.append(" value:");            if (this.value == null)                sb.append("None");            else                sb.append(this.value.toString());            sb.append("]");            return sb.toString();        }    // 余下都是get,set方法, 这里省略    .....}
    接下来是SkipList的基本实现,为了能够让Key进行比较,我们规定Key的类型必须实现了Comparable接口,同时为了支持ForEach循环,该类还实现了Iterable接口。
    public class SkipList, V> implements Iterable {  // 一个随机数生成器    protected static final Random randomGenerator = new Random();  // 默认的概率    protected static final double DEFAULT_PROBABILITY = 0.5;  // 头节点    private Node head;    private double probability;  // SkipList中的元素数量(不计算多个层级中的冗余元素)    private int size;    public SkipList() {        this(DEFAULT_PROBABILITY);    }    public SkipList(double probability) {        this.head = new Node(null, null, 0);        this.probability = probability;        this.size = 0;    }  .....}
    我们还需要定义几个辅助方法,如下所示(都很简单):
    // 对key进行检查// 因为每条链表的头节点就是一个key为null的节点,所以不允许其他节点的key也为null   protected void checkKeyValidity(K key) {       if (key == null)           throw new IllegalArgumentException("Key must be not null!");   }// a是否小于等于b   protected boolean lessThanOrEqual(K a, K b) {       return a.compareTo(b) <= 0;   }// 概率函数   protected boolean isBuildLevel() {       return randomGenerator.nextDouble() < probability;   }// 将y水平插入到x的后面   protected void horizontalInsert(Node x, Node y) {       y.setPrevious(x);       y.setNext(x.getNext());       if (x.getNext() != null)           x.getNext().setPrevious(y);       x.setNext(y);   }// x与y进行垂直连接   protected void verticalLink(Node x, Node y) {       x.setDown(y);       y.setUp(x);   }

    # 查找

    查找一个节点的过程如下:
    • 从顶层链表的头部开始进行遍历,比较每一个节点的元素与目标元素的大小。
    • 如果当前元素小于目标元素,则继续遍历。
    • 如果当前元素等于目标元素,返回该节点。
    • 如果当前元素大于目标元素,移动到前一个节点(必须小于等于目标元素),然后跳跃到下一层继续遍历。
    • 如果遍历至链表尾部,跳跃到下一层继续遍历。
    protected Node findNode(K key) {      Node node = head;      Node next = null;      Node down = null;      K nodeKey = null;      while (true) {          // 不断遍历直到遇见大于目标元素的节点          next = node.getNext();          while (next != null && lessThanOrEqual(next.getKey(), key)) {              node = next;              next = node.getNext();          }  // 当前元素等于目标元素,中断循环          nodeKey = node.getKey();          if (nodeKey != null && nodeKey.compareTo(key) == 0)              break;          // 否则,跳跃到下一层级          down = node.getDown();          if (down != null) {              node = down;          } else {              break;          }      }      return node;  }  public V get(K key) {      checkKeyValidity(key);      Node node = findNode(key);// 如果找到的节点并不等于目标元素,则目标元素不存在于SkipList中      if (node.getKey().compareTo(key) == 0)          return node.getValue();      else          return null;  }

    # 插入

    插入操作的过程要稍微复杂些,主要在于复制节点到上一层与构建新层的操作上。
    public void add(K key, V value) {      checkKeyValidity(key);// 直接找到key,然后修改对应的value即可      Node node = findNode(key);      if (node.getKey() != null && node.getKey().compareTo(key) == 0) {          node.setValue(value);          return;      }// 将newNode水平插入到node之后      Node newNode = new Node(key, value, node.getLevel());      horizontalInsert(node, newNode);      int currentLevel = node.getLevel();      int headLevel = head.getLevel();      while (isBuildLevel()) {          // 如果当前层级已经到达或超越顶层  // 那么需要构建一个新的顶层          if (currentLevel >= headLevel) {              Node newHead = new Node(null, null, headLevel + 1);              verticalLink(newHead, head);              head = newHead;              headLevel = head.getLevel();          }          // 找到node对应的上一层节点          while (node.getUp() == null) {              node = node.getPrevious();          }          node = node.getUp();  // 将newNode复制到上一层          Node tmp = new Node(key, value, node.getLevel());          horizontalInsert(node, tmp);          verticalLink(tmp, newNode);          newNode = tmp;          currentLevel++;      }      size++;  }

    # 删除

    对于删除一个节点,需要先找到节点所在的位置(位于最底层链表中的位置),之后再自底向上地删除该节点在每一行中的冗余复制。
    public void remove(K key) {    checkKeyValidity(key);    Node node = findNode(key);    if (node == null || node.getKey().compareTo(key) != 0)        throw new NoSuchElementException("The key is not exist!");    // 移动到最底层    while (node.getDown() != null)        node = node.getDown();    // 自底向上地进行删除    Node prev = null;    Node next = null;    for (; node != null; node = node.getUp()) {        prev = node.getPrevious();        next = node.getNext();        if (prev != null)            prev.setNext(next);        if (next != null)            next.setPrevious(prev);    }    // 对顶层链表进行调整,去除无效的顶层链表    while (head.getNext() == null && head.getDown() != null) {        head = head.getDown();        head.setUp(null);    }    size--;}

    # 迭代器

    由于我们的SkipList实现了Iterable接口,所以还需要实现一个迭代器。对于迭代一个Skip List,只需要找到最底层的链表并且移动到它的首节点,然后进行遍历即可。
    @Override  public String toString() {      StringBuilder sb = new StringBuilder();      Node node = head;      // 移动到最底层      while (node.getDown() != null)          node = node.getDown();      while (node.getPrevious() != null)          node = node.getPrevious();      // 第一个节点是头部节点,没有任何意义,所以需要移动到后一个节点      if (node.getNext() != null)          node = node.getNext();// 遍历      while (node != null) {          sb.append(node.toString()).append("\n");          node = node.getNext();      }      return sb.toString();  }  @Override  public Iterator iterator() {      return new SkipListIterator(head);  }  protected static class SkipListIterator, V> implements Iterator {      private Node node;      public SkipListIterator(Node node) {          while (node.getDown() != null)              node = node.getDown();          while (node.getPrevious() != null)              node = node.getPrevious();          if (node.getNext() != null)              node = node.getNext();          this.node = node;      }      @Override      public boolean hasNext() {          return this.node != null;      }      @Override      public K next() {          K result = node.getKey();          node = node.getNext();          return result;      }      @Override      public void remove() {          throw new UnsupportedOperationException();      }  }

    作者:SylvanasSun’s Blog      

    来源:sylvanassun.github.io/2017/12/31/2017-12-31-skip_list

     往期推荐 

    ?

    • 阿里技术揭秘:如何实现32.5万笔/秒的交易峰值?
    • 一口气说出 6种:@Transactional注解的失效场景
    • 我的VS Code设置,高效编码!

    7cf5bc39aa02166a602944f5be192ed6.png

    35b893a6387908d4307634a624e39d16.gif
    展开全文
  • 技术面试,数据结构很重要,作为提醒和重点1、栈:(stack)先进后出,后进先出;一个开口2、队列:(queue)先进先出3、二叉树:每个节点至多只有两颗子树,有顺序存储结构和链式存储结构。4、遍历二叉树:先序遍历 DLR...
  • 数据结构-线索二叉树

    2019-08-13 16:30:31
    1.什么是线索二叉树 遍历二叉树是按一定的规则将二叉树中所有结点排列为一个有序序列,这实质上是对一个非线性的数据结构进行线性化的操作。经过遍历的结点序列,除第一个结点和最后一个结点以外,其余每个结点都有...
  • 什么是线索二叉树 在有n个结点的二叉链表中必定存在n+1个空指针域,因此可以利用这些空指针域存放指向结点的某种遍历次序下的前趋和后继结点的指针,这种指向前趋和后继结点的指针称为“线索”,加上线索的二叉...
  •  我们知道二叉树一种非线性结构,当我们遍历二叉树的时候,我们一般的方法利用递归或者借助栈来实现非递归,而不管利用递归还是栈我们知道,它们所用的开销很大的,即压栈,建立新的栈帧,当有时候我们...
  • 数据结构是什么

    2019-09-24 09:51:55
    数据结构:直白地理解,就是研究数据的存储方式。 数据结构大致包含以下几种存储结构: 线性表:还可细分为顺序表、链表、栈和队列; 树结构:包括普通树,二叉树,线索二叉树等; 图存储结构; 顺序表:...
  • 什么是线索二叉树? 我们知道二叉树的是一棵树的度小于等于2的有序树;那么线索二叉树又是什么呢?线索二叉树实际是一棵变形的二叉树。 如果有一种算法需要经常的对一棵二叉树进行遍历,那么遍历的过程就是在频繁...
  • 文章目录思路Java 实现 思路 声明 线索二叉树结点中含有...为什么线索化二叉树呢? 我们知道对于一个满二叉树来讲,其叶子结点为2^(n-1)个,这些叶子空指针域有2^n个,这个 n 树的深度,我们可以利用这些空指针...
  • 数据结构在计算机中的表示,使用计算机语言实现的逻辑结构,它依赖于计算机语言。 2 通过逻辑结构和存储结构的精确定义我们可以发现,存储结构 依赖于计算机语言 的,当我们用计算机高级语言如c语言去定义二叉...
  • 思考:在有n个节点的二叉链表中必定有n+1个空链域(下面会说为什么),遍历运算最重要也最常用的运算,之前的无论递归与非递归算法实现遍历效率都不算高。能不能利用这未使用的n+1空指针域,设计出提高遍历效率...
  • 有趣的数据结构算法16——线索二叉树的构建什么是线索二叉树线索二叉树的实现形式线索二叉树的代码实现线索二叉树的初始化线索的串联全部实现代码GITHUB下载连接 深度遍历不仅仅有递归的方法噢,还有通过建立线索...
  • 线索二叉树,设计的思想是什么呢?不用帮我写代码,告诉我思想就行了。比如,用递归算法完成遍历子树功能,我课本有代码,但是看不懂 。,,
  • 数据结构 — 二叉树的线索

    千次阅读 2017-05-15 19:34:21
    二叉树的线索化 首先线索是什么
  • 什么线索化二叉树? 对于二叉树的遍历,我们知道每个节点的前驱与后继,但是这建立在遍历的基础上,否则我们只知道后续的左右子树。现在我们充分利用二叉树左右子树的空节点,分别指向当前节点的前驱、后继,便于...
  • 1)什么是线索二叉树以及线索的作用 1)什么是线索二叉树以及线索的作用 指向前驱和后继的指针称为线索,相应的二叉树就称为线索二叉树。 线索的作用:因为空地址存放指向结点在某种遍历次序下的前驱和后继结点的...
  • 什么线索化二叉树?对于二叉树的遍历,我们知道每个节点的前驱与后继,但是这建立在遍历的基础上,否则我们只知道后续的左右子树。现在我们充分利用二叉树左右子树的空节点,分别指向当前节点的前驱、后继,便于...
  • 什么是线索二叉树 一个普通的二叉树,使用链式存储: 对于n个结点的二叉树,在二叉链存储结构中有n+1个空链域,利用这些空链域存放在某种遍历次序下该结点的前驱结点和后继结点的指针,这些指针称为线索,加上线索...
  • 数据结构和算法系列15 线索二叉树 ...1,什么是线索二叉树? 2,为什么要建立线索二叉树? 3,如何将二叉树线索化? 4,线索二叉树的常见操作及实现思路? 5,算法实现代码? 一,
  • ​zhuanlan.zhihu.com什么是线索二叉树?线索二叉树分为三类:对一棵二叉树中所有节点的空指针域按照某种遍历方式加线索的过程叫作线索化,被线索化了的二叉树称为线索二叉树。为什么需要线索二叉树?知道了“前驱”...
  • 先试试看原先的遍历方法: 测试:出现死循环。 因为原先的8号节点的左右指针空的,这也结束遍历的条件。 但在线索化之后,这个结束条件就不成立了。...会有疑问,例如:拿什么来区分节点指向的
  • 二叉线索树 1.概念 ...二叉线索树思想什么的? 线索化过程就是在遍历过程(假设中序遍历)中修改空指针的过程 将空的lchild改为结点的直接前驱 将空的rchild改为结点的直接后继 ...
  • 大话数据结构十五:线索二叉树

    千次阅读 2013-11-07 21:46:37
    1. 什么是线索二叉树? n个结点的二叉链表中含有(2n-(n-1)=n+1个空指针域。利用二叉链表中的空指针域,存放指向结点在某种遍历次序下的前驱和后继结点的指针(这种附加的指针称为"线索")。这种加上了线索的二叉...
  • 什么线索化二叉树?对于二叉树的遍历,我们知道每个节点的前驱与后继,但是这建立在遍历的基础上,否则我们只知道后续的左右子树。现在我们充分利用二叉树左右子树的空节点,分别指向当前节点的前驱、后继,便于...
  • 在介绍线索化二叉树之前先看一个问题:有一个数列Array(1,3,6,8,10,14),要构建成一棵二叉树,那么构建出来之后这个样子的:     好像没有什么问题,但是你会发现叶子节点8、10和14的左右...

空空如也

空空如也

1 2 3 4 5 ... 9
收藏数 165
精华内容 66
关键字:

数据结构什么是线索

数据结构 订阅