代码随想录 第8章 二叉树

1、理论知识

(1)、满二叉树

如果一棵二叉树只有度为0的节点和度为2的节点,并且度为0的节点在同一层上,则这棵二叉树为满二叉树。

(2)、完全二叉树

除了底层节点可能没有填满,其余每层的节点数都达到了最大值,并且底层的节点都集中在该层最左边的若干位置。

(3)、二叉搜索树

前面介绍的二叉树都没有数值,而二叉搜索树是有数值的。二叉搜索树是一个有序树,满足如下规则:

一、若它的左子树不为空,则左子树上所有节点的值都小于它的根节点的值。

二、弱它的右子树不为空,则右子树上所有节点的值都大于它的根节点的值。

三、它的左、右子树也分别为二叉排序树。

(4)、平衡二叉搜索树

平衡二叉搜索树又称为AVL树,它是一棵空树,或者它的左右两个字树的高度差的绝对值不超过1,并且两个字树都是一棵平衡二叉树。

2、二叉树的遍历

深度优先:递归、迭代;

广度优先:迭代;

编程语言都是通过栈这种数据结构实现递归的,也就是说,前序、中序、后序遍历都可以通过栈使用非递归的方式实现。

而广度优先遍历一般使用队列实现,这也是由队列先进先出的特点决定的,因为通过先进先出的结构,才能一层一层地遍历二叉树。文章来源地址https://www.uudwc.com/A/8dnw9/

原文地址:https://blog.csdn.net/qq_32565805/article/details/133325509

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请联系站长进行投诉反馈,一经查实,立即删除!

h
上一篇 2023年09月27日 16:33
蓝桥杯 题库 简单 每日十题 day10
下一篇 2023年09月27日 17:33