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

网站类别划分/外贸b2b平台都有哪些网站

news 2025/7/2 2:40:39

网站类别划分,外贸b2b平台都有哪些网站,学做美食看哪个网站,网站怎么做文字禁止复制本博客将介绍二叉树的基本知识，包括二叉树的概念、特性、模拟实现。一.二叉树概述 1.二叉树的定义要明白二叉树是什么，就要明白树是什么。树：一种非线性数据结构，由节点（Node）和边（Edge&a…

本博客将介绍二叉树的基本知识，包括二叉树的概念、特性、模拟实现。

一.二叉树概述

1.二叉树的定义

要明白二叉树是什么，就要明白树是什么。

树：一种非线性数据结构，由节点（Node）和边（Edge）构成。

节点好比一颗树的叶子，边好比一棵树的枝干。

关键概念：

子树（Subtree）：以某节点为根的树
兄弟节点（Siblings）：同一父节点的子节点
叶子结点或终端结点：度为0的结点称为叶结点
双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点
根结点：一棵树中，没有双亲结点的结点
孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点
度（Degree）：节点的子节点数量
树的度：一棵树中，所有结点度的最大值称为树的度
层级（Level）：根为第1层，子节点层级=父节点层级+1
高度（Height）：从某节点到最远叶子节点的边数（叶子节点高度=0）
深度（Depth）：从根到该节点的边数（根深度=0）
森林：由m（m>=0）棵互不相交的树组成的集合称为森林

树的特点：

有且仅有一个根节点（Root）（无父节点）
除根节点外，每个节点有且仅有一个父节点（Parent）
节点可以有0或多个子节点（Child）
没有子节点的节点称为叶子节点（Leaf）树

二叉树：

每个节点最多有两个子节点，称为左子节点和右子节点
子树有严格的左右之分（即使单子树也要明确左右）

如下就是一颗简单的二叉树：

2.二叉树的分类

（1）满二叉树（Full Binary Tree）

定义：所有层的节点都达到最大数量
特性：
- 第k层最多有2**(k-1)个节点
- 高度为h的满二叉树总节点数2**k-1

如下就是一个满二叉树：

（2）完全二叉树（Complete Binary Tree）

定义：除最后一层外全满，最后一层节点左对齐
特性：
- 适合用数组存储（父节点索引i，左子=2i+1，右子=2i+2）
- 堆结构的基础形态

如下就是一个完全二叉树：

3.二叉树的数学特性

非空二叉树第k层最大节点数：2*k−1
高度为h的二叉树最大节点数：2**h−1
具有n个节点的二叉树最小高度：h=⌈log⁡2(n+1)⌉（向上取整）
设叶子节点数为n0，度为2的节点数为n2，则：n0=n2+1

4.二叉树的遍历

二叉树有4种主要遍历方式：前序遍历、中序遍历、后序遍历、层序遍历

前三种又称为深度优先遍历，层序遍历又称为广度优先遍历。

ps：遍历本质是递归遍历，结合之后的代码更好理解。

前序遍历(Preorder Traversal)——访问根结点--->根的左子树--->根的右子树

如下访问顺序为1->7

中序遍历(Inorder Traversal)——根的左子树--->根节点--->根的右子树。

后序遍历(Postorder Traversal)——根的左子树--->根的右子树--->根节点

层序遍历：

按层级从左到右访问节点

二.二叉树的模拟实现

二叉树有2种模拟实现方式，一种是链式结构的实现，一种是基于堆（稍后介绍）的实现。

1.基于链式结构的二叉树

由于树是靠边连在一起的，于是我们自然想到了链式结构，用索引套用把节点（Node）连接在一起：

（1）存储结构

public class MyBinaryTree {// 节点定义static class TreeNode {int val;TreeNode left;TreeNode right;public TreeNode(int val) {this.val = val;}}private TreeNode root; // 根节点

（2）遍历

前序遍历(Preorder)

void preOrder(TreeNode root) {if (root == null) return;System.out.print(root.val + " "); // 访问根节点preOrder(root.left);               // 递归左子树preOrder(root.right);              // 递归右子树
}

中序遍历(Inorder)

void inOrder(TreeNode root) {if (root == null) return;inOrder(root.left);                // 递归左子树System.out.print(root.val + " "); // 访问根节点inOrder(root.right);               // 递归右子树
}

后序遍历(Postorder)

void postOrder(TreeNode root) {if (root == null) return;postOrder(root.left);              // 递归左子树postOrder(root.right);              // 递归右子树System.out.print(root.val + " "); // 访问根节点
}

层序遍历

层序遍历稍微复杂点，他调用了一个队列来存储元素：

void levelOrder(TreeNode root) {Queue<TreeNode> queue = new LinkedList<>();if (root != null) queue.offer(root);while (!queue.isEmpty()) {TreeNode node = queue.poll();System.out.print(node.val + " ");if (node.left != null) queue.offer(node.left);if (node.right != null) queue.offer(node.right);}
}

第一步，根节点入队（根节点非null时）

第二步，循环执行队首出队并打印输出，出队节点的子节点入队

这样就可以按层遍历节点了。

如下：

此时出队节点4无子节点，则不执行入队，其余节点同理出队，最后就可以得到层序遍历的结果：

基于以上遍历，我们可以写出：

（3）按层序的空位插入

public void insert(int val) {TreeNode newNode = new TreeNode(val);if (root == null) {root = newNode;return;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {TreeNode current = queue.poll();if (current.left == null) {current.left = newNode;return;} else {queue.offer(current.left);}if (current.right == null) {current.right = newNode;return;} else {queue.offer(current.right);}}
}

（4）查找节点

public boolean contains(int val) {return containsRec(root, val);
}private boolean containsRec(TreeNode node, int val) {if (node == null) return false;if (node.val == val) return true;return containsRec(node.left, val) || containsRec(node.right, val);
}

（5）删除节点

/*** 删除节点（普通二叉树）*/
public void delete(int val) {root = deleteRec(root, val);
}private TreeNode deleteRec(TreeNode node, int val) {if (node == null) return null;if (node.val == val) {// Case 1: 叶子节点if (node.left == null && node.right == null) {return null;}// Case 2: 单子节点if (node.left == null) {return node.right;}if (node.right == null) {return node.left;}// Case 3: 双子节点（找右子树最小值替换）TreeNode minNode = findMin(node.right);node.val = minNode.val;node.right = deleteRec(node.right, minNode.val);} else {node.left = deleteRec(node.left, val);node.right = deleteRec(node.right, val);}return node;
}private TreeNode findMin(TreeNode node) {while (node.left != null) {node = node.left;}return node;
}

（6）计算树高

public int height() {return heightRec(root);
}private int heightRec(TreeNode node) {if (node == null) return 0;return 1 + Math.max(heightRec(node.left), heightRec(node.right));
}