数据结构-二叉树详解（原理+基本操作Java实现）

阳光穿透心脏的1/2处 2023-09-27 13:51 105阅读 0赞

## 二叉树的概念及特点 ##

二叉树的概念

二叉树（Binary Tree）是n （n>=0）个节点的有限集合，该集合可以为空集（称为空二叉树），或者由一个根节点和两个互不相交的，分别称为根节点的左子树和右子树的二叉树组成。

二叉树的特点：

1、每个节点最多有两棵子树，即不存在超过度为2的节点。

2、二叉树的子树有左右之分，且左右不能颠倒。

如下图所示，下图就是一个二叉树

![17a1497d06cfd340ba38ed1f8113c44c.png][]

## 特殊的二叉树 ##

1. 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树。

如下图所示

![d7e9b6284b5804683ab2842bc91d1377.png][]

2.完全二叉树：完全二叉树是由满二叉树引出的。满二叉树要求每一层的节点数都达到最大值，完全二叉树仅要求除最后一层外的节点数达到最大值，也就是说最后一层可以不满。我们可以把满二叉树看错特殊的完全二叉树。

如下图所示

![320696a9e93349870f028e7207d74f09.png][]

## 二叉树的性质 ##

1.若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1) 个结点。

2.若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h- 1。

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

4.若规定根节点的层数为1，具有n个结点的满二叉树的深度，h=Log2(n+1)

5.对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的结点有：

（1）若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点

（2）若2i+1<n，左孩子序号：2i+1，2i+1>=n否则无左孩子

（3）若2i+2<n，右孩子序号：2i+2，2i+2>=n否则无右孩子

## 二叉树的基本操作 ##

### 树结点类和构造方法 ###

static class TreeNode {
            public char val;
            public TreeNode left;//左孩子的引用
            public TreeNode right;//右孩子的引用
     
            public TreeNode(char val) {
                this.val = val;
            }
        }

### *创建一棵二叉树* ###

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');
            A.left=B;
            A.right=D;
            B.left=C;
            D.left=E;
            D.right=F;
            return A;
        }

### 遍历 ###

#### 前序遍历 ####

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

#### 中序遍历 ####

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

#### 后序遍历 ####

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

### *获取树中节点的个数：遍历思路* ###

public static int nodeSize;//定义一个全局变量方便保存结点个数
    public void size(TreeNode root) {
            if (root==null){
                return;
            }
            nodeSize++;//不是空就++
            size(root.left);
            size(root.right);
        }

### *获取节点的个数：子问题的思路* ###

int size2(TreeNode root) {
            if (root==null){
                return 0;
            }
            int leftSize=size2(root.left);//先求左子树的结点个数
            int rightSize=size2(root.left);//然后求右子树结点的个数
            return leftSize+rightSize+1;//返回左子树和右子树加上1
        }

也许有的小伙伴不明白为什么要加一，加一就是加上本根结点

### 获取叶子节点的个数：遍历思路 ###

遍历思路跟上面一样，定义全局变量，满足条件就++，缺点就是只能求一棵树，两棵树就不好求，建议大家用子问题的思路

public static int leafSize = 0;//和上面一样，方便保存叶子结点个数 
        void getLeafNodeCount1(TreeNode root) {
            if (root==null){
                return;
            }
            if (root.left==null&&root.right==null){//满足if里面的条件就说明是叶子结点
                leafSize++;
            }
            getLeafNodeCount1(root.left);
            getLeafNodeCount1(root.right);
        }

### 获取叶子节点的个数：子问题 ###

如下代码，满足条件就返回1，否则返回零，通过左子树加右子树累加起来，最后返回总数目

int getLeafNodeCount2(TreeNode root) {
            if (root==null){
                return 0;
            }
            if (root.left==null&&root.right==null){
                return 1;
            }
            int l=getLeafNodeCount2(root.left);
            int r=getLeafNodeCount2(root.right);
            return l+r;
        }

### 获取第K层节点的个数 ###

利用一直递归k-1求得左子树和右子树的本层结点个数，最后返回它们的和

int getKLevelNodeCount(TreeNode root, int k) {
            if (root==null){
                return 0;
            }
            if (k==1){
                return 1;
            }
    
            int l=getKLevelNodeCount(root.left,k-1);
            int r=getKLevelNodeCount(root.right,k-1);
    
            return l+r;
        }

### 获取二叉树的高度 ###

利用递归方法返回左右子树最大高度加上根节点本身

int getHeight(TreeNode root) {
           if (root==null){
               return 0;
           }
           int leftHigh=getHeight(root.left);
           int rightHigh=getHeight(root.right);
           return Math.max(leftHigh,rightHigh)+1;
        }

### 检测值为value的元素是否存在 ###

TreeNode find(TreeNode root, char val) {
            if(root == null) {
                return null;
            }
            if(root.val == val) {
                return root;
            }
            TreeNode ret1 = find(root.left,val);
            if(ret1 != null) {
                return ret1;//如果左子树不为空，就说明找到了，返回
            }
            TreeNode ret2 = find(root.left,val);
            if(ret2 != null) {
                return ret2;//如果右子树不为空，就说明找到了，返回
            }
            return null;
        }

### 判断一棵树是不是完全二叉树 ###

boolean isCompleteTree(TreeNode root) {
            if(root == null) {
                return true;
            }
            Queue<TreeNode> qu = new LinkedList<>();
            qu.offer(root);
            while(!qu.isEmpty()) {
                TreeNode node = qu.poll();
                if(node != null) {
                    qu.offer(node.left);
                    qu.offer(node.right);
                } else {
                    break;
                }
            }
            if(!qu.isEmpty()) {
                TreeNode node = qu.poll();
                if(node != null) {
                    return false;
                }
            }
            return true;
        }

本期知识点就到这里，关注我，下期会给大家带来关于二叉树的力扣等练习题

[17a1497d06cfd340ba38ed1f8113c44c.png]: https://img-blog.csdnimg.cn/img_convert/17a1497d06cfd340ba38ed1f8113c44c.png
[d7e9b6284b5804683ab2842bc91d1377.png]: https://img-blog.csdnimg.cn/img_convert/d7e9b6284b5804683ab2842bc91d1377.png
[320696a9e93349870f028e7207d74f09.png]: https://img-blog.csdnimg.cn/img_convert/320696a9e93349870f028e7207d74f09.png