认识二叉树

简介: 认识二叉树

hi,代噶候。今天带大家认识一下二叉树,这个二叉树在我看来确实很有难度,但是不要怕,,鲁迅先生曾经说过,真正的勇士敢于面对惨淡的人生,敢于正视淋漓 的鲜血,下面让我们开始吧,先看看大纲

🚀1.什么是树

🚀2.树的相关概念

🚀3.什么是二叉树

🚀4.二叉树的相关概念

🚀5.二叉树的基本操作


什么是树呢???

树是一种非线性的结构,由n个结点组成,之所以叫做树,是因为它是根朝上,叶子朝下的结构,和现实中的树很像。

树的几个注意的点

1.一棵树只有一个根节点

2.树和链表不一样。没有所谓的前驱,只有左树和右树

3.树是递归实现的


6cbe7cb116314e8e9f4882003ad5caf3.png

现在对树的相关概念进行介绍


1.结点的度:树的子树的个数 ,上图中A的度为2


2.树的度:所有节点数的最大值叫做树的度,上图中树的度为5


3.叶子结点:没有左子树并且没有右子树


4.双亲结点:若一个结点有孩子结点,那么该结点为双亲节点


5.孩子结点:双亲结点的孩子叫做孩子结点


6.根节点:没有父亲结点的结点;


7.树的层次:从根开始定义起,根为第1层,根的子结点为第2层,以此类推


8.树的高度或深度:结点的最大层次

树要怎么表示呢

有双亲表示法

孩子表示法

孩子双亲表示法

孩子兄弟表示法


class Node {

int value ; //树的存储的值

Node fifirstChild ;//第一个孩子引用

Node nextBrother ; //第二个孩子引用

这个了解即可


现在重头戏来了:二叉树来了


先了解一下二叉树的概念

就是每个结点的度不能超过2的树

画个图

2bca9c6aebf54ceabfc205cf0dba11b5.png


这个图就是一个二叉树

满二叉树

二叉树的每一个结点都有左子树和右子树

如图


完全二叉树

不一定满。但是在进行层次遍历的时候顺序一定是相连的

在进行层次遍历的时候有1,2,3,4,5,6,7,8,9,10,11,12,13

这就是有序的

什么是无序的呢,再画个图

3576be3366814412911d5687c384e612.png

这就不是一个完全二叉树,不连续,11和13之间差一个12


由此可看,满二叉树是一种特殊的完全二叉树


二叉树的性质


若规定 根结点的层数为 1 ,则一棵 非空二叉树的第 i层有2^(i-1)

(i>0) 个结点

若规定只有 根结点的二叉树的深度为 1 ,则 深度为 K 的二叉树的最大结点数是2^k-1

(k>=0)

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

总结点数n=n0+n1+n2;

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

的结点有 :

若 i>0 , 双亲序号: (i-1)/2 ; i=0 , i 为根结点编号 ,无双亲结点

若 2i+1<n ,左孩子序号: 2i+1 ,否则无左孩子

若 2i+2<n ,右孩子序号:2i+2,   否则无右孩子

具有 n 个结点的完全二叉树的深度 k 为log(n+1)向

上取整

有一个关于完全二叉树的点

当有n个结点,n 为偶数个结点时,度为1的结点的个数为1,n为奇数结点的时候,度为1的结点的个数为0

二叉树的存储


二叉树的存储分为链式存储额和顺序存储


今天先讲链式存储


//孩子表示法
class Node {
int val; // 数据域
Node left; // 左孩子的引用,常常代表左孩子为根的整棵左子树
Node right; // 右孩子的引用,常常代表右孩子为根的整棵右子树
}


下面来说一说二叉树的遍历方式

1.前序遍历  根左右

2.中序遍历  左根右

3.后序遍历  左右根

4.层次遍历  从左至右

f1b1f299a0c34a3da3a80259b3eca337.png

就拿这棵树来举例

前序遍历:ABDGEHCF

中序遍历:GDBHEACF

后序遍历:GDHEBFCA

层次遍历:ABCDEFGH

还有一种考法,多出现在选择题里面,已知前序和中序,求后序。或者已知中序和后序,求前序

下面是二叉树的基本操作


 public class BinaryTree {
    static class TreeNode {
        public char val;
        public TreeNode left;//左孩子的引用
        public TreeNode right;//右孩子的引用
        public TreeNode(char val) {
            this.val = val;
        }
    }
    public TreeNode root;
    /**
     * 创建一棵二叉树 返回这棵树的根节点
     *
     * @return
     */
    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');
        A.left=B;
        B.left=D;
        B.right=E;
        C.left=F;
        C.right=G;
        E.right=H;
        this.root=A;
        return root;
    }
    // 前序遍历
    public void preOrder(TreeNode root) {
        if(root==null){
            return;
        }
        System.out.println(root.val+"");
       preOrder(root.left);
       preOrder(root.right);
    }
    // 中序遍历
    void inOrder(TreeNode root) {
        if(root==null){
            return;
        }
       inOrder(root.left);
        System.out.println(root.val+"");
        inOrder(root.right);
    }
    // 后序遍历
    void postOrder(TreeNode root) {
        if(root==null){
            return;
        }
        postOrder(root.left);
        System.out.println(root.val+"");
        postOrder(root.right);
    }
    public static int nodeSize;
    /**
     * 获取树中节点的个数:遍历思路
     */
    public int NodeSize;//成员变量
    void size(TreeNode root) {
        if(root==null){
            return;
        }
        NodeSize++;
       size(root.left);
       size(root.right);
    }
    /**
     * 获取节点的个数:子问题的思路
     *
     * @param root
     * @return
     */
    int size2(TreeNode root) {
        if(root==null){
            return -1;
        }
        int leftSize=size2(root.left);
        int rightSize=size2(root.right);
        return leftSize+rightSize+1;
    }
    /*
     获取叶子节点的个数:遍历思路
     */
    public static int leafSize = 0;//静态成员变量
    void getLeafNodeCount1(TreeNode root) {
        if(root==null){
            return;
        }
        if(root.left==null&&root.right==null){
            leafSize++;
        }
        getLeafNodeCount1(root.left);
        getLeafNodeCount1(root.right);
    }
    /*
     获取叶子节点的个数:子问题
     */
    int getLeafNodeCount2(TreeNode root) {
        if(root==null){
            return -1;
        }
        if(root.left==null&&root.right==null){
            return 1;
        }
        int leftSize=getLeafNodeCount2(root.left);
        int rightSize=getLeafNodeCount2(root.right);
        return leftSize+rightSize;
    }
    /*
    获取第K层节点的个数
     */
    int getKLevelNodeCount(TreeNode root, int k) {
        if(root==null){
            return -1;
        }
        if(k==1){
            return 1;
        }
         int leftSize=   getKLevelNodeCount(root.left,k-1);
      int rightSize=  getKLevelNodeCount(root.right,k-1);
      return leftSize+rightSize;
    }
    /*
     获取二叉树的高度
     时间复杂度:O(N)
     */
    int getHeight(TreeNode root) {
        if(root==null){
            return -1;
        }
        int leftHeight=getHeight(root.left);
        int  rightHeight=getHeight(root.right);
        return (leftHeight>rightHeight)?leftHeight+1:rightHeight+1;
    }
    // 检测值为value的元素是否存在
    TreeNode find(TreeNode root, char val) {
        if(root==null){
            return null;
        }
        if(root.val==val){
            return root;
        }
     TreeNode  leftNode=   find(root.left,val);
        if( leftNode!=null){
            return leftNode;
        }
        TreeNode  rightNode=find(root.right,val);
     if(rightNode!=null){
            return rightNode;
        }
        return null;
    }


今天的分享先到这里,下期再见!!!

相关文章
|
7月前
|
算法 前端开发
2583. 二叉树中的第 K 大层和
2583. 二叉树中的第 K 大层和
57 0
|
3月前
|
算法
22_最大二叉树
22_最大二叉树
|
7月前
|
存储
|
7月前
|
存储 C++
二叉树
二叉树“【5月更文挑战第22天】”
36 3
二叉树的讲解
1.若规定根节点的层数为1,则一棵非空二叉树的第i层上最多有2^(i-1) 个结点. 2. 若规定根节点的层数为1,则深度为h的二叉树的最大结点数是 2^h-1. 3. 对任何一棵二叉树, 如果度为0其叶结点个数为n0 , 度为2的分支结点个数为02 ,则有n0 =n2 +1 4. 若规定根节点的层数为1,具有n个结点的满二叉树的深度,h= . (ps: 是log以2为底,n+1为对数) 5. 对于具有n个结点的完全二叉树,如果按照从上至下从左至右的数组顺序对所有节点从0开始编号,则对于序号为i的结点有:
二叉树的讲解
二叉树(详解)下
二叉树(详解)
62 0
|
存储
浅谈二叉树
浅谈二叉树
55 1
|
7月前
|
存储
二叉树的实现(下)
二叉树的实现(下)
64 0
|
存储
二叉树的相关列题!!
二叉树的相关列题!!
81 0