嚎羸的博客

因为Hexo是静态博客,部署多有不便,建议查看我的语雀文档

0%

10、树基础部分

树的概述

为什么需要树这种数据结构

我们之前学过数组和链表

数组的查找快,但是对于增加值的时候要整体移动到新数组上,效率低。

链表这种数据结构插入的时候十分快,但是在检索的时候就比较慢了。

虽然我们在插入和检索的时候要根据需求来选择数据结构。

但是我们还是在想,有没有一种数据结构插入又快,检索又快。其实是有的,这就是我们的树。

树这种数据结构可以提高数据的存储和查找的效率,比如利用二叉排序树,既可以保证数据的检索,同时可以保证数据的插入、删除、修改的速度。


树的基本术语

树的基本术语

image-20201228093105816

概念 意义
节点 节点就是对象,其中A、B、C、D、E、F、G、H都是节点
父节点 D就是H的父节点、B是D的父节点、A是B的父节点。
也就是说,节点的上一级叫做父节点
子节点 和父节点的概念对应,父节点的下一级叫做子节点。
B是A的子节点、D是B的子节点、H是D的子节点。
根节点 没有父节点的节点就叫做根节点
叶子节点 没有子节点的节点就叫做叶子节点
节点的权 就是节点的值
路径 从根节点到该节点的路线。比如找到D应该A–>B–>D
比如A就是第一层,B和C位于第二层,DEFG位于第三层,H位于第四层
子树 我们看到,在虚线的三角形中,D和E两者也可以叫做子树。
可以叫做A的子树,可以叫做B的子树。在这颗子树中,D为根节点。
树的高度 一颗树有多少层
森林 多颗子树构成森林

二叉树

二叉树的概念

二叉树的意思就是,一个节点只能有两个子节点,并且子节点要明确分为左子节点和右子节点

image-20201228094529650

假如二叉树的所有叶子节点都==在最后一层或者倒数第二层==,并且==最后一层的叶子节点在左边连续==,==倒数第二层的叶子节点在右边连续==,我们称为==完全二叉树==

image-20201228095023594

连续这个概念很容易让人懵逼,连续的意思就是说每一个叶子节点都挨着,比如71挨着61、61挨着15。

但是假如把61这个节点删除,那么71不挨着15。假如把71去掉,剩下61和15,那也不叫连续。

假如我去掉81,那也不叫连续。

假如二叉树的所有叶子节点==都在最后一层==,并且节点的总数为2^n^-1(n为层数),则我们称为==满二叉树==

image-20201228095015131

满二叉树是一种特殊的完全二叉树

对于完全二叉树也可以这样想:完全二叉树去掉倒数第一层的叶子节点,剩下的也是一颗满二叉树

前序遍历、中序遍历、后序遍历

前序遍历

先遍历父节点,再遍历左子树,再遍历右子树

中序遍历

先遍历左子树,再遍历父节点,再遍历右子树

后序遍历

先遍历左子树,再遍历右子树,再遍历父节点

总而言之,只需要看父节点的输出位置就可以判断是哪种遍历了,而左边肯定先遍历。

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
/**
* 二叉树的节点
*/
class HeroNode {

//信息
private Integer id;
private String name;

//左子树
private HeroNode left;
//右子树
private HeroNode right;

public HeroNode() {
}

public HeroNode(Integer id, String name) {
this.id = id;
this.name = name;
}

/**
* 前序遍历
*/
public void preOrder() {

//输出父节点
System.out.println(this);

//假如左子树不为null,那么递归左子树
if (this.left != null) {
this.left.preOrder();
}

//假如右子树不为null,那么递归右子树
if (this.right != null) {
this.right.preOrder();
}
}

/**
* 中序遍历
*/
public void infixOrder() {
//假如左子树不为null,那么递归左子树
if (this.left != null) {
this.left.preOrder();
}

//输出父节点
System.out.println(this);

//假如右子树不为null,那么递归右子树
if (this.right != null) {
this.right.preOrder();
}
}

/**
* 后序遍历
*/
public void postOrder() {
//假如左子树不为null,那么递归左子树
if (this.left != null) {
this.left.preOrder();
}

//假如右子树不为null,那么递归右子树
if (this.right != null) {
this.right.preOrder();
}

//输出父节点
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
class BinaryTree {

private HeroNode root;

public BinaryTree() {
}

public BinaryTree(HeroNode root) {
this.root = root;
}

/**
* 前序遍历
*/
public void preOrder() {
if (this.root != null) {
this.root.preOrder();
return;
}
System.out.println("二叉树为空,不可遍历");
}

/**
* 中序遍历
*/
public void infixOrder() {
if (this.root != null) {
this.root.infixOrder();
return;
}
System.out.println("二叉树为空,不可遍历");
}

/**
* 后序遍历
*/
public void postOrder() {
if (this.root != null) {
this.root.postOrder();
return;
}
System.out.println("二叉树为空,不可遍历");
}

}

二叉树的前序查找、中序查找、后序查找

查找其实和遍历一模一样,只不过查找是找到之后就结束查找

现在我们搞这样一个关系:

image-20201228143345775

假如我现在要查询编号为5的节点,也就是关胜,那么以前序查找为例:

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
public class BinaryTreeDemo {
public static void main(String[] args) {
BinaryTree binaryTree = new BinaryTree();

HeroNode one = new HeroNode(1, "宋江");
HeroNode two = new HeroNode(2, "吴用");
HeroNode three = new HeroNode(3, "卢俊义");

one.setLeft(two);
one.setRight(three);

HeroNode four = new HeroNode(4, "林冲");
HeroNode five = new HeroNode(5, "关胜");

three.setLeft(five);
three.setRight(four);

binaryTree.setRoot(one);

//前序查找
HeroNode heroNode = binaryTree.preOrderSearch(5);

if (heroNode != null) {
System.out.println(heroNode.toString());
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class BinaryTree {

private HeroNode root;

public BinaryTree() {
}

public BinaryTree(HeroNode root) {
this.root = root;
}

/**
* 前序查找对应的HeroNode
*
* @param id HeroID
* @return Hero
*/
public HeroNode preOrderSearch(Integer id) {

return this.root.preOrderSearch(id);
}

}
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
/**
* 二叉树的节点
*/
class HeroNode {

//信息
private Integer id;
private String name;

//左子树
private HeroNode left;
//右子树
private HeroNode right;

public HeroNode() {
}

public HeroNode(Integer id, String name) {
this.id = id;
this.name = name;
}

/**
* 前序查找对应的HeroNode
*
* @param id Hero的ID号码
* @return Hero
*/
public HeroNode preOrderSearch(Integer id) {

//假如当前节点的值为要查询的值,那么直接返回即可
if (this.id.equals(id)) {
return this;
}

//定义一个中间变量
HeroNode mid = null;

//假如左子节点不为null,那么向左进行遍历
if (this.left != null) {
mid = this.left.preOrderSearch(id);
}
//假如查询到了结果,那么直接返回即可
if (mid != null) {
return mid;
}

//假如右子节点不为null,那么向右进行遍历
if (this.right != null) {
mid = this.right.preOrderSearch(id);
}

//无论右子节点有没有查询到最终的值,都返回null即可,最坏的结果就是查不到
return mid;
}
}

二叉树的删除

我们现在规定:

1、假如删除的节点是一个叶子节点,那么直接删除

2、假如删除的节点是一个非叶子节点,那么删除该节点和它所代表的子树

现在我们先来一个比较简单的,等到后面讲其他树的时候,我们再具体来讲应该如何删除

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
class BinaryTree {

private HeroNode root;

public BinaryTree() {
}

public BinaryTree(HeroNode root) {
this.root = root;
}

/**
* 前序遍历
*/
public void preOrder() {
if (this.root != null) {
this.root.preOrder();
return;
}
System.out.println("二叉树为空,不可遍历");
}

/**
* 删除节点
*
* @param id 节点的ID
* @return 返回是否删除成功
*/
public boolean delNode(Integer id) {

if (this.root == null) {
System.out.println("二叉树为null");
}

if (this.root.getId().equals(id)) {
this.root = null;
return true;
}

return this.root.delNode(id);
}

}
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
/**
* 二叉树的节点
*/
class HeroNode {

//信息
private Integer id;
private String name;

//左子树
private HeroNode left;
//右子树
private HeroNode right;

public HeroNode() {
}

public HeroNode(Integer id, String name) {
this.id = id;
this.name = name;
}
/**
* 前序遍历
*/
public void preOrder() {

//输出父节点
System.out.println(this);

//假如左子树不为null,那么递归左子树
if (this.left != null) {
this.left.preOrder();
}

//假如右子树不为null,那么递归右子树
if (this.right != null) {
this.right.preOrder();
}
}

/**
* 删除节点
*
* @param id 节点的ID
* @return 是否删除成功
*/
public boolean delNode(Integer id) {

/*
* 首先进行左边节点的判断
* 假如左边节点不为null并且查询到是左边节点
* 那么直接置空并返回
*/
if (this.left != null && this.left.id.equals(id)) {
this.left = null;
return true;
}


/*
* 假如左边节点不是我们想要的值,那么进行右边节点的判断
* 同样的,假如右边节点不为null并且是我们想要的值,那么直接将右边节点置空并且返回
*/
if (this.right != null && this.right.id.equals(id)) {
this.right = null;
return true;
}

// 定义一个变量,保存递归回来的值
boolean flag = false;

/*
* 假如左右两边的节点都不是我们想要的值,我们首先向左边进行递归
*/
if (this.left != null) {
flag = this.left.delNode(id);
}


/*
* 假如我们得到的flag为true,说明已经删除了节点,那么直接返回即可
* 假如我们得到的flag为false,那么说明在左边并没有将节点删除,还需要向右边进行遍历
* 在向右边进行遍历的时候,无论是什么结果都应该返回了
*/
if (flag) {
return true;
}

/*
* 假如右边的节点不为null,那么才进行遍历,否则直接返回false
*/
if (this.right != null) {
return this.right.delNode(id);
}

return false;
}
}
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
public class BinaryTreeDemo {
public static void main(String[] args) {
BinaryTree binaryTree = new BinaryTree();

HeroNode one = new HeroNode(1, "宋江");
HeroNode two = new HeroNode(2, "吴用");
HeroNode three = new HeroNode(3, "卢俊义");

one.setLeft(two);
one.setRight(three);

HeroNode four = new HeroNode(4, "林冲");
HeroNode five = new HeroNode(5, "关胜");

three.setLeft(five);
three.setRight(four);

binaryTree.setRoot(one);

binaryTree.preOrder();

System.out.println("----------------删除----------------");
binaryTree.delNode(5);

binaryTree.preOrder();

}
}

顺序存储二叉树

概念

什么是顺序存储二叉树

我们的树其实可以转换为数组,而数组也可以转换为树

image-20210104164030681

上图中是树转换为数组的形式,也可以叫做数组转换为树的形式

现在有一个需求:我将树转换为数组,仍然可以依照某几种规则来进行前序遍历,中序遍历和后序遍历

那么能够实现上面这种需求的,就是顺序存储二叉树

顺序存储二叉树的特点

1、顺序二叉树通常只考虑完全二叉树

2、第n个元素的左子节点的下标为 2 * n + 1(n在这里指的是转换为数组之后的下标,也就是从0开始的数组节点)

3、第n个元素的右子节点的下标为2 * n + 2

4、第n个元素的父节点的下标为 (n - 1) / 2

举个例子,还是我们刚才的图

image-20210104164030681

在图中,树的下标为0-6,那么我们举一个例子,就以下标为1,值为2的树节点为例子:

第1个元素(也就是下标为1的节点)

  • 左子节点为 2 * 1 + 1 = 3,也就是下标为3,值为4的节点

  • 右子节点为 2 * 1 + 2 = 4,也就是下标为4,值为5的节点

  • 父节点为( 2 - 1 ) / 2 = 0,也就是根节点

代码实现

需求:现在有一个数组:int[] arr = {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
class ArrayBinaryTree {

// 数组节点的存储
int[] arr;

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

public void preOrder(int index) {
if (arr == null || arr.length <= 0) {
System.out.println("数组中必须有值!");
return;
}

// 左子节点
int left = 2 * index + 1;

System.out.print(arr[index] + " ");

if (left <= arr.length - 1) {
preOrder(left);
}

// 右子节点
int right = 2 * index + 2;
if (right <= arr.length - 1) {
preOrder(right);
}
}

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
package com.howling;

/**
* 顺序存储二叉树
*/
public class ArrayBinaryTreeDemo {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5, 6, 7};

ArrayBinaryTree tree = new ArrayBinaryTree(arr);

// 1 2 4 5 3 6 7
tree.preOrder(0);
}
}

线索化二叉树

线索化二叉树概述

问题描述

我们先来看一个数列:{1,3,6,8,10,14},我们将这个数列构建成一个线索化二叉树,如图:

image-20210104172013857

我们当我们使用中序遍历的时候,发现它的输出是这样的:8、3、10、1、14、6

我们发现对于6、8、10、14这几个节点的左右指针并没有完全利用上,这在一定程度上就造成了一种资源的浪费

假如我们想要充分地利用各个节点的左右指针,让各个节点可以指向自己的前后节点怎么办?

这就是线索二叉树的作用

线索二叉树

1、现在有一个完全二叉树,一共有n个节点,那么对于这棵树来讲,它的空指针域为n+1

image-20210105100425757

比如上面这个树,它的节点一共有六个,但是它的空指针域有7个

2、一个节点的前一个节点称为前驱结点,一个节点的后一个节点称为后继结点

3、假如我们可以利用这些空指针域,存放当前节点在某种遍历顺序下的前驱结点和后继结点的指针,那么这种附加的指针就叫做线索,这种行为我们称之为线索化

image-20210105101031342

我们可以看到,在上图中,假如我们以中序遍历的方式去遍历这个树,那么对于节点8、3、10,它们遍历的顺序应当是8、3、10,那么节点8的右子节点(后继结点)指向3,而节点10的左子节点(前驱结点)指向3,那么这种前驱节点和后继结点就叫做线索,这种行为叫做线索化

4、附加上了线索的二叉链表我们称为线索链表,对应的二叉树我们称为线索二叉树。根据线索性质的不同,我们可分为前序线索二叉树中序线索二叉树后序线索二叉树

线索化二叉树应用

现在有一棵树,要求我们进行中序线索化

image-20210105102033382

首先我们要明白一件事情:这棵树的中序遍历之后应当是什么样子,它的中序遍历应该是:8、3、10、1、14、6

那么我们按照前面讲到的知识,进行线索化,将它变为中序线索二叉树

1、对于8来讲,它没有前驱节点,后继结点是3

2、对于10来讲,它的前驱节点就是3,后继结点就是1

3、对于14来讲,它的前驱节点是1,后继结点是6

4、对于6来讲,它的前驱节点是14,没有后继结点

那么它的中序线索化应当是这样子的:

image-20210105102638614

我们发现一个问题:

当线索化二叉树之后,节点的left和right,有可能是前驱和后继节点,也有可能是左右子节点


线索化二叉树应用

因为线索化二叉树可能有些难以理解,所以我们根据上图来走一遍基本的代码实现

还是之前的图片

image-20210105102638614

1、准备三个指针:

  • 一个指针是pre,指向当前节点的上一个指针
  • 一个指针是leftType,用于标识当前节点的left节点是前驱节点还是左子树
  • 一个指针是rightType,用于标识当前节点的right节点是后继结点还是右子树

2、在一开始pre为null,当前指针为8

  • 判断pre是否为null–>pre不为null–>令pre的right指向当前节点–>形成pre的后继节点–>类型标记为后继节点

  • 判断当前指针的left是否为null–>left为null–>令left指向pre–>形成前驱节点,并左标记

  • pre指向当前节点,当前节点指向下一个节点

3、pre为8,当前节点为3

  • left和right都不为null–>不进行处理
  • pre指向当前节点,当前节点指向下一个节点

4、pre为3,当前节点为10

  • 判断pre是否为null–>pre不为null–>判断pre的right是否为null–>不为null,不进行处理(不能形成pre的后继结点,因为)
  • 判断当前节点的left是否为null–>left为null,指向pre
  • pre指向当前节点,当前节点指向下一个节点

5、……

思路有了就行,文字太多不讲了,直接上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 节点
class HeroNode {
// 节点基本信息
private Integer id;

// 规定:leftType和rightType为0时代表为左右子树,为1时代表前驱后继节点
private Integer leftType = 0;
private Integer rightType = 0;

// 当前节点的左右节点
private HeroNode left;
private HeroNode right;

public HeroNode(Integer id) {
this.id = id;
}
}
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
// 树
class ThreadedBinaryTree {

// 根节点
private HeroNode root;

// 当前节点的前置节点,默认为null
private HeroNode pre;

public ThreadedBinaryTree(HeroNode root) {
this.root = root;
}

/**
* 二叉树中序线索化
*
* @param node 要进行线索化的节点
*/
public void threadNodes(HeroNode node) {

// 判断node是否为null,假如为null,那么直接返回
if (node == null) {
return;
}

/*
* 根据我们所说的中序线索化
* 我们的顺序应当为 前置节点 --> 当前节点 --> 后继结点
*/

// 1、进行前驱节点的线索化
threadNodes(node.getLeft());

// 2、 进行当前节点的线索化

/*
* 根据我们之前分析的,进行当前节点的线索化要进行以下几个步骤:
* 1、判断pre是否为null
* - 假如为null,那么不进行处理
* - 假如不为null,判断pre的right是否为null
* - 假如pre的right为null,那么将当前节点转换为pre的后继节点
*
* 2、判断当前节点的left是否为null
* - 假如为null,令left指向pre,形成前驱结点
*
* 3、pre指向当前节点
*/
if (pre != null && pre.getRight() == null) {
pre.setRight(node);
pre.setRightType(1);
}

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

pre = node;
// 3、 进行后继结点的线索化
threadNodes(node.getRight());
}
}
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
public class ThreadedBinaryTreeDemo {
public static void main(String[] args) {
HeroNode root = new HeroNode(1);

HeroNode three = new HeroNode(3);
HeroNode six = new HeroNode(6);

HeroNode eight = new HeroNode(8);
HeroNode ten = new HeroNode(10);
HeroNode fourteen = new HeroNode(14);

root.setLeft(three);
root.setRight(six);

three.setLeft(eight);
three.setRight(ten);

six.setLeft(fourteen);

ThreadedBinaryTree tree = new ThreadedBinaryTree(root);
tree.threadNodes(root);

// 1--HeroNode{id=3, leftType=0, rightType=0}
System.out.println(eight.getRightType() + "--" + eight.getRight());

// 1--HeroNode{id=3, leftType=0, rightType=0}
System.out.println(ten.getLeftType() + "--" + ten.getLeft());

// 1--HeroNode{id=1, leftType=0, rightType=0}
System.out.println(ten.getRightType() + "--" + ten.getRight());
}
}

image-20210105134653067


遍历线索化二叉树

线索化二叉树因为重新排列了我们节点的左右指针,所以按照以前的方法遍历肯定是不行的,所以我们需要来一个新的遍历方式,并且遍历之后的结果应当是你线索化之前的结果,举个例子:我们中序线索化的二叉树,那么我们遍历之后的结果应该和中序遍历二叉树的结果一模一样

image-20210105134653067

还是以这张图为例子:

中序遍历的结果应当为:8、3、10、1、14、6,那么我们进行线索化二叉树的遍历之后,应当和这个结果完全一致

还是先说一下基本的思路:

1、在这颗二叉树上向左寻找(因为是中序遍历),找到一个当前节点的左节点的leftType==1的节点

2、打印该节点,向右寻找节点,只要rightType==1,那么就打印,然后继续重复步骤2

3、到达第三步说明当前所在节点的rightType==0,那么令当前节点为右节点,回到第一步

4、进入第四步说明我们的线索二叉树全部都遍历完成了

对于线索二叉树我只能说一句鬼才设计,这玩意儿可比递归的效率高多了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class HeroNode {
// 节点基本信息
private Integer id;

// 规定:leftType和rightType为0时代表为左右子树,为1时代表前驱后继节点
private Integer leftType = 0;
private Integer rightType = 0;

// 当前节点的左右节点
private HeroNode left;
private HeroNode right;

public HeroNode(Integer id) {
this.id = id;
}
}
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
class ThreadedBinaryTree {

// 根节点
private HeroNode root;

// 当前节点的前置节点,默认为null
private HeroNode pre;

public ThreadedBinaryTree(HeroNode root) {
this.root = root;
}

/**
* 线索二叉树遍历
*
* @param node
*/
public void threadOrder(HeroNode node) {

if (node == null) {
return;
}

HeroNode mid = node;

while (mid != null) {
while (mid.getLeftType() != 1) {
mid = mid.getLeft();
}

System.out.println(mid);

while (mid.getRightType() == 1) {
mid = mid.getRight();
System.out.println(mid);
}

mid = mid.getRight();
}
}
}
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
public class ThreadedBinaryTreeDemo {
public static void main(String[] args) {
HeroNode root = new HeroNode(1);

HeroNode three = new HeroNode(3);
HeroNode six = new HeroNode(6);

HeroNode eight = new HeroNode(8);
HeroNode ten = new HeroNode(10);
HeroNode fourteen = new HeroNode(14);

root.setLeft(three);
root.setRight(six);

three.setLeft(eight);
three.setRight(ten);

six.setLeft(fourteen);

ThreadedBinaryTree tree = new ThreadedBinaryTree(root);
// 二叉树的线索化在前面线索化二叉树应用部分
tree.threadNodes(root);

tree.threadOrder(root);
}
}