链表与树的总结

链表总结
链表是由一个个节点组成的，就像是一个火车，每个节点都可以类似的看成是一个车厢。而节点里面储存的则是数据对象还有下一个节点的地址。链表可以是单向链表，双向链表，还有循环链表，区别就是节点里面存储的节点地址是父节点和子节点还是只有子节点。而循环链表则是尾指针的下个节点是头指针，这样链表就连成一个圈了。

节点：
节点里面的属性有子节点父节点，还有存储的对象。

链表跟队列相似，但其在内存里存储是不连续的。同样也拥有增删改查的方法。
增加节点：
分两种情况：一种是链表为空，另外一种是链表不为空
public void add(Yuangong y) {
LinkNode<Yuangong> ll = new LinkNode<Yuangong>(y);
if (front == null) { // 当此链表是空的时候，头尾节点都是同一个节点ll
front = ll;
last = ll;
size++; // 增加一个节点长度加一
} else { // 如果不是空链表，那么每次添加都在链表末尾添加
LinkNode<Yuangong> temp = last;// 把原先为尾节点的节点取出来
ll.setParent(temp);// 先给ll节点设置父节点temp
temp.setChild(ll);// 给原先是尾节点的temp设置子节点是ll
last = ll; // 在设置ll为尾节点
size++;
}
}

删除节点：
public void remove(int index) {
if (index < 0 && index > size - 1) {
System.out.println("您输入的索引值有错误!!");
}
if (index == 0) {
// 当删除的是头节点，则把头节点往下移动以为
front = front.getChild();
size--;
}
if (index == size - 1) {
// 当删除的是尾节点，则把尾节点往前移动一位
last = last.getParent();
last.setChild(null);// 尾节点的子节点为null
size--;
} else {
LinkNode<Yuangong> ll = front;
for (int i = 0; i < index; i++) {
ll = ll.getChild();
}
// 为ll节点的子节点设置父节点，为ll的父节点设置子节点
ll.getChild().setParent(ll.getParent());
ll.getParent().setChild(ll.getChild());
size--;
}
}
此方法值得注意的是，对于子节点与父节点的设置，可能会出错，可能子节点和父节点同时指向自己。该注意点在其他方法里也同样值得注意！

还有一个方法是对链表进行排序。我采用的是冒泡法，而排序也只是对节点存储的对象进行调换而已。代码如下：
public void sortLinkList() {
LinkNode<Yuangong> ll = front;
for(int i=0;i<size;i++){
LinkNode<Yuangong> kk= ll;
for(int j=i+1;j<size;j++){
if(ll.getYuanG().getMoney()>kk.getChild().getYuanG().getMoney()){//当父节点小于子节点的员工对象的工资，两个进行对调
Yuangong y1=ll.getYuanG();//取得父节点的员工对象
Yuangong y2 = kk.getChild().getYuanG();//取得子节点的员工对象
//两个节点的对象分别调换
ll.setYuangong(y2);
kk.getChild().setYuangong(y1);
}
kk=kk.getChild();//子节点往后移动
System.out.println(ll.getYuanG().getNum()+"号员工");
}
ll=ll.getChild();//前一节点进行往后移动
}
}


树的总结：
之前听胡老师扯的，人生就是一棵大树，你要怎么建，才会使得这棵大树更好，枝叶更繁茂。听说建树这个词就是来自搞编程的人嘴里说出来的。树有着树根还有树叶，枝干等等。树也是由节点构成的，节点分为三种，分别是叶子节点，根节点还有既不是叶子节点，也不是根节点的节点（可理解为树的分叉）。树可以有多个分支，多个叶子，但根只能有一个。以后用到遍历节点的时候就从它开始，相当于链表的头节点。
树的深度：指的是根节点到最远的叶子节点之间的路径条数。
树的高度：树的深度加一
树的度：表示父节点有几个子节点
下面来讲一讲二叉树：
二叉树中节点最多只有两个，分别是左子节点和右子节点。由于计算机位是0，1两个组成，所以二叉树的运用比较方便和广泛。二叉树的节点也存储值的对象，存储左子树右子树的地址，可能也存储着父节点。

二叉树的遍历分为四种，分别是前序，中序，后序，还有层次遍历。其中较常用到的是前序中序还有后序。这三种遍历方法只是语句调换了一下顺序，程序输出的结果就会不一样。
前序的遍历顺序：先找树节点储存的对象值，然后遍历左子树，在遍历右子树
中序的遍历顺序：先遍历左子树，然后输出节点的对象值，在遍历右子树
后序的遍历顺序：先遍历左子树，然后遍历右子树，输出节点的对象值。

方法 preorder(TreeNode t){
If(t.lchild==null&&t.rchild==null){
Return null;
}
Preorder(t.lchild);
System.out.println(t.getdata());
Preorder(t.rchild);
//此方法就是中序遍历，先一直找左子节点，然后取得后返回输出节点的值，在返回回到父节点输出父节点的值，然后遍历右子树，开始找左子节点，如此循环，直到把整个树都遍历完成了后，每个节点就都能取到了。
而前序和后序遍历则是改变一下三条语句的位置，输出语句分别放在第一句和最后一句，就使得输出的内容不一样了。说起来也是蛮有意思的。

关于使用二叉树进行算术式的运算：
思路，先把树给建立好，对各个节点进行父子左右节点的设置。然后叶子节点存放的都是数值，而其他的不是根节点和叶子节点的存放的则是运算符+—×/。采用递归方法遍历，然后分四种情况把数值进行相应的运算，得出数值，把该数值存放到父节点进行下一轮的运算。由此一来，树的遍历完成，相应的运算结果也将出来。
public static int count(TreeNode<String> t){
//当此节点是叶子节点的时候，则返回子节点自己
if(t.getLchild()==null&&t.getRchild()==null){
return Integer.parseInt(t.getObj().toString());
}
else{
int k = 0;
int value1=count(t.getLchild());
//采用递归思想，对左子树进行遍历
System.out.print(t.getObj());
//输出节点的存储字符
int value2=count(t.getRchild());
//分四种情况来，加减乘除四种方法
if(t.getObj().equals("*")){
return value1*value2;
}
if(t.getObj().equals("/")){
return value1/value2;
}
if(t.getObj().equals("+")){
return value1+value2;
}
if(t.getObj().equals("-")){
return value1-value2;
}
}
return 0;

}