Fork me on GitHub

数据结构--二叉树

字数统计: 3.6k字   |   阅读时长≈ 15分

树：（一对多关系，非线性结构）

avatar

  • 结点的度：一个节点含有的子树的个数称为该节点的度；如上图：A的度为6，即B、C、D、E、F、G。

  • 叶子结点：度为0的节点称为叶子结点；如上图：B、C、H、K、L、M、N、P、Q为叶子结点。

  • 双亲结点或父结点：若一个节点含有子结点，则这个结点称为其子结点的父结点；如上图：A是B、C、D、E、F、G的父结点。

  • 孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点；如上图：B、C、D、E、F、G是A的孩子节点。

  • 兄弟结点：具有相同父结点的结点互称为兄弟结点； 如上图：B、C、D、E、F、G是兄弟结点。

  • 树的度：一棵树中，最大的节点的度称为树的度； 如上图：树的度为6。

  • 结点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推。

  • 树的高度或深度：树中结点的最大层次； 如上图：树的高度为4。

  • 节点的祖先：从根到某一结点所经分支上的所有结点；如上图：D、A是H的祖先；A是所有结点的公共祖先。

  • 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙。

  • 森林：多棵互不相交的树的集合称为森林。

avatar

二叉树：

avatar

  • 特点：

    • 每个结点最多有两棵子树，即二叉树不存在度大于2的结点。

    • 二叉树的子树有左右之分，其子树的次序不能颠倒。

  • 满二叉树：在一棵二叉树中，如果所有分支结点都有左孩子结点和右孩子结点，并且叶子结点都集中在二叉树的最下一层，这样的二叉树称为满二叉树（每一层的结点数都达到最大值）

avatar

  • 完全二叉树：若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树（满二叉树从下到上，从右往左去掉结点）

avatar

二叉树：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class BinaryTree<T> {
    /**
     * 结点类
     */
    static class TreeNode <T>{
        T data;//存放数据
        TreeNode left;//左指针
        TreeNode right;//右指针

        public TreeNode() {
        }

        public TreeNode(T data) {
            this.data = data;
            left=null;
            right=null;
        }

        @Override
        public String toString() {
            return "TreeNode{" +
                    "data=" + data +
                    '}';
        }

    }

    TreeNode root;//根结点

    public BinaryTree() {
        root=null;
    }
}

常用方法：

  • 二叉树构造：

    括号表示法：将树的根结点写在括号的左边，除根结点之外的其余结点写在括号中并用逗号分隔。如：

    A(B(,D),C)

    avatar

方式一：根据括号表示法给定字符串序列构造

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
* 根据字符串构造二叉树
*/
public void creatTree(String str){
    Stack<TreeNode> st = new Stack<>();
    int i=0;
    boolean isFlag=false;
    TreeNode<Character> node=null;
    while (i<str.length()){
        char c = str.charAt(i);
        switch (c){
            case '(':
                st.push(node);
                isFlag=true;
                break;
            case ',':
                isFlag=false;
                break;
            case ')':
                st.pop();
                break;
            default:
                node=new TreeNode<>(c);
                if (root==null){
                    root=node;
                }else {
                    if (isFlag){
                        if (!st.empty()){
                            st.peek().left=node;
                        }
                    }else {
                        if (!st.empty()){
                            st.peek().right=node;
                        }
                    }
                }
                break;
        }
        i++;
    }
}

方式二：由先序遍历序列和中序遍历序列唯一确定一棵二叉树

已知先序序列为ABDGCEF，中序序列为DGBAECF，则构造二叉树的过程：

![avatar][PAndI]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//由先序序列pre和中序序列in构造二叉树
public BinaryTree createBT(String pre,String in) {  
    BinaryTree bt=new BinaryTree();
    bt.b=createBT1(pre,0,in,0,pre.length());
    return bt;
}

private TreeNode<Character> createBT1(String pre,int i, String in,int j,int n){  
    TreeNode<Character> t;
    char ch;
    int p,k;
    if (n<=0) return null;
    ch=pre.charAt(i);
    t=new TreeNode<Character>(ch);    //创建根结点(结点值为ch)
    p=j;    //p指中序序列的开始元素
    while (p<j+n){  //在in中找等于ch的位置p
        if (in.charAt(p)==ch){
            break;
        }
        p++;
    }
    k=p-j;	//确定左子树中结点个数k
    t.left=createBT1(pre,i+1,in,j,k);		//递归构造左子树
    t.right=createBT1(pre,i+k+1,in,p+1,n-k-1);	//递归构造右子树
    return t;
}

方式三：由后序遍历序列和中序遍历序列唯一确定一棵二叉树

已知中序序列为DGBAECF，后序序列为GDBEFCA，则构造二叉树的过程

![avatar][IAndP]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//由后序序列post和中序序列in构造二叉树
public BinaryTree createBT(String post,String in){      
    BinaryTree bt=new BinaryTree();
    bt.b=createBT1(post,0,in,0,post.length());
    return bt;
}

private TreeNode<Character> createBT1(String post,int i, String in,int j,int n){  
    TreeNode<Character> t;
    char ch;
    int p,k;
    if (n<=0) return null;
    ch=post.charAt(i+n-1);			//取后序序列尾元素
    t=new TreeNode<Character>(ch);			//创建根结点(结点值为ch)
    p=j;						//p指中序序列的开始元素
    while (p<j+n){  //在中序序列中找根位置p
        if (in.charAt(p)==ch){//在in中找到根后退出
            break;
        }								
        p++;
    }
    k=p-j;					//确定左子树中结点个数k
    t.left=createBT1(post,i,in,j,k);		//递归构造左子树
    t.right=createBT1(post,i+k,in,p+1,n-k-1);	//递归构造右子树
    return t;
}

注意：由先序遍历序列和后序遍历序列不能唯一确定一棵二叉树

  • 前序遍历：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    /**
    * 前序遍历
    */
    public void preOrder(BinaryTree binaryTree){
        this.perOrder1(binaryTree.root);
        }

        private void perOrder1(TreeNode treeNode){
        if (treeNode!=null){
            System.out.println(this);
            perOrder1(treeNode.left);
            perOrder1(treeNode.right);
        }
    }

  • 中序遍历：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    /**
    * 中序遍历
    */
    public void infixOrder(BinaryTree binaryTree){
        this.infixOrder1(binaryTree.root);
    }
    private void infixOrder1(TreeNode treeNode){
        if (treeNode!=null){
            infixOrder1(treeNode.left);
            System.out.println(this);
            infixOrder1(treeNode.right);
        }
    }

  • 后续遍历：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    /**
    * 后续遍历
    */
    public void postOrder(BinaryTree binaryTree){
        this.postOrder1(binaryTree.root);
    }

    private void postOrder1(TreeNode treeNode){
        if (treeNode!=null){
            postOrder1(treeNode.left);
            postOrder1(treeNode.right);
            System.out.println(this);
        }
    }

  • 查找值为x的结点：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    /**
    * 查找值为x的结点(前序查找)
    * @return
    */
    public TreeNode search(T c){
        return this.search1(root,c);
    }
    private TreeNode search1(TreeNode treeNode, T c){
        //根结点就是要查找的
        if (treeNode.data==c){
            return treeNode;
        }
        //用来记录找到的结点
        TreeNode search=null;
        //往左子树递归查找
        if (treeNode.left!=null){
            search = search1(treeNode.left,c);
        }
        //左子树如果找到则返回
        if (search!=null){
            return search;
        }
        //左子树找不到，往右子树递归查找
        if (treeNode.right!=null){
            search = search1(treeNode.right,c);
        }
        return search;
    }

  • 求树的高度：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    /**
    * 求树的高度
    * @return
    */
    public int height(BinaryTree binaryTree){
        return this.height1(binaryTree.root);
    }


    private int height1(TreeNode treeNode){
        int leftHeight =0;
        int rightHeight =0;
        if (treeNode==null) {
            return 0;
        } else {
            leftHeight=height1(treeNode.left);
            rightHeight=height1(treeNode.right);
            return Math.max(leftHeight,rightHeight)+1;
        }

    }

二叉排序树（二叉搜索树）：

avatar

特点：

  • 若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
  • 若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
  • 左、右子树也分别为二叉排序树；

哈夫曼树（最优树）：该树的带权路径长度（WPL）最小

W=(1，3，5，7)来构造一棵哈夫曼树

avatar

WPL=1 * 3 + 3 * 3 + 5 * 2 + 7 * 1 = 29

构建过程：

首次挑选两个小的结点1、3，将1、3相加构成4（1，3）子树，再挑选剩下结点中最小的5，和子树4（1，3）相加构成新的树9（4（1，3），5），以此类推···

Java 树：

  1. TreeSet

    继承关系：

    • Iterator 接口
      • Collection 接口
        • Set 接口:存储无序的、不可重复的元素(数学中的集合)
          • TreeSet 类

特点：基于TreeMap(二叉树–红黑树)实现;TreeSet是有序的,可以照添加对象的指定属性，进行排序,也提供了制定比较器的构造函数，如果没有提供比较器，则采用自然顺序进行比较大小（自然排序），如果指定的比较器，则采用指定的比较器，进行值大小的比较（定制排序）;向TreeSet中添加的数据，要求是相同类的对象

两种排序方式：

  • 自然排序（添加元素类必须实现Comparable接口）
  • 定制排序（需提供Comparator比较器）

自然排序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
@Test
public void test1(){
    TreeSet set = new TreeSet();

    //失败：不能添加不同类的对象
    //  set.add(123);
    //  set.add(456);
    //  set.add("AA");
    //  set.add(new User("Tom",12));

    //举例一：
    //  set.add(34);
    //  set.add(-34);
    //  set.add(43);
    //  set.add(11);
    //  set.add(8);

    //举例二：
    set.add(new User("Tom",12));
    set.add(new User("Jerry",32));
    set.add(new User("Jim",2));
    set.add(new User("Mike",65));
    set.add(new User("Jack",33));
    set.add(new User("Jack",56));


    Iterator iterator = set.iterator();
    while(iterator.hasNext()){
        System.out.println(iterator.next());
    }

}

定制排序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
@Test
public void test2(){
    //比较器
    Comparator com = new Comparator() {
        //照年龄从小到大排列
        @Override
        public int compare(Object o1, Object o2) {
            if(o1 instanceof User && o2 instanceof User){
                User u1 = (User)o1;
                User u2 = (User)o2;
                return Integer.compare(u1.getAge(),u2.getAge());
            }else{
                throw new RuntimeException("输入的数据类型不匹配");
            }
        }
    };

    TreeSet set = new TreeSet(com);
    set.add(new User("Tom",12));
    set.add(new User("Jerry",32));
    set.add(new User("Jim",2));
    set.add(new User("Mike",65));
    set.add(new User("Mary",33));
    set.add(new User("Jack",33));
    set.add(new User("Jack",56));

    Iterator iterator = set.iterator();
    while(iterator.hasNext()){
        System.out.println(iterator.next());
    }
}

常用方法：

  • E first(): 返回此集合中的第一个元素。其中，E 表示集合中元素的数据类型
  • E last(): 返回此集合中的最后一个元素
  • E poolFirst(): 获取并移除此集合中的第一个元素
  • E poolLast(): 获取并移除此集合中的最后一个元素
  • 3 个从 TreeSet 中截取子 TreeSet 的方法:
    • SortedSet < E > subSet(E fromElement,E toElement): 返回一个新的集合，新集合包含原集合中 fromElement 对象与 toElement对象之间的所有对象。包含 fromElement 对象，不包含 toElement 对象
    • SortedSet< E > headSet< E toElement >: 返回一个新的集合，新集合包含原集合中 toElement 对象之前的所有对象。不包含 toElement 对象
    • SortedSet< E > tailSet(E fromElement): 返回一个新的集合，新集合包含原集合中 fromElement 对象之后的所有对象。包含 fromElement 对象
  • boolean add：将指定的元素添加到此 set（如果该元素尚未存在于 set 中）
  • boolean addAll：将指定 collection 中的所有元素添加到此 set 中。
  • E ceiling：返回此 set 中大于等于给定元素的最小元素；如果不存在这样的元素，则返回 null。
  • void clear：移除此 set 中的所有元素。
  • Object clone：返回 TreeSet 实例的浅表副本。属于浅拷贝。
  • Comparator comparator：返回对此 set 中的元素进行排序的比较器；如果此 set 使用其元素的自然顺序，则返回 null。
  • boolean contains：如果此 set 包含指定的元素，则返回 true。
  • Iterator descendingIterator：返回在此 set 元素上按降序进行迭代的迭代器。
  • NavigableSet descendingSet：返回此 set 中所包含元素的逆序视图。

  1. TreeMap

    继承关系：

    • Map 接口:键值对 key➡value 的形式保存，key不能重复
      • SortedMap 接口
        • TreeMap 类

特点：有序的key-value集合，底层通过红黑树实现;TreeMap支持自然排序 、定制排序，如果没有提供比较器，则采用key的自然顺序进行比较大小（自然排序前提：添加元素类必须实现Comparable接口），如果指定的比较器，则采用指定的比较器，进行key值大小的比较（定制排序）;向TreeMap中添加key-value，要求key必须是由同一个类创建的对象

定制排序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import java.util.TreeMap;
import java.util.Comparator;

class Main {
    public static void main(String[] args) {

        //使用自定义比较器创建treemap
        TreeMap<String, Integer> numbers = new TreeMap<>(new CustomComparator());

        numbers.put("First", 1);
        numbers.put("Second", 2);
        numbers.put("Third", 3);
        numbers.put("Fourth", 4);
        System.out.println("TreeMap: " + numbers);
    }

    //创建一个比较器类
    public static class CustomComparator implements Comparator<String> {

        @Override
        public int compare(String number1, String number2) {
            int value =  number1.compareTo(number2);

            //元素以相反的顺序排序
            if (value > 0) {
                return -1;
            }
            else if (value < 0) {
                return 1;
            }
            else {
                return 0;
            }
        }
    }
}

常用方法：

  • 增添元素:
    • V put(K key, V value)：将指定映射放入该TreeMap中
    • V putAll(Map map)：将指定map放入该TreeMap中
  • 删除元素:
    • void clear()：清空TreeMap中的所有元素
    • V remove(Object key)：从TreeMap中移除指定key对应的映射
  • 修改元素
    • V replace(K key, V value)：替换指定key对应的value值
    • boolean replace(K key, V oldValue, V newValue)：当指定key的对应的value为指定值时，替换该值为新值
  • 查找元素
    • boolean containsKey(Object key)：判断该TreeMap中是否包含指定key的映射
    • boolean containsValue(Object value)：判断该TreeMap中是否包含有关指定value的映射
    • Map.Entry< K, V > firstEntry()：返回该TreeMap的第一个（最小的）映射
    • K firstKey()：返回该TreeMap的第一个（最小的）映射的key
    • Map.Entry< K, V > lastEntry()：返回该TreeMap的最后一个（最大的）映射
    • K lastKey()：返回该TreeMap的最后一个（最大的）映射的key
    • v get(K key)：返回指定key对应的value
    • SortedMap< K, V > headMap(K toKey)：返回该TreeMap中严格小于指定key的映射集合
    • SortedMap< K, V > subMap(K fromKey, K toKey)：返回该TreeMap中指定范围的映射集合（大于等于fromKey，小于toKey）
  • 其他方法
    • Object clone()：返回TreeMap实例的浅拷贝
    • Comparator<? super K> comparator()：返回给该TreeMap的keys排序的comparator，若为自然排序则返回null
    • int size()：返回该TreepMap中包含的映射的数量

TreeSet和TreeMap比较

相同点：

  • TreeMap和TreeSet都是有序的集合

  • TreeMap和TreeSet都是非同步（线程不安全）集合，因此他们不能在多线程之间共享，不过可以使用方法Collections.synchroinzedMap()来实现同步

  • 运行速度都要比Hash集合慢，他们内部对元素的操作时间复杂度为O(logN)，而HashMap/HashSet则为O(1)

不同点：

  • 最主要的区别就是TreeSet和TreeMap分别实现Set和Map接口

  • TreeSet只存储一个对象，而TreeMap存储两个对象Key和Value（仅仅key对象有序）

  • TreeSet中不能有重复对象，而TreeMap中可以存在

扫一扫，分享到微信

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia-plus根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

主要涉及技术：
Java开发

联系QQ:1445911979

如有错误，请帮忙指正，谢谢大家~~