二叉树

简介

树是一种经常用到的数据结构，用来模拟具有树状结构性质的数据集合。 二叉树是一种更为典型的树状结构。如它名字所描述的那样，二叉树是每个节点最多有两个子树的树结构，通常子树被称作“左子树”和“右子树”。

树的遍历

void traverse(TreeNode root) {
    if (root == null) {
        return;
    }
    // 前序位置
    traverse(root.left);
    // 中序位置
    traverse(root.right);
    // 后序位置
}

• 前序位置的代码在刚刚进入一个二叉树节点的时候执行；

• 后序位置的代码在将要离开一个二叉树节点的时候执行；

• 中序位置的代码在一个二叉树节点左子树都遍历完，即将开始遍历右子树的时候执行。

• 二叉树的每个节点都有「唯一」属于自己的前中后序位置，所以前中后序遍历是遍历二叉树过程中处理每一个节点的三个特殊时间点。

---

void TreeNode<T>
{
    //每个结点的数据
    T data;
    //左子树
    TreeNode  left;
    //右孩子
    TreeNode  right;
};

前序遍历

void PreorderTraverse(TreeNode root){
    if (root == null) {
        return;
    }
     
    // 前序位置
    
     System.out.println(root);//访问根结点
      
    traverse(root.left); //遍历左子树   
    
    traverse(root.right); //遍历右子树   
    
}

中序遍历

//递归实现中序遍历
void InorderTraverse(TreeNode root){
    if (root == null) {
        return;
    }

    traverse(root.left); //遍历左子树   
    
    // 中序位置
     System.out.println(root);//访问根结点
    
    traverse(root.right); //遍历右子树   
    
}

后序遍历

//递归实现后序遍历
void PostorderTraverse(TreeNode root){
    if (root == null) {
        return;
    }

    traverse(root.left); //遍历左子树   
    
    traverse(root.right); //遍历右子树   
    
    // 后序位置
     System.out.println(root);//访问根结点
    
}

二叉排序树

•         在建立二叉树的同时，数据已经经过初步比较，按照二叉树进行排序。

class BinaryTree{
    public TreeNode rootNode;
    
    public void add(int value){
        if( rootNode == null){
            rootNode = new TreeNode(value);
            return;
        }
        TreeNode timeNode = rootNode; 
        //排序
        while(true){
            if(value < timeNode.data ){
                if(timeNode.left == null){
                    timeNode.left = new TreeNode(value);
                    return;
                }else{
                    timeNode = timeNode.left; 
                }
            }else{
                if(timeNode.right == null){
                    timeNode.right = new TreeNode(value);
                    return;
                }else{
                    timeNode = timeNode.right; 
                }
            }
        }
    }
}

二叉搜索树

• 可是是空集合，若不为空则节点上一定有键值。
• 每一个根的值需要大于左子树的值。
• 每一个根的值需要小于右子树的值。
• 左右子树也是二叉搜索树。
• 树的每个节点值都不同。

class BinarySearch{
    public TreeNode rootNode;
    public static int count = 1;
    
    
    public void add(int value){
        if( rootNode == null){
            rootNode = new TreeNode(value);
            return;
        }
        TreeNode timeNode = rootNode; 
        //排序
        while(true){
            if(value < timeNode.data ){
                if(timeNode.left == null){
                    timeNode.left = new TreeNode(value);
                    return;
                }else{
                    timeNode = timeNode.left; 
                }
            }else{
                if(timeNode.right == null){
                    timeNode.right = new TreeNode(value);
                    return;
                }else{
                    timeNode = timeNode.right; 
                }
            }
        }
    }
    
    public boolean findTree(int value){
        if( rootNode == null){
            return false;
        }
        
        if(value == rootNode.data){
            return true;
        }else{
            return findTree(rootNode,value);
        }
    }
    
    private boolean findTree(TreeNode node,int value){
        if( value == node.data{
            return true;
        }
        count +=1;
        if(value < node.data){
            return findTree(node.left,value);
        }else{
            return findTree(node.right,value);
        }
       
    }
}