二叉树的构建和遍历、查询-编程实验室

一、构建二叉树

1.引入：

如图，树的一个节点拥有三个关键部分，分别是左子节点（lChild）、右子节点（rChild）和值（data）。

就拿有序二叉树来说，它的特点是：左子节点的值比父节点小，右子节点比父节点大

例如：构建有序二叉树4871923

2.我们该如何用代码构建构建它呢？

①先定义一个树的Java类，把它里边所含有的成员变量声明出来：

public class TreeNode { public TreeNode lChild; public TreeNode rChild; public Integer data; public TreeNode(Integer data){ this.data = data; } }

类是创建对象的模板，我们先创建了类才能创建对象。

②再创建一个有序二叉树的类，我们把我们要写的构建方法写在里边：

首先创建头指针：

TreeNode root;

然后在下边我们就改写相应的构建二叉排序树的方法了，我们就要先思考它的逻辑，新加入节点该如何用代码实现判断？怎么根据数值大小判断是该往左子节点走还是右子节点走？

a.如果root=null，新插入节点为根节点，如果不为null，那么就进行值得判断，继续往下走；

b.循环判断（用while（true））插入节点的值是否比当前的值小，小则左走，直到左边为null，大则右走，直到右边为null。

//1.判断根节点是否为空 if(root==null){ root=newNode; return; } //2.不为空就循环判断值 while(true){ TreeNode curNode=root; if(curNode.data<newNode.data){ if(curNode.rChild==null){ curNode.rChild=curNode; return; } curNode=curNode.rChild; if(curNode.data>newNode.data){ if(curNode.lChild==null){ curNode.lChild=curNode; return; } curNode=curNode.lChild;

然后我们在Test类中测试该create（）方法就行了

public static void main(String[] args) { BinaryTree bt = new BinaryTree(); bt.create(5); bt.create(3); bt.create(7); bt.create(0); bt.create(4); bt.create(6); bt.create(9);

二、树的遍历

1.我们创建好了树，那么树该怎么实现遍历呢？

首先我们要知道树的遍历有哪些种类：

通常形况下树的遍历自己一个一个走太麻烦了，所以昨天新学了一个方法，感觉还是比较好用的：

画三角法。

就拿刚才的树来说吧：

画三角，把各个节点小树划分出来，之后变成了：

①前序遍历：

前序遍历是根左右，就先看最上边的树对应写出【4 1 8】；

然后再遍历左边1的子节点，1左右是2、3，也就是【4 12 38】；

2和3下边没有子节点，我们就再遍历右边8的子节点，8的左右是7、9，也就是【4 1 2 3 87 9】；

②中序遍历：

中序遍历是左根右，依旧先看上边的树，对应写出【1 4 8】；

然后遍历左边1的子节点，对应写出【2134 8】；

遍历右边写出【2 1 3 4789】；

③后序遍历：

根据上述规则，最后写出【2 3 1 7 9 8 4】；

④层序遍历：

从上到下、从左到右一层一层遍历：【4 1 8 2 3 7 9】；

2.我们已经搞清楚了树的遍历逻辑，那么如何用代码实现树的遍历呢？

①前序遍历

写出相应的前序遍历（beforeOrder）方法，先判断根节点是否为null，空则返回，不为空就分别输出根的值、左子节点的值和右子节点的值：

// 前序遍历 void beforeOrder(TreeNode root) { if (root == null) { return; } System.out.println(root.data); beforeOrder(root.lChild); beforeOrder(root.rChild); }

②中序遍历

写出相应的中序遍历（inOrder）方法，先判断根节点是否为null，空则返回，不为空就分别输出左子节点的值、根的值和右子节点的值：

//后序遍历 void afterOrder(TreeNode root) { if (root == null) { return; } afterOrder(root.lChild); afterOrder(root.rChild); System.out.println(root.data); }

③后序遍历

写出相应的中序遍历（afterOrder）方法，先判断根节点是否为null，空则返回，不为空就分别输出左子节点的值、右子节点的值和根节点的值：

//后序遍历 void afterOrder(TreeNode root) { if (root == null) { return; } afterOrder(root.lChild); afterOrder(root.rChild); System.out.println(root.data); }

④层序遍历

a.初始化队列，根节点入队；

b.循环出队节点，访问该节点；

c.把该节点的左、右子节点（下一层）入队；

d.重复步骤 b和c，直到队列为空。

//层序遍历 void levelOrder(TreeNode root) { LinkedList<TreeNode> queue=new LinkedList<>(); queue.add(root); while(!queue.isEmpty()){ root=queue.pop(); System.out.println(root.data); if(root.lChild!=null){ queue.add(root.lChild); } if(root.rChild!=null){ queue.add(root.rChild); } } }

三、树的查询

1.查询树的逻辑是什么？

①利用二叉搜索树 “左小右大” 的特性，通过递归缩小查找范围；

②递归终止条件：找到目标节点（返回节点）或遍历到空节点（返回 null）；

③分岔逻辑：目标值大于当前节点则查右子树，小于则查左子树，实现 “二分式” 高效查找。

//节点查询 public TreeNode searchNode(TreeNode root,Integer target){ if(root==null||root.data==target){ return root; } if(target>root.data){ return searchNode(root.rChild,target); }else{ return searchNode(root.lChild,target); } }

Test代码

运行结果