二叉树概念及基本功能实现

一、二叉树概述

二、代码实现一棵二叉树：

三、二叉树的遍历

四、二叉树遍历代码实现

1.先序遍历：

2.中序遍历：

3.后序遍历：

4.层次遍历（一层一层遍历）：

5.main方法执行

五、二叉树的查询和删除：

1.二叉树的查询：

2.二叉树的删除：

3.main方法执行：

六、二叉树深度的计算

七、线索化二叉树：

八、堆排序概述：

一、二叉树概述

二叉树是每个节点最多有两个子树的树结构，也就是说树的度是2.

满二叉树：每一层的结点数都达到最大值。

完全二叉树：若设二叉树的深度为k，除第k层外，其他各层（1~k-1）的结点数都达到最大个数，第k层所有的结点都连续集中在最左边，这就是完全二叉树。

注：完全二叉树的话，所有的结点都连续集中在最左边，也就是如下图所示，右子节点可以没有，但如果右子节点有的话，则左子节点必须存在。下图中如果叶子结点只有4结点，5、6、7结点没有的话，也是完全二叉树。

二、代码实现一棵二叉树：

1.定义结点 2.创建一棵树，手动创建子节点 3.定义一个根节点

public class BinaryTree {//定义一个根节点Node root;//定义结点类public class Node{//存储数据节点Object item;//左子节点Node left;//右子节点Node right;public Node(Object obj){this.item = obj;}}//创建一棵树public void createTree(){//创建根节点root = new Node(1);//创建左子节点Node leftNode = new Node(2);//创建右子节点Node rightNode = new Node(3);//把左右子节点关联到根节点root.left = leftNode;root.right = rightNode;//创建左子节点的左子节点Node leftLeftNode = new Node(4);//创建左子节点的右子节点Node leftRightNode = new Node(5);//把左节点的左右子节点关联到左节点leftNode.left = leftLeftNode;leftNode.right = leftRightNode;//创建右子节点的左子节点Node rightLeftNode = new Node(6);//创建右子节点的右子节点Node rightRightNode = new Node(7);//把右结点的左右子节点关联到右节点rightNode.left = rightLeftNode;rightNode.right = rightRightNode;}
}

三、二叉树的遍历

注：每次遍历的时候，大化小，也就是把大的树化成一颗颗小的树。

比如先序遍历：根左右，先遍历根“1”，然后左子树“2 4 5”作为整体充当根节点的左子树，再进行先序遍历。最后遍历结果就是 1 245 367

四、二叉树遍历代码实现

1.先序遍历：

//实现先序遍历public void preTrival(Node node){//退出的条件if (node == null){return;}//先遍历根节点System.out.print(node.item+" ");//遍历左子树preTrival(node.left);//遍历右子树preTrival(node.right);}

2.中序遍历：

//实现中序遍历public void midTrival(Node node){//退出的条件if (node == null){return;}//遍历左子树midTrival(node.left);//先遍历根节点System.out.print(node.item+" ");//遍历右子树midTrival(node.right);}

3.后序遍历：

//实现后序遍历public void postTrival(Node node){//退出的条件if (node == null){return;}//遍历左子树postTrival(node.left);//遍历右子树postTrival(node.right);//先遍历根节点System.out.print(node.item+" ");}

注：由上面代码规律可以看出，除了根节点是直接打印其值之外，左节点、右节点都是通过递归遍历的方式遍历到。如：

先序遍历：打印根节点--->递归遍历左节点--->递归遍历右节点

中序遍历：递归遍历左节点--->打印根节点--->递归遍历右节点

后序遍历：递归遍历左节点--->递归遍历右节点--->打印根节点

4.层次遍历（一层一层遍历）：

思路：将根节点放入一个队列中，然后每次取出这个节点后，相应地将它的左右子节点依次放入队列中，按照队列的先进先出的特性，依次将元素出队列并打印。（如果觉得抽象，可以画图感受一下。）

//实现层次遍历(就是一层一层遍历)//思路：将根节点放入一个队列中，然后每次取出这个节点后，相应地将它的左右子节点依次放入队列//     中，按照队列的先进先出的特性，依次将元素出队列并打印。public void levelTrival(Node node){//创建一个队列ArrayDeque<Node> queue = new ArrayDeque<Node>(10);//将开始的结点放入到队列中queue.add(node);while (!queue.isEmpty()){//将队列中的结点出列Node n = queue.poll();System.out.print(n.item+" ");//将左子节点放入到队列中if (n.left != null){queue.add(n.left);}//将右子节点放入到队列中if (n.right != null){queue.add(n.right);}}}

5.main方法执行

public class TestBinaryTree {public static void main(String[] args) {BinaryTree bTree = new BinaryTree();//创建二叉树bTree.createTree();//执行前序遍历二叉树bTree.preTrival(bTree.root);System.out.println("--------------------");//执行中序遍历二叉树bTree.midTrival(bTree.root);System.out.println("---------------------");//执行后序遍历二叉树bTree.postTrival(bTree.root);System.out.println("---------------------");//执行层次遍历bTree.levelTrival(bTree.root);}
}

五、二叉树的查询和删除：

1.二叉树的查询：

查询可以选择任意一种遍历方式，在遍历的同时对当前元素的值进行比较判断。

这里选用先序遍历的方式来实现：

    //实现树的查询,按先序遍历//思路：可以选择任意一种遍历方式，在遍历的同时对当前元素的值进行比较判断即可。public Node preSearch(Node node, Object obj){//先判断树是否为nullif (node == null){return null;}//定义一个target用于接收preSearch的返回值,如果找到则接收当前结点，否则接收nullNode target = null;if (node.item == obj){//找到元素return node;}else {//先遍历左子树target = preSearch(node.left,obj);//判断是否找到元素if (target != null){return target;}//再遍历右子树target = preSearch(node.right,obj);//判断是否找到元素if (target != null){return target;}}return null;}

2.二叉树的删除：

因为二叉树不像平衡树那么复杂，删除元素要考虑到平衡等因素，所以删除二叉树的元素时，如果是叶子结点则直接赋予null，如果是非叶子结点则将整个子树删除，也就是给当前非叶子结点赋予null。

//实现树的删除//思路：遍历树将树的每一个元素与目标值进行比较，找到了就将其设为null，//     如果是叶子结点，则直接设为null，如果是非叶子结点，就将整个子树删除，也就是将此节点设为null即可。public void deleteNode(Node node,Object obj){//先判断树是否为空if (node == null){return;}//判断根节点是否为目标结点if (node == root && root.item == obj){this.root = null;}//判断子节点是否为目标//先判断左子树是否存在目标if (node.left != null){if (node.left.item == obj){//删除左子节点node.left = null;return;}else {//从子树中进行删除deleteNode(node.left,obj);}}//再判断右子树是否存在目标if (node.right != null){if (node.right.item == obj){//删除左子节点node.right = null;return;}else {//从子树中进行删除deleteNode(node.right,obj);}}}

3.main方法执行：

public class TestBinaryTree02 {public static void main(String[] args) {BinaryTree bTree = new BinaryTree();bTree.createTree();//查询结点BinaryTree.Node result = bTree.preSearch(bTree.root, 13);if (result != null){System.out.println("结果："+result.item);}else {System.out.println("没有此节点");}//删除结点bTree.deleteNode(bTree.root,2);bTree.levelTrival(bTree.root);}
}

六、二叉树深度的计算

//二叉树高度的计算你（深度）//思路：将左子树与右子树进行递归比较，最后返回最深的值。//     比如从根节点开始，比较其左子树、右子树，到了左子树、右子树这边，再比较其对应的左子树右子树，//     以此循环，用递归的方式来判断。public int maxDepth(Node node){//先判断树是否为空if (node == null){return 0;}int leftDepth = 0;int rightDepth = 0;//1.先获取左子树的高度if (node.left != null){leftDepth = maxDepth(node.left);}//2.再获取右子树的高度if (node.right != null){rightDepth = maxDepth(node.right);}//3.判断左右子树谁大if (leftDepth > rightDepth){return leftDepth + 1;}else {return rightDepth + 1;}}