树

树是很常见而且被广泛利用的数据结构,而且种类繁多,包括一般二叉树、完全二叉树、满二叉树、线索二叉树、二叉排序树、平衡二叉树、红黑树、霍夫曼树、B树,B+Tree等.

概念

树是一种抽象数据类型,或是实现这种抽象数据类型的[数据结构]用来模拟具有树状结构性质的数据**。
它是由n（ngt;0）个有限节点组成一个具有层次关系的。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：

树里面没有环路(cycle)
每个节点都只有有限个子节点或无子节点；
没有父节点的节点称为根节点；
每一个非根节点有且只有一个父节点；
除了根节点外，每个子节点可以分为多个不相交的子树；

术语

节点的度：一个节点含有的子树的个数称为该节点的度；
树的度：一棵树中，最大的节点度称为树的度；
叶节点或终端节点：度为零的节点；
非终端节点或分支节点：度不为零的节点；
父亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；
孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；
兄弟节点：具有相同父节点的节点互称为兄弟节点；
节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
深度：对于任意节点n,n的深度为从根到n的唯一路径长，根的深度为0；
高度：对于任意节点n,n的高度为从n到一片树
叶的最长路径长，所有树叶的高度为0；
堂兄弟节点：父节点在同一层的节点互为堂兄弟；
节点的祖先：从根到该节点所经分支上的所有节点；
子孙：以某节点为根的子树中任一节点都称为该节点的子孙。
森林：由m（mgt;=0）棵互不相交的树的**称为森林；

树的表示方法

链表,数组

定义节点

      public class TreeNode {
            E  object;
            TreeNode left;
            TreeNode right;
      }

树的基本操作

二叉树

它是一种特殊的结构的没个节点只有两个分支,而且没有构成环的一种特殊的树.

示例

二叉树的遍历

深度优先分为三种分别是前序,中序,后序(这里的前中后指的是根的顺序).
广度优先是安层来遍历一颗树.

递归的实现 :

import java.util.ArrayList;
import java.util.List;

public class BinaryTree {
     /*
        Definition for a binary tree node.
     * */
      public class TreeNode {
            int val;
            TreeNode left;
            TreeNode right;
            TreeNode(int x) { val = x; }
      }
    List<Integer> result = new ArrayList<>();

    /**
     *   前序遍历
     * @param root
     * @return
     */
    public List<Integer> preorderTraversal(TreeNode root) {
        if (root !=null){
            result.add(root.val);
            preorderTraversal(root.left);
            preorderTraversal(root.right);
        }
        return result;
    }

    /**
     *   中序遍历
     * @param root
     * @return
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        if (root !=null){
            inorderTraversal(root.left);
            result.add(root.val);
            inorderTraversal(root.right);
        }
        return result;
    }
    /**
     *  后序遍历
     * @param root
     * @return
     */
    public List<Integer> postorderTraversal(TreeNode root) {
        if (root !=null){
            postorderTraversal(root.left);
            postorderTraversal(root.right);
            result.add(root.val);
        }
        return result;
    }
}

非递归的实现 :

层遍历

public List<List<Integer>> levelOrder(TreeNode root) {
        if(root == null){return levelRead;}
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        List<Integer> level  =  new ArrayList<>();
        TreeNode current = null;
        queue.add(root);
        while(!queue.isEmpty()){
                  //出队队头元素并访问
            current = queue.poll();
            level.add(current.val);
            // System.out.print(current.val +"-->");
            if(queue.isEmpty()){
                levelRead.add(level);
                level = new ArrayList<>();
            }
            //如果当前节点的左节点不为空入队
            if(current.left != null){
                queue.add(current.left);
            }
            //如果当前节点的右节点不为空，把右节点入队
            if(current.right != null){
                queue.add(current.right);
            }
       }
        return levelRead;
   }

数据结构--树