数据结构Day02树的学习_创建一个node类,数据结构实现结点类的基本方法。

树的实现JAVA

1·新建一个节点类(Node)

新建一个节点类中有a.值b(no).左子树(left)c.右子树(right)

class Node{
int no;
Node left;
Node right;
Node(int no){
this.no = no;
}
}
1
2
3
4
5
6
7
8

遍历方式
a.先序遍历
b.中序遍历
c.后序遍历 三者的区别就是父节点的遍历顺序 先序遍历先遍历父节点 中序就是中间遍历父节点

//先序遍历
public void preOrder(){
if(this!=null){
System.out.println(this);
}
if(this.left!=null){
this.left.preOrder();
}
if(this.right!=null){
this.right.preOrder();
}
}
1
2
3
4
5
6
7
8
9
10
11
12

//中序和后序就是把位置换一下就行

//中序遍历
public void midOrder(){
if(this.left!=null){
this.left.midOrder();
}
if(this!=null){
System.out.println(this);
}
if(this.right!=null){
this.right.midOrder();
}
}
1
2
3
4
5
6
7
8
9
10
11
12

2.树的类(binaryTree)

树需要一个初始节点

class binaryTree{
Node root;
setRoot(Node root){
this.root = root;
}
}
1
2
3
4
5
6

树进行遍历

//前序遍历  其他两种遍历相似
public void preOrder(){
if(this.root!=null){
this.root.preOrder();//这里是用的节点里的方法
}else{
System.out.println("这个树是空的");
}
}
1
2
3
4
5
6
7
8

树的查找

//节点下的方法
public Node preOrderSearch(int no){
Node temp= null;  //临时用于存放结果
if(this.no==no){
return this;
}
if(this.left!=null){
temp = this.left.preOrderSearch(no);
}
if(temp!=null){
return temp;
}
if(this.right!=null){
temp = this.right.preOrderSearch(no);
}
if(temp!=null){
return temp;
}
return temp;
}


//树下的方法
public Node preOrderSearch(int no){
Node temp = null;
if(root!=null){
temp = root.preOrderSearch(no);//节点的方法
}
return temp;
}
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

树的删除

//节点下的方法
public void  delete (int no){
if(this.left!=null&&this.left.no==no){
this.left  = null;
return;
}
if(this.right!=null&&this.right.no==no){
this.right = null;
return;
}
if(this.left!=null){
this.left.delete(no);
}
if(this.right!=null){
this.right.delete(no);
}
}
//树下的方式
public void delete(int no){
if(this.root !=null){
if(this.root.no == no){
this.root = null;
}else{
this.root.delete(no);
}
}else {System.out.println("树是空的^")}
}
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

3.树的线索化

就是在树上增强一个功能，本质上还是一个树
1.节点上新增leftype和rightype两个属性，用于区分连接的是左右子树还是前驱后继节点
2.树的线索化和删除一样需要的定位他的前一个节点，所有需要一个pre节点来指向需要操作的节点的前一个节点；在树里新增一个pre属性；

//这里用的是中序线索化
public void threadedTree(Node node){
if(node!=null){
threadedTree(node.getLeft);

if(node.getLeft==null){
node.setLeft=pre;
node.setLefType = 1;
}

if(pre!=null&&this.getRight==null){
pre.setRight = node;
pre.setRighType = 1;
}

pre = node;
threadedTree(node.getRight);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

4.树的顺序存储

1.需要一个数组
2.规律a.节点的左子树的在数组的下标为n2+1，右子树为n2+2

class arrTree{
int[] arr;
arrTree(int[] arr){
this.arr = arr;
}
public void preOrder(int index){

if(arr==null||arr.lenght==0){
return;}
System.out.println(arr[index]);
}
if(index*2+1<arr.length){
preOrder(index*2+1)
}
if(index*2+2<arr.length){
preOrder(index*2+2)
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18