树

树（Tree）是n(n>=0)个结点的有限集。n=0时称为空树。

在任意一颗非空树中：

(1)有且仅有一个特定的称为根（Root）的结点。

(2)当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1、T2、…..、Tm,其中每一个集合本身又是一棵树，并且称为根的子树（SubTree）。

树的常用术语

名称 含义
节点 树中的数据元素
树的度 树内各节点的度的最大值
节点的度 节点拥有的子树的数目称为度，记作d(v)
叶子节点 节点的度数为0，称为叶子节点leaf、终端节点、末端节点
分支节点 节点度数不为0，称为非终端节点或分支节点
分支 节点之间的关系
内部节点 除根节点外的分支节点，当然也不包括叶子节点
孩子节点 节点的子树的根节点成为该节点的孩子
双亲节点 父节点，即该节点的前驱
兄弟节点 具有相同双亲节点的节点
祖先节点 从根节点到该节点所经分支上所有的节点。
子孙节点 节点的所有子树上的节点都成为该节点的子孙。
节点的层次 根节点为第一层，根的孩子为第二层，依次类推记作(Lv)
树的深度 节点的层次的最大值
堂兄弟 双亲在同一层的节点
有序树 结点的子树是有顺序的(兄弟有大小，有先后次序)，不能交换
无序数 结点的子树是无序的，可以交换
路径 树中的k个节点n1、n2、…nk，满足ni是n(i+1)的双亲，成为n1到nk的一条路径。就是一条线串下来的，前一个都是后一个父(前驱)节点。
森林 m(m≥0)课不相交的树的集合，对于节点而言，其子树的集合就是森林。

二叉树

二叉树（Binary Tree）是n（n>=0）个节点的有限集合，该集合可以为空集（称为空二叉树），或者由一个根节点和两个互不相交的、分别称为根节点的左子树和右子树的二叉树组成。

二叉树的5种基本形态

  1. 根节点既有左子树，又有右子树
  2. 根节点只有左子树
  3. 根节点只有右子树
  4. 只有一个根节点
  5. 空二叉树

二叉树特点

  1. 每个节点最多有两个子树，所以二叉树不存在度大于2的节点，可以没有子树或者一个子树。
  2. 左子树和右子树有顺序，次序不能任意颠倒。
  3. 即使树中某节点只有一颗子树，也要区分是左子树还是右子树。

特殊二叉树

斜树：所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树。

斜树有很明显的特点，就是每一层都只有一个结点，结点的个数与二叉树的深度相同。线性表结构就可以理解为是树的一种极其特殊的表现形式。

满二叉树：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。

满二叉树的特点有：
（1）叶子只能出现在最下一层。
（2）非叶子结点的度一定是2。
（3）在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。

完全二叉树：对一棵具有n个结点的二叉树按层序编号，如果编号为i（1<i<n）的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树。

满二叉树一定是一棵完全二叉树，但完全二叉树不一定是满的。

完全二叉树的特点：
（1）叶子结点只能出现在最下两层。
（2）最下层的叶子一定集中在左部连续位置。
（3）倒数二层，若有叶子结点，一定都在右部连续位置。
（4）如果结点度为1，则该结点只有左孩子，即不存在只有右子树的情况。
（5）同样结点数的二叉树，完全二又树的深度最小。

二叉树性质

性质1：在二叉树的第i层上至多有2i-1个结点（i>=1）

性质2：深度为k的二叉树至多有2k-1个结点（k>=1）

性质3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0 = n2+1。

性质4：具有n个结点的完全二叉树的深度为[log2n ] + 1 ([X]表示不大于X的最大整数)。

性质5：如果对一颗有n个结点的完全二叉树的结点按层序编号（从第1层到第[log2n ] + 1层，每层从左到右），对任一结点 i (1<=i<=n)有：

  1. 如果 i=1，则结点i是二叉树的根，无双亲；如果 i>1，则其双亲是结点[i/2]。
  2. 如果 2i>n,则结点i无左孩子（结点i为叶子结点）；否则其左孩子是结点2i。
  3. 如果 2i+1>n,则结点i无右孩子；否则其右孩子是结点2i+1。

结合下图理解：

二叉树的遍历

二叉树的遍历是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。

前中后序遍历的介绍

前序遍历：规则是若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。如图所示，遍历的顺序为：ABDGHCEIF。

中序遍历：规则是若树为空，则空操作返回，否则从根结点开始（注意并不是先访问根结点），中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树。如图所示，遍历的顺序为：GDHBAEICF。

后序遍历：规则是若树为空，则空操作返回，否则从左到右的方式遍历访问左右子树，最后访问根结点。如图所示，遍历的顺序为：GHDBIEFCA。

前中后序遍历的代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
package com.nanzx.tree;

public class BinaryTreeDemo {

	public static void main(String[] args) {
		// 先创建一颗二叉树
		BinaryTree binaryTree = new BinaryTree();
		// 创建需要的结点
		HeroNode root = new HeroNode(1, "宋江");
		HeroNode node2 = new HeroNode(2, "吴用");
		HeroNode node3 = new HeroNode(3, "卢俊义");
		HeroNode node4 = new HeroNode(4, "林冲");
		HeroNode node5 = new HeroNode(5, "关胜");

		// 先手动创建该二叉树，后面学习递归的方式创建二叉树
		root.setLeft(node2);
		root.setRight(node3);
		node3.setRight(node4);
		node3.setLeft(node5);
		binaryTree.setRoot(root);

		// 测试
		System.out.println("前序遍历"); // 1,2,3,5,4
		binaryTree.preOrder();
		System.out.println("中序遍历");
		binaryTree.infixOrder(); // 2,1,5,3,4
		System.out.println("后序遍历");
		binaryTree.postOrder(); // 2,5,4,3,1
	}
}

class BinaryTree {
	private HeroNode root;

	public void setRoot(HeroNode root) {
		this.root = root;
	}

	// 前序遍历
	public void preOrder() {
		if (this.root != null) {
			this.root.preOrder();
		} else {
			System.out.println("二叉树为空，无法遍历");
		}
	}

	// 中序遍历
	public void infixOrder() {
		if (this.root != null) {
			this.root.infixOrder();
		} else {
			System.out.println("二叉树为空，无法遍历");
		}
	}

	// 后序遍历
	public void postOrder() {
		if (this.root != null) {
			this.root.postOrder();
		} else {
			System.out.println("二叉树为空，无法遍历");
		}
	}
}

class HeroNode {
	private int no;
	private String name;
	private HeroNode left;
	private HeroNode right;

	public HeroNode(int no, String name) {
		super();
		this.no = no;
		this.name = name;
	}

	public int getNo() {
		return no;
	}

	public void setNo(int no) {
		this.no = no;
	}

	public String getName() {
		return name;
	}

	public void setName(String name) {
		this.name = name;
	}

	public HeroNode getLeft() {
		return left;
	}

	public void setLeft(HeroNode left) {
		this.left = left;
	}

	public HeroNode getRight() {
		return right;
	}

	public void setRight(HeroNode right) {
		this.right = right;
	}

	@Override
	public String toString() {
		return "HeroNode [no=" + no + ", name=" + name + "]";
	}

	// 前序遍历
	public void preOrder() {
		System.out.println(this);
		if (this.left != null) {
			this.left.preOrder();
		}
		if (this.right != null) {
			this.right.preOrder();
		}
	}

	// 中序遍历
	public void infixOrder() {
		if (this.left != null) {
			this.left.infixOrder();
		}
		System.out.println(this);
		if (this.right != null) {
			this.right.infixOrder();
		}
	}

	// 后序遍历
	public void postOrder() {
		if (this.left != null) {
			this.left.postOrder();
		}
		if (this.right != null) {
			this.right.postOrder();
		}
		System.out.println(this);
	}
}

前中后序查找的代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
package com.nanzx.tree;

public class BinaryTreeDemo {

	public static void main(String[] args) {
		// 先创建一颗二叉树
		BinaryTree binaryTree = new BinaryTree();
		// 创建需要的结点
		HeroNode root = new HeroNode(1, "宋江");
		HeroNode node2 = new HeroNode(2, "吴用");
		HeroNode node3 = new HeroNode(3, "卢俊义");
		HeroNode node4 = new HeroNode(4, "林冲");
		HeroNode node5 = new HeroNode(5, "关胜");

		// 先手动创建该二叉树，后面学习递归的方式创建二叉树
		root.setLeft(node2);
		root.setRight(node3);
		node3.setRight(node4);
		node3.setLeft(node5);
		binaryTree.setRoot(root);
		
		//前序遍历查找的次数 4次
		System.out.println("前序遍历方式~~~");
		HeroNode resNode = binaryTree.preOrderSearch(5);
		if (resNode != null) {
			System.out.printf("找到了，信息为 no=%d name=%s", resNode.getNo(), resNode.getName());
		} else {
			System.out.printf("没有找到 no = %d 的英雄", 5);
		}
		
		//中序遍历查找的次数 3次
//		System.out.println("中序遍历方式~~~");
//		HeroNode resNode = binaryTree.infixOrderSearch(5);
//		if (resNode != null) {
//			System.out.printf("找到了，信息为 no=%d name=%s", resNode.getNo(), resNode.getName());
//		} else {
//			System.out.printf("没有找到 no = %d 的英雄", 5);
//		}
		
		//后序遍历查找的次数  2次
//		System.out.println("后序遍历方式~~~");
//		HeroNode resNode = binaryTree.postOrderSearch(5);
//		if (resNode != null) {
//			System.out.printf("找到了，信息为 no=%d name=%s", resNode.getNo(), resNode.getName());
//		} else {
//			System.out.printf("没有找到 no = %d 的英雄", 5);
//		}
	}

}

class BinaryTree {
	private HeroNode root;

	public void setRoot(HeroNode root) {
		this.root = root;
	}

	// 前序遍历查找
	public HeroNode preOrderSearch(int no) {
		if (root != null) {
			return root.preOrderSearch(no);
		} else {
			return null;
		}
	}

	// 中序遍历查找
	public HeroNode infixOrderSearch(int no) {
		if (root != null) {
			return root.infixOrderSearch(no);
		} else {
			return null;
		}
	}

	// 后序遍历查找
	public HeroNode postOrderSearch(int no) {
		if (root != null) {
			return this.root.postOrderSearch(no);
		} else {
			return null;
		}
	}
}

class HeroNode {
	private int no;
	private String name;
	private HeroNode left;
	private HeroNode right;

	public HeroNode(int no, String name) {
		super();
		this.no = no;
		this.name = name;
	}

	public int getNo() {
		return no;
	}

	public void setNo(int no) {
		this.no = no;
	}

	public String getName() {
		return name;
	}

	public void setName(String name) {
		this.name = name;
	}

	public HeroNode getLeft() {
		return left;
	}

	public void setLeft(HeroNode left) {
		this.left = left;
	}

	public HeroNode getRight() {
		return right;
	}

	public void setRight(HeroNode right) {
		this.right = right;
	}

	@Override
	public String toString() {
		return "HeroNode [no=" + no + ", name=" + name + "]";
	}

	public HeroNode preOrderSearch(int no) {
		System.out.println("进入前序遍历");
		// 比较当前结点是不是
		if (this.no == no) {
			return this;
		}
		// 1.判断当前结点的左子节点是否为空，如果不为空，则递归前序查找
		// 2.如果左递归前序查找，找到结点，则返回
		HeroNode resNode = null;
		if (this.left != null) {
			resNode = this.left.preOrderSearch(no);
		}
		if (resNode != null) {// 说明我们左子树找到
			return resNode;
		}
		// 1.左递归前序查找，找到结点，则返回，否继续判断，
		// 2.当前的结点的右子节点是否为空，如果不空，则继续向右递归前序查找
		if (this.right != null) {
			resNode = this.right.preOrderSearch(no);
		}
		return resNode;
	}

	// 中序遍历查找
	public HeroNode infixOrderSearch(int no) {
		HeroNode resNode = null;
		if (this.left != null) {
			resNode = this.left.infixOrderSearch(no);
		}
		if (resNode != null) {
			return resNode;
		}
		System.out.println("进入中序查找");
		if (this.no == no) {
			return this;
		}
		if (this.right != null) {
			resNode = this.right.infixOrderSearch(no);
		}
		return resNode;
	}

	// 后序遍历查找
	public HeroNode postOrderSearch(int no) {
		HeroNode resNode = null;
		if (this.left != null) {
			resNode = this.left.postOrderSearch(no);
		}
		if (resNode != null) {
			return resNode;
		}
		if (this.right != null) {
			resNode = this.right.postOrderSearch(no);
		}
		if (resNode != null) {
			return resNode;
		}
		System.out.println("进入后序查找");
		if (this.no == no) {
			return this;
		}
		return resNode;
	}
}

删除结点的代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
package com.nanzx.tree;

public class BinaryTreeDemo {

	public static void main(String[] args) {
		// 先创建一颗二叉树
		BinaryTree binaryTree = new BinaryTree();
		// 创建需要的结点
		HeroNode root = new HeroNode(1, "宋江");
		HeroNode node2 = new HeroNode(2, "吴用");
		HeroNode node3 = new HeroNode(3, "卢俊义");
		HeroNode node4 = new HeroNode(4, "林冲");
		HeroNode node5 = new HeroNode(5, "关胜");

		// 先手动创建该二叉树，后面学习递归的方式创建二叉树
		root.setLeft(node2);
		root.setRight(node3);
		node3.setRight(node4);
		node3.setLeft(node5);
		binaryTree.setRoot(root);

		// 测试一把删除结点
		System.out.println("删除前,前序遍历");
		binaryTree.preOrder(); // 1,2,3,5,4
		binaryTree.delNode(5);
		System.out.println("删除后，前序遍历");
		binaryTree.preOrder(); // 1,2,3,4
	}
}

class BinaryTree {
	private HeroNode root;

	public void setRoot(HeroNode root) {
		this.root = root;
	}

	// 删除结点
	public void delNode(int no) {
		if (root != null) {
			// 如果只有一个root结点, 这里立即判断root是不是就是要删除结点
			if (root.getNo() == no) {
				root = null;
			} else {
				// 递归删除
				root.delNode(no);
			}
		} else {
			System.out.println("空树，不能删除~");
		}
	}

	// 前序遍历
	public void preOrder() {
		if (this.root != null) {
			this.root.preOrder();
		} else {
			System.out.println("二叉树为空，无法遍历");
		}
	}
}

class HeroNode {
	private int no;
	private String name;
	private HeroNode left;
	private HeroNode right;

	public HeroNode(int no, String name) {
		super();
		this.no = no;
		this.name = name;
	}

	public int getNo() {
		return no;
	}

	public void setNo(int no) {
		this.no = no;
	}

	public String getName() {
		return name;
	}

	public void setName(String name) {
		this.name = name;
	}

	public HeroNode getLeft() {
		return left;
	}

	public void setLeft(HeroNode left) {
		this.left = left;
	}

	public HeroNode getRight() {
		return right;
	}

	public void setRight(HeroNode right) {
		this.right = right;
	}

	@Override
	public String toString() {
		return "HeroNode [no=" + no + ", name=" + name + "]";
	}

	// 递归删除结点
	// 1.如果删除的节点是叶子节点，则删除该节点
	// 2.如果删除的节点是非叶子节点，则删除该子树
	public void delNode(int no) {
		// 1.因为我们的二叉树是单向的，所以我们是判断当前结点的子结点是否需要删除结点，而不能去判断当前这个结点是不是需要删除结点.  
		// 2.如果当前结点的左子结点不为空，并且左子结点就是要删除结点，就将this.left = null; 并且就返回(结束递归删除)
		if (this.left != null && this.left.no == no) {
			this.left = null;
			return;
		}
		// 3.如果当前结点的右子结点不为空，并且右子结点就是要删除结点，就将this.right= null ;并且就返回(结束递归删除)
		if (this.right != null && this.right.no == no) {
			this.right = null;
			return;
		}
		// 4.我们就需要向左子树进行递归删除
		if (this.left != null) {
			this.left.delNode(no);
		}
		// 5.则应当向右子树进行递归删除
		if (this.right != null) {
			this.right.delNode(no);
		}
	}

	// 前序遍历
	public void preOrder() {
		System.out.println(this);
		if (this.left != null) {
			this.left.preOrder();
		}
		if (this.right != null) {
			this.right.preOrder();
		}
	}
}

顺序存储二叉树

从数据存储来看，数组存储方式和树的存储方式可以相互转换，即数组可以转换成树，树也可以转换成数组。

顺序存储二叉树的特点: (i表示二叉树中的第几个元素(从0开始编号))

  1. 顺序二叉树通常只考虑完全二叉树
  2. 第i个元素的左子节点为 2 * i + 1
  3. 第i个元素的右子节点为 2 * i + 2
  4. 第i个元素的父节点为 (i-1) / 2

需求: 给定数组为{1,2,3,4,5,6,7}，要求以二叉树前序遍历的方式进行遍历。 前序遍历的结果应当为 1,2,4,5,3,6,7

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
package com.nanzx.tree;

public class ArrBinaryTreeDemo {

	public static void main(String[] args) {
		int[] arr = { 1, 2, 3, 4, 5, 6, 7 };
		ArrBinaryTree tree = new ArrBinaryTree(arr);
		tree.preOrder();
	}
}

class ArrBinaryTree {
	private int[] arr;

	public ArrBinaryTree(int[] arr) {
		super();
		this.arr = arr;
	}

	public void preOrder() {
		preOrder(0);
	}

	public void preOrder(int index) {
		if (arr == null || arr.length < 0) {
			System.out.println("数组为空，不能按照二叉树前序遍历。");
		}
		System.out.print(arr[index]);
		if ((2 * index + 1) < arr.length) {// 防止索引越界
			preOrder(2 * index + 1);
		}
		if ((2 * index + 2) < arr.length) {
			preOrder(2 * index + 2);
		}
	}
}

线索化二叉树

线索化二叉树是为了解决无法直接找到该结点在某种遍历次序中的前驱结点和后继结点的问题。

n个节点的二叉树中含有n+1个空指针域。利用二叉树中的空指针域来存放在某种遍历次序下的前驱和后继结点的指针，这种指针叫“线索”。这种加上了线索的二叉树称为线索二叉树。线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。

为了知道某一结点的left是指向它的左孩子还是指向前驱结点，我们设置了两个标志域：

leftType left data right rightType
0表示left存放左孩子，1表示存放前驱结点 存放左孩子或前驱结点 存放数据 存放右孩子或后继结点 0表示right存放右孩子，1表示存放后继结点 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
package com.nanzx.tree.threadedbinarytree;

public class ThreadedBinaryTreeDemo {

	public static void main(String[] args) {
		// 测试一把中序线索二叉树的功能
		HeroNode root = new HeroNode(1, "tom");
		HeroNode node2 = new HeroNode(3, "jack");
		HeroNode node3 = new HeroNode(6, "smith");
		HeroNode node4 = new HeroNode(8, "mary");
		HeroNode node5 = new HeroNode(10, "king");
		HeroNode node6 = new HeroNode(14, "dim");

		// 二叉树，后面我们要递归创建, 现在简单处理使用手动创建
		root.setLeft(node2);
		root.setRight(node3);
		node2.setLeft(node4);
		node2.setRight(node5);
		node3.setLeft(node6);

		// 测试中序线索化
		ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();
		threadedBinaryTree.setRoot(root);
		threadedBinaryTree.threadedNodes();

		// 测试: 以10号节点测试
		HeroNode leftNode = node5.getLeft();
		HeroNode rightNode = node5.getRight();
		System.out.println("10号结点的前驱结点是 =" + leftNode); // 3
		System.out.println("10号结点的后继结点是 =" + rightNode); // 1

		System.out.println("使用线索化的方式遍历 线索化二叉树");
		threadedBinaryTree.threadedList(); // 8, 3, 10, 1, 14, 6
	}

}

class ThreadedBinaryTree {
	private HeroNode root;
	private HeroNode pre = null;//在递归进行线索化时，pre 总是保留前一个结点

	public void setRoot(HeroNode root) {
		this.root = root;
	}

	public void threadedNodes() {
		this.threadedNodes(root);
	}

	// 中序线索化二叉树
	public void threadedNodes(HeroNode node) {
		// 如果node==null, 不能线索化
		if (node == null) {
			return;
		}
        
		// (一)先线索化左子树
		threadedNodes(node.getLeft());
		// (二)线索化当前结点[有难度]
		// 处理当前结点的前驱结点
		// 以8结点来理解
		// 8结点的.left = null , 8结点的.leftType = 1
		if (node.getLeft() == null) {
			// 让当前结点的左指针指向前驱结点
			node.setLeft(pre);
			// 修改当前结点的左指针的类型,指向前驱结点
			node.setLeftType(1);
		}

		// 处理后继结点
		if (pre != null && pre.getRight() == null) {
			// 让前驱结点的右指针指向当前结点
			pre.setRight(node);
			// 修改前驱结点的右指针类型
			pre.setRightType(1);
		}
		// !!! 每处理一个结点后，让当前结点是下一个结点的前驱结点
		pre = node;

		// (三)再线索化右子树
		threadedNodes(node.getRight());
	}

    	// 遍历线索化二叉树的方法
	public void threadedList() {
		// 定义一个变量，存储当前遍历的结点，从root开始
		HeroNode node = root;
		while (node != null) {
			// 循环的找到leftType == 1的结点，第一个找到就是8结点
			while (node.getLeftType() == 0) {
				node = node.getLeft();
			}

			// 打印当前这个结点
			System.out.println(node);
			// 如果当前结点的右指针指向的是后继结点,就一直输出
			while (node.getRightType() == 1) {
				// 获取到当前结点的后继结点
				node = node.getRight();
				System.out.println(node);
			}
			// 让node指向该结点的右孩子
			node = node.getRight();
		}
	}
}

class HeroNode {
	private int no;
	private String name;
	private HeroNode left;
	private HeroNode right;
	private int leftType;
	private int rightType;

	public HeroNode(int no, String name) {
		super();
		this.no = no;
		this.name = name;
	}

	public int getNo() {
		return no;
	}

	public void setNo(int no) {
		this.no = no;
	}

	public String getName() {
		return name;
	}

	public void setName(String name) {
		this.name = name;
	}

	public HeroNode getLeft() {
		return left;
	}

	public void setLeft(HeroNode left) {
		this.left = left;
	}

	public HeroNode getRight() {
		return right;
	}

	public void setRight(HeroNode right) {
		this.right = right;
	}

	public int getLeftType() {
		return leftType;
	}

	public void setLeftType(int leftType) {
		this.leftType = leftType;
	}

	public int getRightType() {
		return rightType;
	}

	public void setRightType(int rightType) {
		this.rightType = rightType;
	}

	@Override
	public String toString() {
		return "HeroNode [no=" + no + ", name=" + name + "]";
	}
}