线索二叉树小结

在前面总结的链表是一种一对一的关系，而有一种一对多的关系就是树。树也是由一个一个的结点组成的，每一个结点都可以看成一棵树。每一个结点只能有一个父结点，而子结点可以有多个，没有父结点的结点称为根结点，在一棵树中，根结点有且仅有一个。根结点的子结点又可以当成是一棵树，称为子树。没有子结点的结点称为叶子结点。在树结构中，最常用的时二叉树，即每个结点至多只有两颗子树。
现在我们来自定义一颗二叉树，要构造一颗二叉树，首先要有结点，所以首先要先定义一个结点类TreeNode，然后定义结点的属性，即数据域，指向父结点的对象和指向两个子结点的对象以及设置和得到这些属性的相关方法，具体代码如下：
/**
* 二叉树结点类
* @author lenovo
*
*/
public class TreeNode {

private Object obj;
private TreeNode parent;
private TreeNode Lchild;
private TreeNode Rchild;

//构造方法
public TreeNode(Object obj){
this.obj = obj;
}

public Object getObj() {
return obj;
}
public void setObj(Object obj) {
this.obj = obj;
}
public TreeNode getParent() {
return parent;
}
public void setParent(TreeNode parent) {
this.parent = parent;
}
public TreeNode getLchild() {
return Lchild;
}
public void setLchild(TreeNode lchild) {
Lchild = lchild;
}
public TreeNode getRchild() {
return Rchild;
}
public void setRchild(TreeNode rchild) {
Rchild = rchild;
}

}

定义了结点之后，就可以创建根结点以及其他子结点，然后再建立引用关系就可以手工建成一颗二叉树了，具体代码如下所示:
/**
* 手工创建二叉树
* @return：返回树的根结点
*/
public TreeNode createTree(){
//创建根结点
TreeNode root = new TreeNode("根结点");
TreeNode lchild = new TreeNode("左孩子");
TreeNode rchild = new TreeNode("右孩子");
TreeNode llchild = new TreeNode("左左孩子");
TreeNode lrchild = new TreeNode("左右孩子");
TreeNode rlchild = new TreeNode("右左孩子");
TreeNode rrchild = new TreeNode("右右孩子");
TreeNode lllchild = new TreeNode("左左左孩子");
TreeNode llrchild = new TreeNode("左左右孩子");

//建立引用关系
root.setLchild(lchild);
root.setRchild(rchild);

lchild.setParent(root);
rchild.setParent(root);

lchild.setLchild(llchild);
lchild.setRchild(lrchild);

llchild.setParent(lchild);
lrchild.setParent(lchild);

rchild.setLchild(rlchild);
rchild.setRchild(rrchild);

rlchild.setParent(rchild);
rrchild.setParent(rchild);

llchild.setLchild(lllchild);
llchild.setRchild(llrchild);

lllchild.setParent(llchild);
llrchild.setParent(llchild);


return root;
}
这样弄好之后，要检验是不是我们所想要的二叉树，最好的办法就是把它遍历出来。对树的遍历有三种方法，一般都是遍历左子树，再是右子树，根据根结点被遍历的顺序分为先序遍历，中序遍历，后序遍历，这里用中序遍历，具体代码如下：
/**
* 根据根结点遍历二叉树
* @param root：传入的根结点
*/
public void printTree(TreeNode root){

if (root!=null){
TreeNode Lchild = root.getLchild();
TreeNode Rchild = root.getRchild();

//递归
printTree(Lchild);

Object data = root.getObj();
System.out.print(data+"\t");

//递归
printTree(Rchild);

}

}

运行结果为：
左左左孩子
左左孩子
左左右孩子
左孩子
左右孩子
根结点
右左孩子
右孩子
右右孩子

运行结果可以证明是我们想要的二叉树。现在来总结把任意一个整型的一维数组转化为一颗线索二叉树，并且通过遍历二叉树能得到有序的数组。首先要定义遍历的规则，这里是用中序遍历的。然后是把数组的第一个元素当做二叉树的根结点，然后根据根结点的四种情况定义一个方法，即根的子左结点和子右结点都不为空；子左结点不为空，子右结点为空；子左结点为空，子右结点不为空；子左结点和子右结点都为空这四种情况，然后再用递归法，具体代码如下所示：

/**
* 根据根结点的四种情况建立二叉树
* @param num：新结点数据
* @param root：根结点
*/
public void judgeNode(int num,TreeNode root){
if (root.getLchild()==null&&root.getRchild()==null){//如果根结点的左子结点和右子结点都为空
if (num<(Integer)root.getObj()){
TreeNode node = new TreeNode(num);//创建新结点
//建立引用关系
root.setLchild(node);
node.setParent(root);
}else {
TreeNode node = new TreeNode(num);//建立新结点
//建立引用关系
root.setRchild(node);
node.setParent(root);
}

}else if (root.getLchild()!=null&&root.getRchild()==null){//根结点的左子节点不为空
if (num<(Integer)root.getObj()){
//递归
judgeNode(num,root.getLchild());
}else {
TreeNode node = new TreeNode(num);//建立新结点
//建立引用关系
root.setRchild(node);
node.setParent(root);
}
}else if (root.getLchild()==null&&root.getRchild()!=null){//根结点的右子结点不为空
if (num<(Integer)root.getObj()){
TreeNode node = new TreeNode(num);//建立新结点
//建立引用关系
root.setLchild(node);
node.setParent(root);
}else {
//递归
judgeNode(num,root.getRchild());
}

}else if (root.getLchild()!=null&&root.getRchild()!=null){//根结点的左子结点和右子结点都不为空
if (num<(Integer)root.getObj()){
//递归
judgeNode(num,root.getLchild());
}else {
//递归
judgeNode(num,root.getRchild());
}

}

}
最后再遍历数组调用此方法就可以了，代码如下：
/**
* 将数组转化为二叉树
* 定义规则:中序遍历
* @param array：传入的数组
*/
@SuppressWarnings("unused")
public TreeNode arrayToTree(int[] array){
//取数组第一个元素作为根结点
TreeNode root = new TreeNode(array[0]);
if (array==null){
throw  new RuntimeException("数组为空，不能生成树！！");

}else {
for (int i=1;i<array.length;i++){
//调用方法
judgeNode(array[i],root);

}

}

return root;
}
然后随机生成一个数组检验如下：
/**
* 程序入口
* @param args
*/
public static void main(String args[]){
Random rd = new Random();

//实例化对象
Tree t = new Tree();
//随机生成数组
int[] b = new int[10];
for (int i=0;i<b.length;i++){
b[i] = rd.nextInt(100);
}
System.out.println("原有数组：");
for (int i=0;i<arr.length;i++){
System.out.print(arr[i]+"\t");
}
System.out.println();
System.out.println("生成树后，按中序遍历的数组：");
TreeNode root = arrayToTree(arr);
printTree(root);
}

运行结果：
原有数组：
3 52 26 84 93 67 79 49 4 90
生成树后，按中序遍历的数组：
3 4 26 49 52 67 79 84 90 93

至此我们已经对二叉树有了一定的了解，但是知识是无限的，学习还在继续中，总结也会陆续更新。