链式存储结构的特点

1.优点

1.存储空间动态分配，可以根据实际需要使用

2.不需要地址连续的存储空间

3.插入/删除操作只须通过修改指针实现，不必移动数据元素，操作时间效率高 （无论位于链表何处无论链表长度如何，插入和删除操作的时间都是O(1)）

2.缺点

1.每个链结点需要设置指针域（存储密度小）

2.是一种非随机存储结构，查找、定位等操作要通过顺序扫描链表实现，时间效率低O(n)

例题：

请写一个算法，该算法尽可能高的时间效率找到由list所指的线性链表的倒数第k个结点。若找到这样的结点，算法给出该结点的地址，否则给出NULL 

限制：1.算法中不得求出链表长度，也不允许对链表进行逆转

2.不允许使用除指针变量和控制变量以外的其他辅助空间

1.设置一个指针变量p，初始时指向链表的第一个结点

2.然后令p后移指向链表的第k个结点    执行k-1次

3.再设置另一个指针变量q,初始时指向链表的第一个结点

4.利用一个循环让p q 同步沿链表向后移动；当p指向链表最后那个结点时，q指向链表的倒数第k个结点  执行n-k次

LinkList SEARCHNODE(LinkList list, int k) 

{

LinkList p,q;

int i;

if (list != NULL && k > 0) {

p = p ->link;

if(p == NULL) {

printf(“链表中不存在倒数第k个结点”)；

return NULL;

}

}

q = list;

while(p -> link != NULL) {

p = p ->link;

q = q ->link;

}

return q; 

}

一、链式存储结构

由于顺序存储二叉树的空间利用率较低，因此二叉树一般都采用链式存储结构，用链表结点来存储二叉树中的每个结点。在二叉树中，结点结构通过包括若干数据域和若干指针域，二叉链表至少包含3个域：数据域 data、左指针域 lchild和右指针域 rchild，如下图所示：

其中，n 个结点的二叉链表中含有 n+1 [ 2n-(n-1)=n+1 ] 个空指针域。

二、线索二叉树

传统的二叉链表仅能体现出一种父子关系，不能直接得到结点在遍历中的前驱或后继。引入线索二叉树正是为了加快查找结点前驱和后继的速度。

规定：若无左子树，令 lchild指向其前驱结点；若无右子树，令rchild执行指向其后继结点。增加两个标志域标识是指向左/右孩子还是指向前驱/后继。

其标志位含义如下：

这种加上线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树。根据线索性质的不同， 线索二叉树可分为前序线索二叉树、 中序线索二叉树和后序线索二叉树三种。

1.1、中序线索二叉树
1.1.1 中序线索二叉树的构造

设置结点pre指向刚刚访问过的结点，结点node指向正在访问的结点，即pre指向node的前驱。在遍历过程中，检查node的左指针是否为空，若为空就将它指向pre；检查pre的右指针是否为空，若为空就将它指向node。

public static void inthreadNode(Node node) {
		if(node==null) {//结点为空无法线索化
			return;
		}
		//线索化左子树
		inthreadNode(node.getLeft());
		//线索化当前结点
		if(node.getLeft()==null) {
			node.setLeft(pre);//让当前结点的左指针指向前驱结点
			node.setLtag(1);//修改当前结点的左指针的类型,指向前驱结点
		}
		if(pre!=null&&pre.getRight()==null) {
			pre.setRight(node);//让前驱结点的右指针指向当前结点
			pre.setRtag(1);//修改当前结点的右指针的类型,指向后继结点
		}
		pre=node;//每处理一个结点后，让当前结点成为刚刚访问过的结点
		//线索化右子树
		inthreadNode(node.getRight());
	}

1.1.2 中序线索二叉树的遍历

因为线索化后， 各个结点指向有变化， 因此原来的遍历方式不能使用， 需要使用新的方式遍历线索化二叉树。中序线索二叉树的结点中隐含了线索二叉树的前驱和后继信息。在对其遍历时，需要找到第一个具有前驱结点的左结点，然后依次找结点的后继。在中序线索二叉树中找结点后继的规律是：若其右标志为1，则右链为线索，指示其后继，否则遍历右子树中第一个访问的结点（右子树中最左下的结点）为其后继。

public static void inthreadlist(Node node) {
		node=root;//存储当前遍历的结点，从root开始
		while(node!=null) {
			while(node.getLtag()==0) {
				node=node.getLeft();
			}
			System.out.println(node);//打印当前结点
			while(node.getRtag()==1) {//获取到当前结点的后继结点
				node=node.getRight();
				System.out.println(node);
			}
			node=node.getRight();//依次替换遍历的结点
		}
	}

1.1.3 中序线索二叉树完整代码

package Tree;

public class InThreadedBinaryTree {

	public static void main(String[] args) {
		Node root=new Node(7,"A");//创建二叉树
		Node a=new Node(4,"B");
		Node b=new Node(9,"C");
		Node c=new Node(2,"D");
		Node d=new Node(5,"E");
		Node e=new Node(8,"F");
		Node f=new Node(11,"G");
		Node g=new Node(1,"H");
		Node h=new Node(3,"I");
		Node i=new Node(10,"J");
		Node j=new Node(12,"K");
		root.setLeft(a);
		root.setRight(b);
		a.setLeft(c);
		a.setRight(d);
		b.setLeft(e);
		b.setRight(f);
		c.setLeft(g);
		c.setRight(h);
		f.setLeft(i);
		f.setRight(j);
		
		inThreadBinaryTree thread=new inThreadBinaryTree(root);
		inThreadBinaryTree.inthreadNode(root);//创建中序线索二叉树
		inThreadBinaryTree.inthreadlist(root);//遍历中序线索二叉树
	}
}

class Node{
	private int data;
	private String name;
	private Node left;//默认null
	private Node right;//默认null
	
	//若ltag == 0,说明指向的是左子树;ltag == 1，指向的是前驱结点
    //若rtag == 0,说明指向的是右子树;rtag == 1，指向的是后继结点
	private int ltag;
	private int rtag;
	
	public Node(int data,String name) {
		this.data=data;
		this.name=name;
	}
	
	public int getData() {
		return data;
	}
	public void setData(int data) {
		this.data = data;
	}
	public String getName() {
		return name;
	}
	public void setName(String name) {
		this.name = name;
	}
	public Node getLeft() {
		return left;
	}
	public void setLeft(Node left) {
		this.left = left;
	}
	public Node getRight() {
		return right;
	}
	public void setRight(Node right) {
		this.right = right;
	}
	public int getLtag() {
		return ltag;
	}
	public void setLtag(int ltag) {
		this.ltag = ltag;
	}
	public int getRtag() {
		return rtag;
	}
	public void setRtag(int rtag) {
		this.rtag = rtag;
	}

	@Override
	public String toString() {//重写toString方法
		return "Node [data=" + data + ", name=" + name + "]";
	}
}

//中序线索化二叉树(左->根->右)
class inThreadBinaryTree{
	private static Node root;
	
	private static Node pre=null;//pre表示刚刚访问过的结点，即前一个结点
	public inThreadBinaryTree(Node root) {//inThreadBinaryTree构造函数
		this.root=root;
	}
	
	public static void inthreadNode(Node node) {
		if(node==null) {//结点为空无法线索化
			return;
		}
		//线索化左子树
		inthreadNode(node.getLeft());
		//线索化当前结点
		if(node.getLeft()==null) {
			node.setLeft(pre);//让当前结点的左指针指向前驱结点
			node.setLtag(1);//修改当前结点的左指针的类型,指向前驱结点
		}
		if(pre!=null&&pre.getRight()==null) {
			pre.setRight(node);//让前驱结点的右指针指向当前结点
			pre.setRtag(1);//修改当前结点的右指针的类型,指向后继结点
		}
		pre=node;//每处理一个结点后，让当前结点成为刚刚访问过的结点
		//线索化右子树
		inthreadNode(node.getRight());
	}
	
	//中序线索化二叉树的遍历(遍历次序和中序遍历保持一致)
	public static void inthreadlist(Node node) {
		node=root;//存储当前遍历的结点，从root开始
		while(node!=null) {
			while(node.getLtag()==0) {
				node=node.getLeft();
			}
			System.out.println(node);//打印当前结点
			while(node.getRtag()==1) {//获取到当前结点的后继结点
				node=node.getRight();
				System.out.println(node);
			}
			node=node.getRight();//依次替换遍历的结点
		}
	}
}

运行结果：

Node [data=1, name=H]
Node [data=2, name=D]
Node [data=3, name=I]
Node [data=4, name=B]
Node [data=5, name=E]
Node [data=7, name=A]
Node [data=8, name=F]
Node [data=9, name=C]
Node [data=10, name=J]
Node [data=11, name=G]
Node [data=12, name=K]

该实例的二叉树图如下图所示：

2.1、前序线索二叉树和后序线索二叉树

一、线性表的链式存储结构

1、定义

线性表的链式存储单元的特点是用一组任意的存储单元存储线性表的数据元素，我们除了要存储它的元素信息外，我们还要存储它们的后继元素的存储地址。

如上图所示，在我们的节点中分数据域和指针域，指针域中存放的便是下一个结点的地址，如上图存放的0500便是下一个结点的地址。

2、头指针or头节点

头指针

• 头指针是指链表指向的第一个节点的指针，若链表有头节点，则是指向头节点的指针
• 头指针有标志作用，一般用头指针冠以链表的名字。
• 不论链表是否为空，头指针均不为空。
  头节点
• 头节点是为了操作的方便而设立的，数据域一般无意义。
• 有了头节点，对在第一元素节点前插入节点和删除节点等操作就统一了。
• 头节点不一定是链表必须要素。

二、单链表的读取

我们要获取第i个数据的算法思路，没办法一开始就知道，链表的查找比较麻烦。

1. 声明一个节点p指向链表的第一个结点，初始化j从1开始；
2. 当j<i时候，就遍历链表，让p的指针向后移，不断指向下一个节点，j累加。
3. 若到链表末尾p为空，则说明第i个元素不存在；
4. 否则查找成功，返回节点p的数据。
   说白了，就是从头开始找，直到第 i 个元素为止，因为不知道要循环多少次，所以我们不能用for循环，核心思想还是指针后移。

三、单链表的插入与删除

1、插入

如上图图所示，单链表的插入，需要先断开上面两个节点关系，让 p 的指针域存放 e 的地址，然后把之前 p 的下一个节点的地址给e的指针域。插入后如图所示：

当然，表头和表尾的操作也是一样，表头的操作就是把新的表头的指针域里存放之前表头的地址，表尾增加则是把新表尾的地址放在之前表尾的指针域。

2、单链表的删除

单链表的删除操作，也就是把上图所示的ai节点删除，我们只需要把ai+1结点的地址交给ai-1的指针域即可。
我们可以明显看到看到，对于插入删除数据越频繁的操作，单链表的优势是十分的明显，他们的时间复杂度都是O（1）。

三、单链表的整表创建

1、头插法

创建单链表的过程就是一个动态生成链表的过程，单链表头插法的思路是：
5. 声明一个节点p和计数变量i；
6. 初始化一空链表L；
7. 让L的头节点的指针指向null，建立一个带头结点的单链表。
8. 循环：
①生成一新结点赋值给P；
②随机生成艺术字赋值给p的数据域；
③将p插入到头节点与前一新结点之间。

2、尾插法

尾插法即我们在标为添加，我们设 r 为指向尾结点的变量，r 会随着循环不断的变化结点，而L我们定义为整个单链表，我们把原先的 r 的指针域存放新的尾结点的地址，然后我们最后让 r 拿到新的尾结点的地址，这样就完成了尾插法。

四、单链表的整表删除

单链表的整表删除也是要一个一个来，不能直接删除，要把下一个结点的值拿到后再删除本结点，不然找不到下一个节点在哪。步骤：

1. 声明节点p和q；
2. 将第一个结点赋给p；
3. 循环：先将下一个节点赋值给q，然后释放p，然后把q赋给p，如此循环。