首页 前端知识 二叉树的性质和实现

二叉树的性质和实现

2025-03-16 12:03:28 前端知识 前端哥 28 637 我要收藏

二叉树开端

我们要理解二叉树我们可以先看看什么是树,如图

这个树虽然没有什么叶子,不是很好看,但是用在这里刚刚好,我们从局部来看它,随便挑一根树枝,

大概是这样,由一根粗的的主干和一些细的支干构成(枝干和主干在一定条件下面是可以转换的,说一个最通俗的例子就是,有一颗大树,它只有一个主干对吧,我爬上去把他上面的一个小枝干折下来,种在地上,而这个小枝干就变为了一课树,这个枝干也就变为了主干),而这些枝干拼接再主干上面,这样就可以算一颗树,也可以算一颗树上面的一个小枝干(我们把这个主干看为一支粗一点的枝干,就好了)

这个是真实的树,而我们抽象到计算机里面来看

就是和一个树状图很像,而二叉树就是一种特殊的树,就是一个主干,在这个主干上面有且只有两个枝干就叫二叉树

二叉树

完全二叉树与满二叉树

这个就是青天大老爷画的二叉树,我们不看叶子的话,就和我们的定义(我们后面聊)一模一样了,我们把它抽象到计算机里面就是

这个我们也叫满二叉树,而右边少了一点的话,我们就叫完全二叉树而且不能少太多(最后一行),但是右边少几个无所谓,但是左边的一定要完全健在(而这个左边右边的区分,是随便你的,假如你想左边只有一个也可以,你想右边只有一个都是可以的)

二叉树的概念

现在我们再聊一聊二叉树的概念结点的度(别背,后面我们讲怎么理解):

我们先说什么是度,就是一个主干上面有几个枝干,就有几个度,抽象一下就是有几条线连向节点,度就是几,而一棵树的度,就是在每个节点种找出度最大的节点,这个节点的度就是树的度。别的都很通俗易懂了,就不说了。

二叉树的性质

我们主要看3和5。这个3是怎么算的呢,我们首先要知道一个大前提,就是节点等于度加一,我们假设节点有n个,度为m,n = m+1,而因为是二叉树,使用我们节点的度的取值只有0,1,2。所以我们就可以计算一棵树全部的读,度*个数(我们设度为0有z,度为1有x,度为2有y),0*z+1*x+2*y = m,而z+x+y = n,所以z+x+y = 0*z+1*x+2*y+1,就可以得到z =y+1。

我们再看5,这个其实你自己画出来就可以看出来的,但是我要补充一点,如图

我假如我们是从1开始编号,这个二叉树的编号是不是就刚好等于节点的值(这个也是为了方便我们观察),我们可以很轻松的看出1的右节点是自己的2倍,左节点是自己的2倍+1。

接下来,我们来看看二叉树的结构

二叉树的结构

二叉树的结构有两种一种是顺序结构,还有一种是链式结构

顺序结构

顺序结构就是二叉树的数据,我们使用一个数组来存储,这里就有一道经典的面试题,就是106. 从中序与后序遍历序列构造二叉树 - 力扣(LeetCode),而这个是从数组构建二叉树,而从二叉树变为数组就是二叉树的层序遍历(我们再代码实现里面写)(本章出现的算法题,我们再下一篇一起写一写)

链式结构

链式结构就容易很多了(后面我们用二叉树的实现各种操作的时候,也都是用链式结构来实现的)所以现在我就说一个大概就是我创建一个类型他包括一个值,还有两个引用,一个引用指向左节点,另一个指向右节点就没了,就这么简单。现在我们就写一下代码

二叉树的代码实现前中后层序遍历

二叉树的构建,上面我们说了就是一个值,两个引用

    public static class Node{        
        public int data;
        public Node Left;
        public  Node Right;

        Node(int value){
            this.data = value;
            this.Right = null;
            this.Left = null;
        }

 这个就是二叉树的构建

接下来我们,写前序遍历,但是在这之前我想要提一句,二叉树后面要用到递归,而我们为什么要使用递归,我认为递归是一个先进后出的思想,而我们还有别的办法可以实现先进后出那就是栈(Stack),所以我们二叉树的实现也可以使用栈来实现(在下一篇我会写一道使用栈来实现二叉树的遍历)

前序遍历其实,很简单就是我先把值取出来在递归左子树,最后是右子树

        public static void AheadOver(Node head){
            if(head == null)
            {
                return;
            }
            System.out.println(head.data);
            AheadOver(head.Left);
            AheadOver(head.Right);
        }

 而中序遍历就是先递归左子树,在遍历根节点,最后递归右子树,后序遍历就是先遍历左子树,再遍历右子树,最后遍历根节点,这个很简单就直接上代码了

       public static void BetweenOver(Node head){
            if(head == null){
                return;
            }
            BetweenOver(head.Left);
            BetweenOver(head.Right);
            System.out.println(head.data);
        }
        public static void Extremity(Node head){
            if(head == null){
                return;
            }
            Extremity(head.Left);
            System.out.println(head.data);
            Extremity(head.Right);
        }

 现在我们就来写一写层序遍历了,我们再按照上面的思路就不行了,因为链式一般情况下是一直向链表下游前进,在二叉树里面就是(从主干朝向叶子),因此我们实现层序遍历就很复杂,所以就想要一个操作可以把我们遍历的数据记录下来,但是不输出,在我想要他的时候,他再输出。而我们想要存储数据一般是两种操作,栈和队列,那我们要选择那种呢恶魔就要零思考一下,这两种操作的有什么不一样的地方,栈是先进后出,而队列是先进先出,如果说我们使用栈(先进后出,是不是就和我们递归操作差不多了,既然我们递归都不好实现了,所以说我们把栈排除了),所以我们的选择应该是队列,那要实现层序,我们可不可以出一行,进一行呢(好像可以,因为我们只需要对出的那一行的每个元素进行访问,再把他的左右子树添加到队尾是不是就可以了),

        public static void ToString(Node head){
            Queue<Node> q = new LinkedList<>();
            q.offer(head);
            while (q.peek() != null){
                Node node = q.poll();
                System.out.println(node.data);
                q.offer(node.Left);
                q.offer(node.Right);
            }
        }
        //这个是层序遍历

 这篇要写的就这么多,下一篇,我找一些二叉树的经典算法题,让我们来好好动动脑子。

转载请注明出处或者链接地址:https://www.qianduange.cn//article/23898.html
标签
评论
发布的文章

二叉树的性质和实现

2025-03-16 12:03:28

5G智慧室分

2025-03-16 12:03:28

大家推荐的文章
会员中心 联系我 留言建议 回顶部
复制成功!