二叉树【Java数据结构】_java二叉树数据结构

目录

1. 树形结构 

 1.1 概念

2. 二叉树

2.1 概念

 2.2 两种特殊的二叉树

 2.3 二叉树的性质

2.4 题目 

3. 二叉树的遍历

3.1 前序遍历

3.2 中序遍历

3.3 后续遍历

---

 

1. 树形结构 

树是一种非线性 的数据结构，它是由 n （ n>=0 ）个有限结点组成一个具有层次关系的集合。 把它叫做树是因为它看 起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：

1. 有一个特殊的结点，称为根结点，根结点没有前驱结点。

2. 除根结点外，其余结点被分成 M(M > 0) 个互不相交的集合 T1 、 T2 、 ...... 、 Tm ，其中每一个集合 Ti (1 <= i <= m) 又是一棵与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有 0 个或多个后继。

3. 树是递归定义的。

注意：树形结构中，子树之间不能有交集，否则就不是树形结构。 

1. 子树是不相交的。

2. 除了根结点外，每个结点有且仅有一个父结点。

3. 一颗N个结点的树有N-1条边。     

 1.1 概念

 

结点的度 ：一个结点含有子树的个数称为该结点的度； 如上图： A 的度为 6。

树的度 ：一棵树中，所有结点度的最大值称为树的度； 如上图：树的度为 6。

叶子结点或终端结点 ：度为 0 的结点称为叶结点； 如上图： B 、 C 、 H 、 I... 等节点为叶结点。

双亲结点或父结点 ：若一个结点含有子结点，则这个结点称为其子结点的父结点； 如上图： A 是 B 的父结点。

孩子结点或子结点 ：一个结点含有的子树的根结点称为该结点的子结点； 如上图： B 是 A 的孩子结点。

根结点 ：一棵树中，没有双亲结点的结点；如上图： A。

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

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

树的以下概念只需了解，在看书时只要知道是什么意思即可：

非终端结点或分支结点 ：度不为 0 的结点； 如上图： D 、 E 、 F 、 G... 等节点为分支结点。

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

堂兄弟结点 ：双亲在同一层的结点互为堂兄弟；如上图： H 、 I 互为兄弟结点。

结点的祖先 ：从根到该结点所经分支上的所有结点；如上图： A 是所有结点的祖先。

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

森林 ：由 m （ m>=0 ）棵互不相交的树组成的集合称为森林。

 

2. 二叉树

2.1 概念

一棵二叉树是结点的一个有限集合，该集合：

1. 或者为空。

2. 或者是由 一个根节 点加上两棵别称为 左子树 和 右子树 的二叉树组成。

 从上图可以看出：

1. 二叉树不存在度大于 2 的结点。

2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树。

 2.2 两种特殊的二叉树

1. 满二叉树 : 一棵二叉树，如果 每层的结点数都达到最大值，则这棵二叉树就是满二叉树 。也就是说， 如果一棵 二叉树的层数为 K ，且结点总数是（2的k次方-1） 则它就是满二叉树。

2. 完全二叉树 : 完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为 K 的，有 n 个结点的二叉树，当且仅当其每一个结点都与深度为K 的满二叉树中编号从 0 至 n-1的结点一一对应时称之为完 全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

 

 

 

 2.3 二叉树的性质

1. 若规定 根结点的层数为 1 ，则一棵 非空二叉树的第 i 层上最多有2的（i-1次方） (i>0)个结点

2. 若规定只有根结点的二叉树的深度为1，则深度为K的二叉树的最大结点数是（2的k次方-1）(k>=0)

3. 对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2,则有n0＝n2＋1

4. 具有n个结点的完全二叉树的深度k为log2(n+1)上取整。

第三点： 

 

第四点：

 

 

 

2.4 题目 

1. 某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（）

A 不存在这样的二叉树

B 200

C 198

D 199

利用公式3：n0 = n2 +1 可得出结果。        故选B

2. 在具有 2n 个结点的完全二叉树中，叶子结点个数为（）

A n

B n+1

C n-1

D n/2

 

 这一题我们需要注意到有两种情况：

题目所给的是2n，即为偶数，所以是第二种情况，所以 2n = n0 + 1 +n2(1表示只有一个度为1的结点) ，有因为 n0 = n2 + 1，所以可得2n-1 = x + x-1，n=x   ( 设x为结点为0的个数)        故选A。

 

3. 一个具有 767 个节点的完全二叉树，其叶子节点个数为（）

A 383

B 384

C 385

D 386

 

767是奇数，为第二题图中的第一种情况，767=n0+n2 = x + x - 1(设x为结点为0的个数)

得 2x = 768       x = 384        故选B。

 

4. 一棵完全二叉树的节点数为 531 个，那么这棵树的高度为（）

A 11

B 10

C 8

D 12

 

 k = log2(n+1)取整：k = log2 (532)得k = 9.x  取整的10        故选B。

 

3. 二叉树的遍历

二叉树的存储分为：顺序存储和类似于链表的链式存储，这里讲解的是链式存储。

二叉树的链式存储是通过一个一个的结点引用起来的，常见的表示方法二叉和三叉表示方法，（这里讲解的是二叉）具体如下：

// 孩子表示法
class Node { 
    int val; // 数据域 
    Node left; // 左孩子的引用，常常代表左孩子为根的整棵左子树 
    Node right; // 右孩子的引用，常常代表右孩子为根的整棵右子树
 }
 
 
 
// 孩子双亲表示法
class Node { 
    int val; // 数据域 
    Node left; // 左孩子的引用，常常代表左孩子为根的整棵左子树 
    Node right; // 右孩子的引用，常常代表右孩子为根的整棵右子树 
    Node parent; // 当前节点的根节点 
}

此处手动快速创建一棵简单的二叉树，快速进入二叉树操作学习。

注意：下述代码并不是创建二叉树的方式！真正创建二叉树方式后序会讲解哦！

public class TestBinaryTree {
    static class TreeNode {
        public char val;
        public TreeNode left;
        public TreeNode right;
 
        public TreeNode(char val) {
            this.val = val;
        }
    }
 
    private TreeNode root;
 
    public TreeNode createTree() {
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');
 
        root = A;
 
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.right = H;
 
        return A;
    }
}

 

 

3.1 前序遍历

访问根结点--->根的左子树--->根的右子树。 

public void preOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }

这里我们以简单一点的图来此解析： 

 

 

 

 上图中的数字就是程序的执行顺序，因此可得输出的结果为：A B E C

按照此逻辑，第一次创建的树的输出结果为：A B D E H C F G 

3.2 中序遍历

根的左子树--->根节点--->根的右子树。  

public void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }

 

上图中的数字就是程序的执行顺序，因此可得输出的结果为：B E A C

按照此逻辑，第一次创建的树的输出结果为：D B E H A F C G

 

3.3 后续遍历

根的左子树--->根的右子树--->根节点。 

public void postOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }

 

 

 

上图中的数字就是程序的执行顺序，因此可得输出的结果为：E B C A

按照此逻辑，第一次创建的树的输出结果为：D H E B F G C A