当前位置：首页 > news >正文

代码随想录---二叉树的总结和二叉树的定义

news 2025/6/20 6:37:39

二叉树的种类：

满二叉树：树的所有节点都是满，即都有左右孩子。

这棵二叉树为满二叉树，也可以说深度为k，有2^k-1个节点的二叉树。

完全二叉树：完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^(h-1) 个节点。

二叉搜索树：二叉搜索树是一颗排序树。

若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉排序树

平衡二叉搜索树：又被称为AVL（Adelson-Velsky and Landis）树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

二叉树的存储方式：

二叉树可以链式存储，也可以顺序存储。

那么链式存储方式就用指针，顺序存储的方式就是用数组。

链式存储：使用链表

顺序存储：使用数组的方式

查找节点：如果父节点的数组下标是 i，那么它的左孩子就是 i * 2 + 1，右孩子就是 i * 2 + 2。

但是用链式表示的二叉树，更有利于我们理解，所以一般我们都是用链式存储二叉树。

二叉树的遍历方式：

二叉树主要有两种遍历方式：

深度优先遍历：先往深走，遇到叶子节点再往回走。
广度优先遍历：一层一层的去遍历。

那么从深度优先遍历和广度优先遍历进一步拓展，才有如下遍历方式：

深度优先遍历
- 前序遍历（递归法，迭代法）
- 中序遍历（递归法，迭代法）
- 后序遍历（递归法，迭代法）
广度优先遍历
- 层次遍历（迭代法）

前中后遍历其实就是看根节点的位置。在中间就是中序；在前面就前序；在后面就是后序遍历。

前序遍历：中左右
中序遍历：左中右
后序遍历：左右中

二叉树的定义：

java的定义：

public class TreeNode {int value;TreeNode left;TreeNode right;//无参数构造器：TreeNode(){}TreeNode(int value){this.value=value;}//有参数构造器：public TreeNode(int value, TreeNode left, TreeNode right) {this.value = value;this.left = left;this.right = right;}
}

python的定义：

class TreeNode: def __init__(self, value):self.value = valueself.left = Noneself.right = None

C++的定义：

struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};