1.二叉树

二叉树

1.二叉树定义

在计算机科学中，二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”和“右子树”，左子树和右子树同时也是二叉树。二叉树的子树有左右之分，并且次序不能任意颠倒。二叉树是递归定义的，所以一般二叉树的相关题目也都可以使用递归的思想来解决，当然也有一些可以使用非递归的思想解决。

2.什么是二叉排序树

二叉排序树又叫二叉查找树或者二叉搜索树，它首先是一个二叉树，而且必须满足下面的条件：

1）若左子树不空，则左子树上所有结点的值均小于它的根节点的值；

2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值

3）左、右子树也分别为二叉排序树

4）没有键值相等的节点

3.二叉树节点定义

采用单项链表的形式，只从根节点指向孩子节点，不保存父节点。

//节点类，用于存储二叉树的节点信息
Class Node{
    public int data;
    public Node leftChild;
    public Node rightChild;  
}

4.二叉树的操作

二叉树(我们这里以二叉排序树为例)的查找插入操作：

 1  Class Tree{
 2      //根节点
 3      private Node root;
 4      //当前节点  
 5      Node current = root;  
 6      
 7     //查找元素
 8     public Node findNode(int key){
 9              if(key < current.data){
10                     current = current.leftChild;              
11             } else if(key > current.data) {
12                     current = current.rightChild;             
13             }
14             else if(current == null) {
15                     return null
16             }
17              return current;
18    }    
19  }

插入元素

 1 public void insert(int key) {
 2           Node newNode = new Node();
 3           newNode.data = key;
 4           if(root==null) {
 5               root = newNode;     
 6             }
 7            else{
 8                Node current = root;
 9                while(true) {
10                    if(key < root.data) {
11                            current = curent.leftChild;
12                            if(current == null) {
13                                 current.leftChild = newNode;
14                                 return;
15                             }
16                        }else {
17                                 current = current.rightChild;
18                                 if (current == null) {
19                                     current.rightChild = newNode;
20                                      return;
21                                   }
22                            }
23                 }
24            }
25 }

二叉树的中序遍历(inOrderTraverse),遍历操作不只针对二叉排序树

二叉树的中序遍历就是首先遍历左子树，然后访问当前节点，最后遍历右子树。对于下面的二叉树，中序遍历结果如下：

结果：[5,10,6,15,2]

直观来看，二叉树的中序遍历就是将节点投影到一条水平的坐标上。如图：

 1 /*
 2 二叉树的中序遍历：
 3 遍历不只是针对二叉排序树，遍历的过程关注的是该节点是否存在子树
 4 遍历的过程中使用到了递归的思想
 5 */
 6 public void inSort(Node root){
 7  if(root!=null) {
 8          inSort(root.leftChild);
 9          System.out.println(root.data); 
10          inSort(root.rightChild);
11    }  
12 }

二叉树的前序遍历(preOrderTraverse):

/* 二叉树的前序遍历(preOrderTraverse）
       1.访问这个节点 
     * 2.调用自身来遍历节点的左子树 
     * 3.调用自身来遍历节点的右子树
     * 
     */

public void preOrderTraverse(Node root){
        if(root!=null){
            System.out.println(root.data);
            preOrderTraverse(root.leftChild);
            preOrderTraverse(root.rightChild);
        }
    }

二叉树的后序遍历

 1 /* 二叉树的后序遍历(OrderTraverse）
 2        1.访问这个节点 
 3      * 2.调用自身来遍历节点的左子树 
 4      * 3.调用自身来遍历节点的右子树
 5      * 
 6      */
 7 
 8 public void postOrderTraverse(Node root){
 9         if(root!=null){
10             postOrderTraverse(root.leftChild);
11             postOrderTraverse(root.rightChild);
12             System.out.println(root.data);
13         }
14     }

二叉树查找最值

/*
     * 二叉排序树查找最值
     */
    //查找最大值
    public Node maxNode(){
        Node current=root;
        Node lastNode = root;
        while(current!=null){
            lastNode=current;
            current=current.leftChild;
        }
        return lastNode;    
    }
    /*
     * 二叉排序树查找最值
     */
    //查找最小值
    public Node minNode(){
        Node current=root;
        Node lastNode = root;
        while(current!=null){
            lastNode=current;
            current=current.rightChild;
        }
        return lastNode;    
    }