树及二叉树【数据结构】

目录

  • 树形结构
    • 概念
    • 树和非树(图)的区别
    • 树的表示形式
  • 二叉树
    • 概念和特点
    • 特殊的二叉树:
    • 二叉树的相关操作
      • 二叉树的表示
      • 二叉树的遍历
      • 求二叉树节点个数
      • 求二叉树叶子节点的个数
      • 求第 K 层节点个数
      • 在二叉树中寻找指定元素

树形结构

我们之前研究的基本都是一对一的问题,而树是一种非线性数据结构,它是由n(n≥0)个结点组成的具有有层次关系的有限集

特点:
当 n=0 时,称为空树,在任何一个非空树中:

  • 有且只有一个根结点
  • 当 n>1 时,其余结点可分为 m(m>0) 个互不相交的有限集T1,T2,…Tm,其中每一个集合本身又是一棵树,并且称为根的子树(SubTree),每棵子树的根节点有且只有一个前驱,可以有0个或多个后继
    如图所示:
    .树及二叉树【数据结构】_第1张图片
  • 树是递归定义的

概念

名称 概念
节点的度: 一个节点含有的子树的个数称为该节点的度; 如上图:A的为2,D的为3
树的度: 一棵树中,最大的节点的度称为树的度; 如上图:树的度为3
叶子节点或终端节点: 度为 0 的节点称为叶子节点; 如上图:G、H、I、F…等节点为叶节点
双亲节点或父节点: 若一个节点含有子节点,则这个节点称为其子节点的父节点; 如上图:A是B的父节点
孩子节点或子节点: 一个节点含有的子树的根节点称为该节点的子节点; 如上图:B是A的孩子节点
根节点: 一棵树中,没有双亲节点的结点;如上图:A
节点的层次: 从根开始定义起,根为第1层,根的子节点为第2层,以此类推
树的高度或深度: 树中节点的最大层次; 如上图:树的高度为4
非终端节点或分支节点: 度不为0的节点; 如上图:B、C、D、E…等节点为分支节点
兄弟节点: 具有相同父节点的节点互称为兄弟节点; 如上图:B、C是兄弟节点
堂兄弟节点: 双亲在同一层的节点互为堂兄弟;如上图:D、E互为兄弟节点
节点的祖先: 从根到该结点所经分支上的所有节点;如上图:A是所有节点的祖先
子孙: 以某节点为根的子树中任一节点都称为该节点的子孙。如上图:所有节点都是A的子孙
森林: 由 m(m≥0) 棵互不相交的树的集合称为森林

树和非树(图)的区别

  • 子树是不相交的
  • 除了根节点外,每个节点有且仅有一个父节点
  • 一颗 n 个节点的树,有 n-1 条边

树及二叉树【数据结构】_第2张图片

树的表示形式

最常用的方法—孩子兄弟表示法:

class Node{
     
    int value;  //树中存储的数据
    Node firstChild;  //树中第一个孩子引用
    Node nextBrother; //下一个兄弟引用
}

画图表示:

树及二叉树【数据结构】_第3张图片

二叉树

概念和特点

概念:

对于在某个阶段都是两种结果的情形,比如:0和1、真和假、上和下、对与错、正和反等,都适合用树状结构来建模,而这种树是很特殊的树状结构,叫做二叉树

二叉树(Binary Tree)是 n(n≥0) 个节点的有限集合,该集合或者为空集(称为空二叉树),或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成

特点:

  • 每个节点最多有两棵子树,二叉树的度大能超过 2
    注意不是只有两棵子树,而是最多有,没有子树或者有一棵子树也是可以的
  • 二叉树的子树有左右之分,其子树的次序不能任意颠倒,因此二叉树是有序树
  • 即使树中某节点只有一棵子树,也要区分它是左子树还是右子树

二叉树的基本形态:

  • 空二叉树
  • 只有一个根节点
  • 根节点只有左子树
  • 根节点只有右子树
  • 根结点既有左子树又有右子树
  • 树及二叉树【数据结构】_第4张图片

特殊的二叉树:

满二叉树:

一个二叉树,若每一个层的节点数都达到最大值(即:2),则就为满二叉树
一个二叉树的层数为 n,且节点总数是 2n-1

树及二叉树【数据结构】_第5张图片
满二叉树的特点:

  • 叶子只出现在最下一层,出现在其他层就不可能达到平衡
  • 非叶子节点的度一定是2
  • 在同样深度的二叉树中,满二叉树的节点个数最大,叶子个数也最多

完全二叉树:

直观来说:相比于满二叉树来说,完全二叉树右小角缺了一块

完全二叉树是效率很高的数据结构,对于深度为K的,有n个节点的二叉树,当且仅当其每一个节点都与深度为K的满二叉树中编号从1至n的节点一一对应时称之为完全二叉树,满二叉树是一种特殊的完全二叉树

树及二叉树【数据结构】_第6张图片

完全二叉树的特点:

  • 叶子节点只能出现在最下两层
  • 最下层的叶子一定集中在左边连续位置
  • 倒数第二层,如果有叶子节点,一定出现在右边连续位置
  • 若节点度为1,则该节点只有左子树
  • 同样节点数的二叉树,完全二叉树的深度最小

二叉树的相关操作

二叉树的表示

可通过左右孩子来表示

class Node{
     
    int val;      //存储的数据
    Node left;    //左子树根节点的引用
    Node right;   //右子树根节点的引用
    Node parent;  //双亲的引用(可选)
}

二叉树的遍历

遍历: 遍历按照一定的顺序访问到集合中的每个元素,不重复不遗漏
由于二叉树不是线性结构,故遍历起来相对复杂

手动构造一棵树:

class Node{
     
    char val;      //存储的数据
    Node left;    //左子树根节点的引用
    Node right;   //右子树根节点的引用
    Node parent;  //双亲的引用(可选)

    //提供构造方法
    public Node(char val) {
     
        this.val = val;
    }
}

//构建一棵树
public static Node buildTree(){
     
    Node a = new Node('A');
    Node b = new Node('B');
    Node c = new Node('C');
    Node d = new Node('D');
    Node e = new Node('E');
    
    a.left = b;
    a.right = c;
    b.left = d;
    b.right = e;

    return a;
}

1.先序遍历

先访问根节点,递归遍历左子树,递归遍历右子树 (根左右)

例图:

树及二叉树【数据结构】_第7张图片
代码实现:

public static void preOrder(Node root){
     
    //若为空树,直接返回
    if(root == null){
     
        return;
    }
    //先访问根节点
    System.out.print(root.val+" ");
    
    //递归访问左子树
    preOrder(root.left);
    //递归访问右子树
    preOrder(root.right);
}

2.中序遍历

先递归遍历左子树,访问根节点,再递归遍历右子树 (左根右)

例图:

树及二叉树【数据结构】_第8张图片

public static void inOrder(Node root){
     
    //若为空树,直接返回
    if(root == null){
     
        return;
    }
    //递归访问左子树
    inOrder(root.left);
    //访问根节点
    System.out.print(root.val+" ");
    //递归访问右子树
    inOrder(root.right);
}

3.后序遍历

先递归遍历左子树,再递归遍历右子树,最后访问根节点 (左右根)

例图:

树及二叉树【数据结构】_第9张图片

public static void postOrder(Node root){
     
    //若为空树,直接返回
    if(root == null){
     
        return;
    }
    //递归访问左子树
    postOrder(root.left);
    //递归访问右子树
    postOrder(root.right);

    //访问根节点
    System.out.print(root.val+" ");
}

4.层序遍历

一层一层往下遍历,每层从左向右访问,为非递归操作

public static void levelOrder(Node root){
     
    //创建一个空队列并把根节点加入队列中
    Queue<Node> queue = new LinkedList<>();
    queue.offer(root);
    while( !queue.isEmpty()){
     
        //队列非空,取出队首元素
        Node cur = queue.poll();
        //访问元素
        System.out.print(cur.val + " ");

        //把左右子树入队列
        if(cur.left != null){
     
            queue.offer(cur.left);
        }
        if(cur.right != null){
     
            queue.offer(cur.right);
        }
    }
}

例图:

树及二叉树【数据结构】_第10张图片

遍历规律:

  • 先序遍历,第一个访问的节点一定是根节点
  • 后续遍历,最后一个访问的节点一定是根节点
  • 中序遍历和后序遍历,第一个访问的节点是树的最左侧节点
  • 针对先 / 后序遍历来说,子树的遍历结果是嵌套在整个遍历结果中的
  • 中序遍历,左子树的遍历结果在根节点的左侧,右子树的遍历结果在根节点的右侧

输出结果:

树及二叉树【数据结构】_第11张图片

求二叉树节点个数

public static int size(Node root){
     
    if(root == null){
     
        return 0;
    }
    //树节点总数 = 根节点个数(1) + 左子树节点个数 + 右子树节点个数
    return 1 + size(root.left) + size(root.right);
}

输出结果:5

画图分析:

执行顺序和"后序遍历"一模一样

树及二叉树【数据结构】_第12张图片

求二叉树叶子节点的个数

叶子节点:即度为0的节点

public static int leafSize(Node root){
     
    //空树
    if(root == null){
     
        return 0;
    }
    //只有根节点时,根节点就是唯一的叶子节点
    if(root.left == null && root.right == null){
     
        return 1;
    }
    // root叶子节点个数 = root.left叶子节点个数 + root.right叶子节点个数
    return leafSize(root.left) + leafSize(root.right);
}

输出结果:3

画图分析:

树及二叉树【数据结构】_第13张图片

求第 K 层节点个数

public static int kLevelSize(Node root,int k){
     
    //若 k<1 或root为空,则为空树
    if(k < 1 || root == null){
     
        return 0;
    }
    //若 k=1,即为根节点
    if(k == 1){
     
        return 1;
    }
    // k 层节点个数 = 左子树的(k-1)层节点个数 + 右子树的(k-1)层节点个数
    return kLevelSize(root.left,k-1) + kLevelSize(root.right,k-1);
}

输出结果:2

画图分析:

树及二叉树【数据结构】_第14张图片

在二叉树中寻找指定元素

public static Node find(Node root,char toFind){
     
    if(root == null){
     
        return null;
    }
    if(root.val == toFind){
     
        return root;
    }
    //递归查找左右子树
    Node result = find(root.left,toFind);
    if(result != null){
     
        return result;
    }
    return find(root.right,toFind);
}

画图分析:

树及二叉树【数据结构】_第15张图片
下篇会讨论二叉树的相关面试题~~

树及二叉树【数据结构】_第16张图片

你可能感兴趣的