跳到主要内容

· 阅读需 7 分钟

前言

目前 React 领域最热门的话题是 React 18 版本。 特别是,该版本将引入一组所谓的并发渲染功能。 这些特性允许开发者选择 React 的并发渲染机制。 这种机制为 React 开发人员提供了一个全新的机会来控制和优化最终用户的体验。 这绝对是自 hooks 以来,我们在 React 世界中将收到的最令人兴奋的事情之一。

因此,你很可能以前听说过并发渲染。 可能是关于它的文章、围绕它的 API,或者 React 18 将为它带来什么。 但是,你可能会对并发渲染的基础知识感到疑惑。 究竟什么是并发渲染,为什么我们真的需要它?

为了帮助你理解,本文将讨论这些问题。 通过研究它的目的、它试图解决什么问题以及它是如何解决它的,你将获得有关并发渲染主题的基础知识。

为什么我们需要并发渲染?

React 当前形式的问题之一是所有状态更新都是同步的。 这意味着 React 只能一一处理它们。 在许多用例和现实生活场景中,这非常好,不会对用户体验施加任何限制。

但是在 React 想要获取与其当前正在处理的状态更新不同的状态更新的情况下,现在这显然是不可能的。 React 在启动后无法中断、暂停或放弃渲染更新——这是一个阻塞的进程。

从本质上讲,这对优化用户体验的过程设置了上限。 虽然很高,但还是有上限的。 每个状态更新都被视为同等重要,即使这不适用于用户体验。 某些更新可能比其他更新具有更高的优先级或紧迫性。 与可能的情况相比,不能这样做实际上会对用户体验产生巨大的负面影响,这是次优的。

什么是并发渲染?

并发渲染是一组功能,允许你的 React 项目选择所谓的可中断渲染。 与之前 React 被阻塞的渲染过程相反,这使得渲染过程可以从 React 端中断,这正是并发渲染的用武之地。这为 React 开发人员进一步提升 React 应用程序的用户体验开辟了许多新的可能性。

它允许 React 一次处理多个状态更新。 然而,这并不意味着 React 会突然同时执行所有排队状态更新。 相反,选择并发渲染允许 React 考虑其最佳行动方案。 幸运的是,这也是我们作为开发人员可以控制的事情。

假设 React 当前正在处理状态更新并且有一个不同的更新进来,那么 React 可以根据变量的因素做出不同的决定。 如果新的传入状态更新被标记为同等或不那么紧急,那么与之前的渲染过程相比没有任何变化。 React 将像往常一样继续当前状态更新。 完成后,它将获取新的状态更新。

但是如果新传入的状态更新被标记为更紧急,那么 React 可以决定暂停当前状态更新并首先处理传入的更新。 在完成新的更紧急的状态更新后,React 会回到原来的状态更新。 如果它确定有必要恢复它,它会这样做。 如果事实证明状态更新现在无关紧要,它可以决定完全放弃它。

下一步是什么?

本文简要介绍了 React 18 将为 React 开发领域带来的最激动人心的功能之一,即并发渲染,并让你快速了解整个主题。 使用本文中的知识,你应该知道什么是并发渲染,了解它试图解决的问题,并大致了解它的工作原理。

幸运的是,并发渲染并不止于此。 虽然并发渲染还有很多方面需要理解或深入研究,但本文作为介绍以进入整个主题,并允许你从这里开始进一步探索 React 18。

下面准备了一些资料 这里介绍了 React 18 中引入的三个新 API。所有这些 API 都是允许某些开发人员在某些场景中选择并发渲染的hook。 官方的 React 18 公告是了解更多关于 React 18、不同特性、如何采用它以及关于即将发布的 React 版本的所有信息的好地方。 React 工作组是了解更多技术方面、获得更多指导、了解不同 API 和特性背后的思维过程以及总体上更深入地了解 React 18 中所有内容的好地方。 这就是全部! 现在你已经牢牢掌握了并发渲染的主题,在 React 18 中为你打开了一个全新的世界供你探索。走出去,探索并享受这个新的冒险!

· 阅读需 15 分钟

前言

本文我们讨论如何在 React Router 6 中使用搜索参数。搜索参数是一项强大的功能,它使你能够捕获 URL 中的状态。通过在 URL 中包含状态,你可以与其他人实现共享。例如,如果应用程序显示产品目录,开发人员将使用户能够搜索它。在 React 中,这将转换为项目列表(此处为:产品)和用于过滤它们的 HTML 输入字段。

现在,React 开发人员很有可能会使用 React 的 useState Hook 来管理这种搜索状态。这对这个用户来说很好,但不适合与其他用户共享。

因此,一个不错的方式是在 URL 中管理搜索状态,因为这样搜索状态就可以与其他用户共享。如果一个用户按标题(例如“Rust”)搜索项目列表,则搜索参数将作为键值对附加到 URL,例如 /bookshelf?title=Rust,因为可以与另一个用户共享。所以获得链接的其他用户将在其页面上看到相同的过滤项目列表。

React Router 从状态到 URL

首先,我们将实现上一个所设想的那样,其中有一个项目列表,并通过 HTML 输入字段进行搜索。我们不会使用 React 的 useState Hook 来捕获搜索状态,而是使用 React Router 来获取可共享的 URL。 App 组件如下所示,类似于前面提到的 React Router 教程中的 App 组件:

const App = () => {
return (
<>
<h1>React Router</h1>

<nav>
<Link to="/home">Home</Link>
<Link to="/bookshelf">Bookshelf</Link>
</nav>

<Routes>
<Route index element={<Home />} />
<Route path="home" element={<Home />} />
<Route path="bookshelf" element={<Bookshelf />} />
<Route path="*" element={<NoMatch />} />
</Routes>
</>
);
};

虽然 Home 和 NoMatch 组件只是具有任何实现的占位符组件,但我们将关注 Bookshelf 组件,它将Books显示为列表组件。这些Books示例数据可以从远程 API(或模拟 API)获取:

const Bookshelf = () => {
const books = [
{
title: 'The Road to Rust',
isCompleted: false,
},
{
title: 'The Road to React',
isCompleted: true,
},
];

return (
<>
<h2>Bookshelf</h2>

<ul>
{books.map((book) => (
<li key={book.title}>{book.title}</li>
))}
</ul>
</>
);
};

为了使用户能够通过不区分大小写的标题匹配来过滤此列表,我们使用 React 的 useState Hook 和 HTML 输入字段。最后,事件处理程序将从输入字段中读取值并将其写入状态:

const byTitle = (title) => (book) =>
book.title.toLowerCase().includes((title || '').toLowerCase());

const Bookshelf = () => {
const books = [...];

const [title, setTitle] = React.useState('');

const handleTitle = (event) => {
setTitle(event.target.value);
};

return (
<>
<h2>Bookshelf</h2>

<input type="text" value={title} onChange={handleTitle} />

<ul>
{books.filter(byTitle(title)).map((book) => (
<li key={book.title}>{book.title}</li>
))}
</ul>
</>
);
};

这就是就是“在 React 中使用状态”的版本。接下来,我们要使用 React Router 来在 URL 中捕获此状态。React Router 为我们提供了 useSearchParams hook,它几乎可以用来替代 React 的 useState hook:

import * as React from 'react';
import {
Routes,
Route,
Link,
useSearchParams,
} from 'react-router-dom';

...

const Bookshelf = () => {
const books = [...];

const [search, setSearch] = useSearchParams();

const handleTitle = (event) => {
setSearch({ title: event.target.value });
};

return (
<>
<h2>Bookshelf</h2>

<input
type="text"
value={search.get('title')}
onChange={handleTitle}
/>

<ul>
{books.filter(byTitle(search.get('title'))).map((book) => (
<li key={book.title}>{book.title}</li>
))}
</ul>
</>
);
};

由于以下两点,它不能直接替代 React 的 useState Hook。首先,它对一个对象而不是字符串进行操作,因为一个 URL 可以有多个搜索参数(例如 /bookshelf?title=Rust&rating=4),因此每个搜索参数都成为该对象中的一个属性(例如{ title: 'Rust', rating: 4 })。

如果我们将 React 的 useState Hook 与对象而不是字符串一起使用,它本质上与我们之前的实现类似:

const [search, setSearch] = React.useState({ title: '' });

然而,即使 useSearchParams 返回的有状态值是对象类型(typeof search === 'object'),它仍然不能像单纯的 JavaScript 对象数据结构那样访问,因为它是 URLSearchParams 的一个实例。因此我们需要调用它的 getter 方法(例如 search.get('title'))。

其次,React Router 的 useSearchParams Hook 不接受初始状态,因为初始状态来自 URL。因此,当用户与搜索参数(例如 /bookshelf?title=Rust)共享 URL 时,另一个用户将从 React Router 的 Hook 获得 { title: 'Rust' } 作为初始状态。当应用程序将用户导航到带有搜索参数且设置了可选搜索参数的路线时,也会发生同样的情况。

这就是使用状态的 URL 而不是使用 React 的状态管理 Hook 之一。它极大地改善了用户体验,因为 URL 变得更加特定于用户在页面上看到的内容。因此,这个特定的 URL 可以与其他用户共享,他们将看到具有相同 UI 的页面。

URLSEARCHPARAMS 转换为对象

如果你在处理 React Router 的 useSearchParams Hook 时不想使用 URLSearchParams,你可以编写一个自定义hook,它返回一个 JavaScript 对象而不是 URLSearchParams 的实例:

const useCustomSearchParams = () => {
const [search, setSearch] = useSearchParams();
const searchAsObject = Object.fromEntries(
new URLSearchParams(search)
);

return [searchAsObject, setSearch];
};

const Bookshelf = () => {
const books = [...];

const [search, setSearch] = useCustomSearchParams();

const handleTitle = (event) => {
setSearch({ title: event.target.value });
};

return (
<>
<h2>Bookshelf</h2>

<input
type="text"
value={search.title}
onChange={handleTitle}
/>

<ul>
{books.filter(byTitle(search.title)).map((book) => (
<li key={book.title}>{book.title}</li>
))}
</ul>
</>
);
};

然而,这个自定义hook应该有一点不足,因为它不适用于重复键(例如带有 ?editions=1&editions=3 的数组搜索参数)和使用复杂 URL 时的其他边界情况。

一般来说,仅使用 React Router 的 useSearchParams Hook(或这个自定义的 useCustomSearchParams hook)并不能为你提供 URL 状态管理的完整体验,因为它仅可用于字符串而不能用于其他数据类型。我们将在接下来的部分中探讨这一点以及如何解决这个问题。

搜索参数与保留数据类型

并非所有状态都只包含字符串。在前面使用 React Router 的搜索参数的例子中,我们使用了一个字符串(这里是:title),它被编码到 URL 中。当从 URL 解码这个字符串时,我们将默认得到一个字符串——这在我们的例子中有效,因为我们需要一个字符串。但是其他原始数据类型如数字或布尔值呢?更不用说复杂的数据类型,例如数组。

为了探索解决这个,我们将通过实现一个复选框来继续之前的示例。我们将使用这个复选框组件并将其连接到 React Router 的搜索参数:

const bySearch = (search) => (book) =>
book.title
.toLowerCase()
.includes((search.title || '').toLowerCase()) &&
book.isCompleted === search.isCompleted;

const Bookshelf = () => {
const books = [...];

const [search, setSearch] = useCustomSearchParams();

const handleTitle = (event) => {
setSearch({ title: event.target.value });
};

const handleIsCompleted = (event) => {
setSearch({ isCompleted: event.target.checked });
};

return (
<>
<h2>Bookshelf</h2>

<input
type="text"
value={search.title}
onChange={handleTitle}
/>

<Checkbox
label="Is Completed?"
value={search.isCompleted}
onChange={handleIsCompleted}
/>

<ul>
{books.filter(bySearch(search)).map((book) => (
<li key={book.title}>{book.title}</li>
))}
</ul>
</>
);
};

在浏览器中实验以下。你将看到对 isCompleted 布尔值的搜索不起作用,因为来自我们的搜索对象的 isCompleted 被表示为一个字符串,如“true”或“false”。我们可以通过增强我们的自定义hook来规避这一点:

const useCustomSearchParams = (param = {}) => {
const [search, setSearch] = useSearchParams();
const searchAsObject = Object.fromEntries(
new URLSearchParams(search)
);

const transformedSearch = Object.keys(param).reduce(
(acc, key) => ({
...acc,
[key]: param[key](acc[key]),
}),
searchAsObject
);

return [transformedSearch, setSearch];
};

const PARAMS = {
BooleanParam: (string = '') => string === 'true',
};

const Bookshelf = () => {
const books = [...];

const [search, setSearch] = useCustomSearchParams({
isCompleted: PARAMS.BooleanParam,
});

...

return (...);
};

本质上,新版本的自定义hook采用具有可选转换功能的对象。它遍历每个转换函数,如果找到转换函数和搜索参数之间的匹配项,则将该函数应用于搜索参数。在这种情况下,我们将字符串布尔值(“true”或“false”)转换为实际的布尔值。如果没有找到匹配项,它只返回原始搜索参数。因此我们不需要标题的转换函数,因为它是一个字符串并且可以继续为字符串。

通过拥有自定义hook的实现细节,我们还可以创建其他转换器函数(例如 NumberParam),从而填补缺失数据类型转换(例如数字)的空白:

const PARAMS = {
BooleanParam: (string = '') => string === 'true',
NumberParam: (string = '') => (string ? Number(string) : null),
// other transformation functions to map all data types
};

开源组件中use-query-params这个库完美的解决这个问题。

React Router 使用搜索参数

use-query-params 库非常适合将复杂的 URL 用作超越字符串的状态的用例。在本节中,我们将探索 use-query-params 库,从而摆脱我们自定义的 useSearchParams hook。

自己按照库的安装说明进行操作。你需要在命令行上安装该库并在 React 项目的根级别实例化它:

import React from 'react';
import ReactDOM from 'react-dom';
import { BrowserRouter, Route } from 'react-router-dom';
import { QueryParamProvider } from 'use-query-params';

import App from './App';

ReactDOM.render(
<BrowserRouter>
<QueryParamProvider ReactRouterRoute={Route}>
<App />
</QueryParamProvider>
</BrowserRouter>,
document.getElementById('root')
);

然而, use-query-params 还没有正确适应 React Router 6。因此,你可能会看到以下错误弹出:“<Route> 仅用作 <Routes> 元素的子元素,永远不会直接呈现。请将你的 <Route> 包装在 <Routes> 中。”。因此,在根级别调整你的代码:

import React from 'react';
import ReactDOM from 'react-dom';
import {
BrowserRouter,
useNavigate,
useLocation,
} from 'react-router-dom';
import { QueryParamProvider } from 'use-query-params';

import App from './App';

const RouteAdapter = ({ children }) => {
const navigate = useNavigate();
const location = useLocation();

const adaptedHistory = React.useMemo(
() => ({
replace(location) {
navigate(location, { replace: true, state: location.state });
},
push(location) {
navigate(location, { replace: false, state: location.state });
},
}),
[navigate]
);
return children({ history: adaptedHistory, location });
};

ReactDOM.render(
<BrowserRouter>
<QueryParamProvider ReactRouterRoute={RouteAdapter}>
<App />
</QueryParamProvider>
</BrowserRouter>,
document.getElementById('root')
);

现在你可以使用 use-query-params 在 React 中进行强大的 URL 状态管理。你所要做的就是使用新的 useQueryParams 钩子。另请注意,与我们的自定义钩子相比,你还需要“转换”字符串搜索参数:

import * as React from 'react';
import { Routes, Route, Link } from 'react-router-dom';
import {
useQueryParams,
StringParam,
BooleanParam,
} from 'use-query-params';

...

const Bookshelf = () => {
const books = [...];

const [search, setSearch] = useQueryParams({
title: StringParam,
isCompleted: BooleanParam,
});

...

return (...);
};

你还可以提供合理的默认值。例如,此时在没有搜索参数的情况下导航到 /bookshelf 时,title 和 isComplete 将是未定义的。但是,如果你希望它们至少是标题的空字符串和 isComplete 的 false,你可以提供这些默认值,例如:

import * as React from 'react';
import { Routes, Route, Link } from 'react-router-dom';
import {
useQueryParams,
StringParam,
BooleanParam,
withDefault
} from 'use-query-params';

...

const Bookshelf = () => {
const books = [...];

const [search, setSearch] = useQueryParams({
title: withDefault(StringParam, ''),
isCompleted: withDefault(BooleanParam, false),
});

...

return (...);
};

还有一件值得注意的事情要提到:目前,use-query-params 使用默认的“push in”模式,这意味着每次附加搜索参数时,它不会覆盖其他搜索参数。因此,你在更改其中之一的同时保留所有搜索参数。但是,如果这不是你想要的行为,你还可以更改模式(例如,更改为“push”),这样将不再保留以前的搜索参数(尽管这在我们的场景中没有意义):

const Bookshelf = () => {
...

const handleTitle = (event) => {
setSearch({ title: event.target.value }, 'push');
};

const handleIsCompleted = (event) => {
setSearch({ isCompleted: event.target.checked }, 'push');
};

...

return (...);
};

除了我们在这里使用的两种数据类型转换之外,还有对数字、数组、对象等的转换。例如,如果你希望在 React 中有一个可选择的表,你可能希望将表中的每个选定行表示为数组中的标识符(在 use-query-params 中,它是 ArrayParam 转换)映射到实际 URL .然后你可以与另一个用户共享此 URL,该用户将从所选行开始。

使用 URL 作为状态是改善用户体验的方式。在处理单个或多个字符串状态时,React Router 的搜索参数为你提供了一个很好的体验。但是,一旦你想保留映射到 URL 的数据类型,你可能希望使用诸如 use-query-params 之类的库在 React 中进行复杂的 URL 状态管理。

参考

use-query-params

· 阅读需 11 分钟

前言

本文教你如何在 React Router 6 中使用嵌套路由。嵌套路由是一个强大的功能。虽然大多数人认为 React Router 只会在页面之间路由使用,但它也允许用户根据当前路由交换视图的特定片段。例如,在用户页面上,会显示多个选项卡(例如个人资料、帐户)以浏览用户信息。通过单击这些选项卡,浏览器中的 URL 会发生变化,但不会替换整个页面,只会替换选项卡的内容。 下面我们将使用 React Router 重新创建这个场景。为了说明这是如何工作的,以及如何自己在 React 中逐步实现嵌套路由,我们将从以下示例开始:

import { Routes, Route, Link } from 'react-router-dom';

const App = () => {
return (
<>
<h1>React Router</h1>

<nav>
<Link to="/home">Home</Link>
<Link to="/user">User</Link>
</nav>

<Routes>
<Route index element={<Home />} />
<Route path="home" element={<Home />} />
<Route path="user" element={<User />} />
<Route path="*" element={<NoMatch />} />
</Routes>
</>
);
};

在这个函数组件中,我们使用了 React Router 中的 Link 和 Route 组件,用于 home/ 和 user/ 路由。此外,我们有一个加载了 Home 组件的所谓的索引路由和一个加载了 NoMatch 组件的所谓的 No Match 路由。两者都作为备选路线。从这里开始,我们将了解嵌套路由的概念。

React Router 中的嵌套路由

我们将继续处理 User 组件,这是我们希望通过选项卡进行嵌套路由的地方。因此,我们将实例化一组新的 Link 组件(将是我们的无样式选项卡),用于将用户导航到他们的个人资料和他们的帐户。

const User = () => {
return (
<>
<h1>User</h1>

<nav>
<Link to="/user/profile">Profile</Link>
<Link to="/user/account">Account</Link>
</nav>
</>
);
};

我们在这里使用绝对路径将用户从他们的个人资料导航到他们的帐户,反之亦然,但是,我们也可以使用相对路径作为最佳实践。因为 User 组件位于 /user 路由中,所以 Link 组件可以预测它们的父路由(这里是:/user),并且只需将相对路径(这里:profile 和 account)附加到它(例如 /user/profile):

const User = () => {
return (
<>
<h1>User</h1>

<nav>
<Link to="profile">Profile</Link>
<Link to="account">Account</Link>
</nav>
</>
);
};

此时,当我们尝试在 React 应用程序中单击这些链接之一时,我们将被困在我们的 No Match Route 中。这告诉我们,我们还没有将这些路由(此处:/user/profile 和 /user/account)映射到任何实际的路由组件。因此,我们将这两个新路由作为所谓的嵌套路由添加到我们的 /user 路由中:

const App = () => {
return (
<>
<h1>React Router</h1>

<nav>
<Link to="/home">Home</Link>
<Link to="/user">User</Link>
</nav>

<Routes>
<Route index element={<Home />} />
<Route path="home" element={<Home />} />
<Route path="user" element={<User />}>
<Route path="profile" element={<Profile />} />
<Route path="account" element={<Account />} />
</Route>
<Route path="*" element={<NoMatch />} />
</Routes>
</>
);
};

Route 组件现在以一对一的关系映射到 Link 组件。但是,可以有多个 Link 组件链接到同一个路由,因此它实际上是一对多的关系。

在浏览器中对此进行测试时,我们将看到仅显示 User 组件,而不会显示其嵌套的 Profile 组件,也不会显示其嵌套的 Account 组件。我们缺少 React Router 的关键 Outlet 组件:

import { Routes, Route, Link, Outlet } from 'react-router-dom';

...

const User = () => {
return (
<>
<h1>User</h1>

<nav>
<Link to="profile">Profile</Link>
<Link to="account">Account</Link>
</nav>

<Outlet />
</>
);
};

Outlet 组件从父 Routes 的 Route 组件集合中使用其各自的组件(此处为 Profile 或 Account 组件)呈现匹配的子路由。 如果没有 /profile 和 /account 路由匹配(例如 /user/settings),你将只看到 User 组件出现。为避免这种情况,你可以添加索引和无匹配路由的组合。之后,默认路由将是 /profile 路由:

const App = () => {
return (
<>
<h1>React Router</h1>

<nav>
<Link to="/home">Home</Link>
<Link to="/user">User</Link>
</nav>

<Routes>
<Route index element={<Home />} />
<Route path="home" element={<Home />} />
<Route path="user" element={<User />}>
<Route index element={<Profile />} />
<Route path="profile" element={<Profile />} />
<Route path="account" element={<Account />} />
<Route path="*" element={<NoMatch />} />
</Route>
<Route path="*" element={<NoMatch />} />
</Routes>
</>
);
};

虽然 User 组件总是将选项卡呈现为导航,但其内容(Outlet)被匹配的嵌套路由(基于 /user/profile 或 /user/account 路由的 Profile 或 Account 组件)替换。如果在访问 /user 路由时这些路由都不匹配,应用程序将显示 Profile 组件(如果路由与 /user 完全匹配)或 NoMatch 组件(如果路由不匹配,例如 /user/setting)出现。

React router 中的 动态嵌套路由

在嵌套路由的下一个示例中,我们将从 App 组件中开始。这次我们不想像之前那样渲染静态嵌套路由(例如 /user/profile),而是基于标识符的动态嵌套路由(例如 /users/1 用于显示具有标识符 1 并因此匹配此路由的用户)。因此,我们将示例从单用户路由 (/user) 调整为多用户路由 (/user)。

const App = () => {
const users = [
{ id: '1', fullName: 'Robin Wieruch' },
{ id: '2', fullName: 'Sarah Finnley' },
];

return (
<>
<h1>React Router</h1>

<nav>
<Link to="/home">Home</Link>
<Link to="/users">Users</Link>
</nav>

<Routes>
<Route element={<Layout />}>
<Route index element={<Home />} />
<Route path="home" element={<Home />} />
<Route path="users" element={<Users users={users} />} />
<Route path="*" element={<NoMatch />} />
</Route>
</Routes>
</>
);
};

Users 组件成为 React 中的列表组件,因为它遍历每个用户并为其返回 JSX。在这种情况下,它不仅仅是一个列表,因为我们将 React Router 的 Link 组件添加到组合中。 Link 组件中的相对路径提示相应的嵌套(此处:/${user.id} 嵌套在 /users 中)但动态(此处:/${user.id})路由:

const Users = ({ users }) => {
return (
<>
<h2>Users</h2>

<ul>
{users.map((user) => (
<li key={user.id}>
<Link to={user.id}>
{user.fullName}
</Link>
</li>
))}
</ul>
</>
);
};

通过拥有这个新的动态嵌套路由,我们需要在 App 组件中为它创建一个匹配的嵌套路由组件。首先,由于它是 /users 路由的所谓嵌套路由(或子路由),我们可以将它嵌套在相应的父路由组件中。此外,由于它是所谓的动态路由,它使用定义为 :userId 的动态路由,而用户的标识符则动态匹配(例如,id 为 '1' 的用户将与 /users/1 匹配):

const App = () => {
const users = [
{ id: '1', fullName: 'Robin Wieruch' },
{ id: '2', fullName: 'Sarah Finnley' },
];

return (
<h1>React Router</h1>

<nav>...</nav>

<Routes>
<Route element={<Layout />}>
<Route index element={<Home />} />
<Route path="home" element={<Home />} />
<Route path="users" element={<Users users={users} />}>
<Route path=":userId" element={<User />} />
</Route>
<Route path="*" element={<NoMatch />} />
</Route>
</Routes>
);
};

这样,User 组件就变成了 Users 组件的嵌套路由。因此,再次在 Outlet 组件的帮助下渲染其嵌套路由是用户组件的责任——再次渲染匹配的子路由:

import { Routes, Route, Link, Outlet } from 'react-router-dom';

...

const Users = ({ users }) => {
return (
<>
<h2>Users</h2>

<ul>...</ul>

<Outlet />
</>
);
};

接下来,我们将声明缺少的 User 组件,只要用户的标识符在 URL 中匹配,该组件就会通过 Users 组件中的 Outlet 嵌套。在这个新组件中,我们可以使用 React Router 的 useParams Hook 从 URL 中获取相应的 userId(等于 :userId):

import {
...
useParams,
} from 'react-router-dom';

...

const User = () => {
const { userId } = useParams();

return (
<>
<h2>User: {userId}</h2>

<Link to="/users">Back to Users</Link>
</>
);
};

我们已经看到了如何通过将一个 Route 组件(或多个 Route 组件)嵌套在另一个 Route 组件中来创建嵌套路由。前者是嵌套的子路由,后者是渲染封闭组件的父路由,该组件必须使用 Outlet 组件来渲染实际匹配的子路由。

此外,我们还看到了如何通过在路由的路径属性中使用冒号(例如:userId)来创建动态路由。本质上, :userId 充当任何标识符的星号。在我们的例子中,我们使用 Link 组件将用户导航到 /users/:userId 路由,其中​​ :userId 代表实际用户的标识符。最后,我们总是可以通过使用 React Router 的 useParams Hook 从 URL 中获取动态路径(称为参数或 params)。

如果你碰巧将 React Router 用于你的 React 应用程序,嵌套路由可以通过让你的用户访问你的应用程序非常特定的部分,同时将这些部分作为 URL 共享,从而极大地提升你的用户体验。

· 阅读需 22 分钟

前言

不久前,React Router 库更新到了第 6 版,随之而来的是一些有趣的变化,本文将讲述React Router 6的一些新特性及使用的案例。 接下来是一些准备工作:

  1. 首先需要创建一个新的 React 项目(例如 create-react-app)。然后,按照官方文档安装 React Router。
    yarn add react-router-dom@latest    
    我们这里安装的是6.0.2版本。
  2. 第一个实现细节将告诉我们的 React 应用程序我们想要使用 React Router。因此,在 React 项目的顶级文件(例如 index.js)中导入 Router 组件,其中 React 使用 ReactDOM API 挂载到 HTML:
import React from 'react';
import ReactDOM from 'react-dom';
import { BrowserRouter } from 'react-router-dom';

import App from './App';

ReactDOM.render(
<BrowserRouter>
<App />
</BrowserRouter>,
document.getElementById('root')
);

从这里开始,我们将在 App.js 文件中继续我们的实现。

匹配路由

首先,我们将使用 React Router 的 Link 组件在我们的 App 组件中实现导航。我不建议使用内联样式,因此请根据你的 React 项目选择合适的样式策略和样式方法:

import { Link } from 'react-router-dom';

const App = () => {
return (
<>
<h1>React Router</h1>
<Navigation />
</>
);
};

const Navigation = () => {
return (
<nav
style={{
borderBottom: 'solid 1px',
paddingBottom: '1rem',
}}
>
<Link to="/home">Home</Link>
<Link to="/users">Users</Link>
</nav>
);
};

当你在浏览器中启动 React 应用程序时,你应该能够单击两个 Link 组件,这些组件应该将你导航到各自的路由。单击这些链接时,可通过检查浏览器的当前 URL 来确认。接下来,我们需要使用 React Router 的 Route 组件将路由映射到实际渲染:

import { Routes, Route, Link } from 'react-router-dom';

const App = () => {
return (
<>
<h1>React Router</h1>

<Navigation />

<Routes>
<Route path="home" element={<Home />} />
<Route path="users" element={<Users />} />
</Routes>
</>
);
};

const Navigation = () => {
return (
<nav
style={{
borderBottom: 'solid 1px',
paddingBottom: '1rem',
}}
>
<Link to="/home">Home</Link>
<Link to="/users">Users</Link>
</nav>
);
};

你可以通过检查它们各自的 to 和 path 属性来查看 Link 和 Route 组件之间的直接匹配。当路由匹配时,每个 Route 组件都会渲染一个 React 元素。由于我们在这里渲染一个 React 元素,我们也可以传递 React props。缺少的是相应功能组件的声明:

const Home = () => {
return (
<main style={{ padding: '1rem 0' }}>
<h2>Home</h2>
</main>
);
};

const Users = () => {
return (
<main style={{ padding: '1rem 0' }}>
<h2>Users</h2>
</main>
);
};

返回浏览器时,你应该能够在看到 Home 和 Users 组件的同时从一个页面导航到另一个页面(此处:从 /home 到 /users 路由)。基本上这就是 React Router 的本质:设置 Link 组件并将它们与 Route 组件匹配。链接与路由是多对一的关系,因此你的应用程序中可以有多个链接链接到同一个路由。

布局路由、索引路由、无匹配路由

接下来,你将看到新的 Home 和 Users 组件如何共享相同的布局。作为 React 开发人员,直觉上我们会从 Home 和 Users 组件中提取一个带有样式的新组件,以避免重复。在这个新组件中,我们将使用 React 的 children 属性将组件组合在一起。第一步,将样式提取到它自己的组件中:

const Home = () => {
return (
<>
<h2>Home</h2>
</>
);
};

const Users = () => {
return (
<>
<h2>Users</h2>
</>
);
};

const Layout = ({ children }) => {
return <main style={{ padding: '1rem 0' }}>{children}</main>;
};

其次,在 App 组件中渲染它。通过使用 React 的子级,Layout 组件应该渲染匹配的封闭子路由:

import { Routes, Route, Link } from 'react-router-dom';

const App = () => {
return (
<>
<h1>React Router</h1>

<Navigation />

<Routes>
<Layout>
<Route path="home" element={<Home />} />
<Route path="users" element={<Users />} />
</Layout>
</Routes>
</>
);
};

const Navigation = () => {
return (
<nav
style={{
borderBottom: 'solid 1px',
paddingBottom: '1rem',
}}
>
<Link to="/home">Home</Link>
<Link to="/users">Users</Link>
</nav>
);
};

const Home = () => {
return (
<>
<h2>Home</h2>
</>
);
};

const Users = () => {
return (
<>
<h2>Users</h2>
</>
);
};

const Layout = ({ children }) => {
return <main style={{ padding: '1rem 0' }}>{children}</main>;
};

但是你会看到这在 React Router 中是不允许的,你会得到一个异常说:<Routes> 的所有组件子项必须是 <Route><React.Fragment>。解决此问题的一种常见方法是在每个组件中单独使用 Layout 组件(类似于我们之前使用的)或在每个 Route 组件中(如下例所示):

const App = () => {
return (
<>
...

<Routes>
<Route path="home" element={<Layout><Home /></Layout>} />
<Route path="users" element={<Layout><Users /></Layout>} />
</Routes>
</>
);
};

然而,这给 React 应用程序增加了不必要的冗余。因此,我们将使用所谓的 Layout Route,而不是复制 Layout 组件,它不是实际的路由,而只是一种方法,可以让一组 Route 中的每个 Route 组件的元素具有相同的周围样式:

const App = () => {
return (
<>
...

<Routes>
<Route element={<Layout />}>
<Route path="home" element={<Home />} />
<Route path="users" element={<Users />} />
</Route>
</Routes>
</>
);
};

如你所见,可以将 Route 组件嵌套在另一个 Route 组件中——而前者成为所谓的嵌套路由。现在不再在 Layout 组件中使用 React 的子组件,而是使用 React Router 的 Outlet 组件作为等效组件:

import { Routes, Route, Outlet, Link } from 'react-router-dom';

...

const Layout = () => {
return (
<main style={{ padding: '1rem 0' }}>
<Outlet />
</main>
);
};

本质上,Layout 组件中的 Outlet 组件插入了父路由(这里:Layout 组件)的匹配子路由(这里:Home 或 Users 组件)。毕竟,使用 Layout Route 可以帮助你为集合中的每个 Route 组件提供相同的布局(例如,CSS 样式,HTML 结构)。

从这里开始,你可以更进一步,将 App 组件的所有实现细节(标题、导航)移动到这个新的 Layout 组件中。此外,我们可以与 NavLink 组件交换链接,以实现所谓的活动链接——向用户显示当前活动的路线。因此,当将新的 NavLink 组件与函数一起使用时,我们可以访问其style和 className props中的 isActive 标志:

import { Routes, Route, Link, NavLink, Outlet } from 'react-router-dom';

const App = () => {
return (
<>
<h1>React Router</h1>

<Navigation />

<Routes>
<Route element={<Layout />}>
<Route path="home" element={<Home />} />
<Route path="users" element={<Users />} />
</Route>
</Routes>
</>
);
};

const Navigation = () => {
return (
<nav
style={{
borderBottom: 'solid 1px',
paddingBottom: '1rem',
}}
>
<Link to="/home">Home</Link>
<Link to="/users">Users</Link>
</nav>
);
};

const Home = () => {
return (
<>
<h2>Home</h2>
</>
);
};

const Users = () => {
return (
<>
<h2>Users</h2>
</>
);
};

const Layout = () => {
const style = ({ isActive }) => ({
fontWeight: isActive ? 'bold' : 'normal',
});

return (
<>
<h1>React Router</h1>

<nav
style={{
borderBottom: 'solid 1px',
paddingBottom: '1rem',
}}
>
<NavLink to="/home" style={style}>Home</NavLink>
<NavLink to="/users" style={style}>Users</NavLink>
</nav>

<main style={{ padding: '1rem 0' }}>
<Outlet />
</main>
</>
);
};

接下来你可能已经注意到这个 React 应用程序缺少一个基本路由。虽然我们有 /home 和 /users 路由,但没有 / 路由。你也会在浏览器的开发人员工具中看到此警告:没有路由匹配位置“/”。因此,每当用户访问 / 路由时,我们都会创建一个所谓的索引路由作为回退。此回退路由的元素可以是新组件或任何已匹配的路由(例如,Home 应为路由 / 和 /home 呈现,如下例所示):

const App = () => {
return (
<Routes>
<Route element={<Layout />}>
<Route index element={<Home />} />
<Route path="home" element={<Home />} />
<Route path="users" element={<Users />} />
</Route>
</Routes>
);
};

当父路由匹配但没有子路由匹配时,你可以将索引路由视为默认路由。接下来,如果用户导航到不匹配的路由(例如 /about),我们将添加一个所谓的 No Match Route(也称为 Not Found Route),它相当于网站的 404 页面:

const App = () => {
return (
<Routes>
<Route element={<Layout />}>
<Route index element={<Home />} />
<Route path="home" element={<Home />} />
<Route path="users" element={<Users />} />
<Route path="*" element={<NoMatch />} />
</Route>
</Routes>
);
};

const NoMatch = () => {
return (<p>There's nothing here: 404!</p>);
};

到目前为止,在使用 Routes 组件作为 Route 组件集合的容器时,通过使用 Layout Routes、Index Routes 和 No Match Routes 展示了 React Router 的其他最佳实践。如你所见,也可以将 Route 组件嵌套到 Route 组件中。下面我们接着了解有关嵌套路由的更多信息。

动态且嵌套的路由

接下来我们将用实现细节来装饰用户组件。首先,我们将在我们的 App 组件中初始化一个项目列表(这里是:用户)。该列表只是示例数据,但它也可以在 React 中从远程 API 获取。其次,我们将用户作为props传递给用户组件:

const App = () => {
const users = [
{ id: '1', fullName: 'Robin Wieruch' },
{ id: '2', fullName: 'Sarah Finnley' },
];

return (
<Routes>
<Route element={<Layout />}>
<Route index element={<Home />} />
<Route path="home" element={<Home />} />
<Route path="users" element={<Users users={users} />} />
<Route path="*" element={<NoMatch />} />
</Route>
</Routes>
);
};

Users 组件成为 React 中的列表组件,因为它遍历每个用户并为其返回 JSX。在这种情况下,它不仅仅是一个列表,因为我们将 React Router 的 Link 组件添加到组合中。 Link 组件中的相对路径提示相应的动态(此处:/${user.id})尚未嵌套(此处:/${user.id} 嵌套在 /users 中)路由:

const Users = ({ users }) => {
return (
<>
<h2>Users</h2>

<ul>
{users.map((user) => (
<li key={user.id}>
<Link to={`/users/${user.id}`}>
{user.fullName}
</Link>
</li>
))}
</ul>
</>
);
};

通过拥有这个新的动态嵌套路由,我们需要在 App 组件中为它创建一个匹配的嵌套路由组件。首先,由于它是 /users 路由的所谓嵌套路由(或子路由),我们可以将它嵌套在相应的父路由组件中。此外,由于它是所谓的动态路由,它使用定义为 :userId 的动态路由,而用户的标识符则动态匹配(例如,id 为 '1' 的用户将与 /users/1 匹配):

const App = () => {
const users = [
{ id: '1', fullName: 'Robin Wieruch' },
{ id: '2', fullName: 'Sarah Finnley' },
];

return (
<Routes>
<Route element={<Layout />}>
<Route index element={<Home />} />
<Route path="home" element={<Home />} />
<Route path="users" element={<Users users={users} />}>
<Route path=":userId" element={<User />} />
</Route>
<Route path="*" element={<NoMatch />} />
</Route>
</Routes>
);
};

之前,当我们介绍将 /home 和 /users 路由作为其子路由的父布局路由时,我们已经了解了嵌套路由。当我们进行此更改时,我们必须使用父路由中的 Outlet 组件来渲染匹配的子路由。同样的情况在这里再次发生,因为用户组件也必须渲染它的嵌套路由:

const Users = ({ users }) => {
return (
<>
<h2>Users</h2>

<ul>...</ul>

<Outlet />
</>
);
};

接下来,我们将声明缺少的 User 组件,只要用户的标识符在 URL 中匹配,该组件就会通过 Users 组件中的 Outlet 嵌套。因此,我们可以使用 React Router 的 useParams Hook 从 URL 中获取相应的 userId(等于 :userId):

import {
...
useParams,
} from 'react-router-dom';

...

const User = () => {
const { userId } = useParams();

return (
<>
<h2>User: {userId}</h2>

<Link to="/users">Back to Users</Link>
</>
);
};

我们再次看到了如何通过将一个 Route 组件(或多个 Route 组件)嵌套在另一个 Route 组件中来创建嵌套路由。前者是嵌套的子路由,后者是渲染封闭组件的父路由,该组件必须使用 Outlet 组件来渲染实际匹配的子路由。

我们还看到了如何通过在路由的路径属性(例如:userId)中使用冒号来创建动态路由。本质上, :userId 充当任何标识符的星号。在我们的例子中,我们使用 Link 组件将用户导航到 /users/:userId 路由,其中​​ :userId 代表实际用户的标识符。最后,我们总是可以通过使用 React Router 的 useParams Hook 从 URL 中获取动态路径(称为参数或 params)。

React Router中的相关链接

最新版本的 React Router 带有所谓的相对链接。我们将通过查看用户组件及其用于链接组件的绝对 /users/${user.id} 路径来研究这个概念。在之前版本的 React Router 中,需要指定整个路径。但是,在此版本中,你可以仅使用嵌套路径作为相对路径:

const Users = ({ users }) => {
return (
<>
<h2>Users</h2>

<ul>
{users.map((user) => (
<li key={user.id}>
<Link to={user.id}>
{user.fullName}
</Link>
</li>
))}
</ul>
</>
);
};

由于 Users 组件用于 /users 路由,因此 Users 组件中的 Link 知道其当前位置,不需要创建绝对路径的整个顶级部分。相反,它知道 /users 并且只是附加 :userId 作为它的相对路径。

声明式和程序式导航

到目前为止,我们只在使用 Link 或 NavLink 组件时使用了声明式导航。但是,在某些情况下,你希望能够通过 JavaScript 以编程方式导航用户。我们将通过实现一个可以在 User 组件中删除用户的功能来展示这个场景。在删除后,用户应该从 User 组件导航到 Users 组件(从 /users/:userId 到 /users)。

我们将通过使用 React 的 useState Hook 创建一个有状态的 users 值来开始这个实现,然后实现一个事件处理程序,该处理程序使用标识符从用户中删除用户:

import * as React from 'react';
...

const App = () => {
const [users, setUsers] = React.useState([
{ id: '1', fullName: 'Robin Wieruch' },
{ id: '2', fullName: 'Sarah Finnley' },
]);

const handleRemoveUser = (userId) => {
setUsers((state) => state.filter((user) => user.id !== userId));
};

return (
<Routes>
<Route element={<Layout />}>
<Route index element={<Home />} />
<Route path="home" element={<Home />} />
<Route path="users" element={<Users users={users} />}>
<Route
path=":userId"
element={<User onRemoveUser={handleRemoveUser} />}
/>
</Route>
<Route path="*" element={<NoMatch />} />
</Route>
</Routes>
);
};

在我们将事件处理程序作为回调处理程序传递给 User 组件后,我们可以在那里使用它作为内联处理程序来通过标识符删除特定用户:

const User = ({ onRemoveUser }) => {
const { userId } = useParams();

return (
<>
<h2>User: {userId}</h2>

<button type="button" onClick={() => onRemoveUser(userId)}>
Remove
</button>

<Link to="/users">Back to Users</Link>
</>
);
};

一旦用户被删除,我们可以使用 React Router 的 useNavigate Hook,它允许我们以编程方式将用户导航到另一个路由(这里:/users):

import * as React from 'react';
import {
...
useNavigate,
} from 'react-router-dom';

const App = () => {
const navigate = useNavigate();

const [users, setUsers] = React.useState([
{ id: '1', fullName: 'Robin Wieruch' },
{ id: '2', fullName: 'Sarah Finnley' },
]);

const handleRemoveUser = (userId) => {
setUsers((state) => state.filter((user) => user.id !== userId));

navigate('/users');
};

return (...);
};

在这种情况下,删除操作是同步发生的,因为用户只是客户端的一个有状态值。但是,如果用户是数据库中的实体,则必须发出异步请求才能删除它。一旦这个操作成功(例如:promise是 resolved时),用户就会被导航到 /users 路由。你可以通过在 React 中设置一个虚假的 API 来自己尝试这个场景,而不使用实际的服务器。

搜索参数

浏览器中的 URL 不仅包含路径,还包含一个可选的查询字符串(在 React Router 中称为搜索参数),它以键/值对的形式出现在 ? URL 中的分隔符。例如,/users?name=robin 将是一个带有一对搜索参数的 URL,其中键是名称,值是 robin。以下示例将其显示为实现:

import * as React from 'react';
import {
...
useSearchParams,
} from 'react-router-dom';

...

const Users = ({ users }) => {
const [searchParams, setSearchParams] = useSearchParams();

const searchTerm = searchParams.get('name') || '';

const handleSearch = (event) => {
const name = event.target.value;

if (name) {
setSearchParams({ name: event.target.value });
} else {
setSearchParams({});
}
};

return (
<>
<h2>Users</h2>

<input
type="text"
value={searchTerm}
onChange={handleSearch}
/>

<ul>
{users
.filter((user) =>
user.fullName
.toLowerCase()
.includes(searchTerm.toLocaleLowerCase())
)
.map((user) => (
<li key={user.id}>
<Link to={user.id}>{user.fullName}</Link>
</li>
))}
</ul>

<Outlet />
</>
);
};

首先,我们使用 React Router 的 useSearchParams Hook 从 URL 中读取当前搜索参数(请参阅 searchParams 上的 get() 方法),同时还将搜索参数写入 URL(请参阅 setSearchParams() 函数)。虽然我们使用前者按键获取搜索参数(此处:“name”)来控制输入字段,但我们使用后者在 URL 中按键设置搜索参数。在输入字段中键入。在其核心,React Router 的 useSearchParams Hook 与 React 的 useState Hook 相同,区别在于该状态是 URL 状态,而不是 React 中的本地状态。最后我们使用搜索参数来过滤用户的实际列表以完成此功能。

毕竟,在你的 URL 中包含搜索参数可以让你与他人共享更具体的 URL。如果你在一个搜索黑色鞋子的电子商务网站上,你可能希望共享整个 URL(例如 myecommerce.com/shoes?color=black)而不仅仅是路径(例如 myecommerce.com/shoes)。

总结

React Router 是 React 最常用的第三方库之一。它的核心功能是将 Link 组件映射到 Route 组件,这使开发人员无需向 Web 服务器发出请求即可实现客户端路由。然而,除了这个核心功能之外,它还是一个成熟的路由库,它支持声明式嵌套路由、动态路由、导航、活动链接,还可以通过 URL 进行编程导航和搜索。

参考

react-router CRA

· 阅读需 13 分钟

前言

之前我们已经研究了树数据结构的实现以及它的一些变体,例如 trie。在这篇文章中,我们将深入研究堆。它也称为优先级队列。

什么是堆?

堆是树数据结构的一种变体,具有两个附加属性: 1.它是一棵完全二叉树:一棵完全二叉树的每一层都包含最大数量的节点,可能最后一层除外,它必须从左到右填充。完整的二叉树总是通过它的定义来平衡的。作为参考下图显示了什么时候可以将树称为完全二叉树: 2.每个节点都满足“堆属性”:堆属性本质上意味着对于任何给定的节点 C,如果 P 是 C 的父节点,则:

  • 对于最大堆:P 的键应该大于或等于 C 的键。
  • 对于最小堆:P 的键应该小于或等于 C 的键。

如何表示堆?

我们通常从节点的类表示开始实现,然后将其与实际数据结构本身的类表示联系起来。我们也可以对堆做同样的事情。但是,有一种更简单的方法可以解决此问题,这是因为所有堆都必须遵守以下两个属性之一:

所有堆必须是完全二叉树 由于所有堆都必须是完全二叉树,并且我们知道完全二叉树中除最后一层外的所有级别都必须完全填充。此外,对于最后一层,所有子项必须从左到右方向填充,没有任何间隙。这个定义确保了一个由 n 个节点组成的完全二叉树只能有 1 种可能的形状。反过来,它允许我们使用数组来表示完整的二叉树。这意味着,堆也可以使用数组来表示。例如,我们可以将一个简单的堆表示为一个数组,如下图所示: 这里要注意的关键是父节点和子节点之间的关系。如果仔细观察上图,我们可以推断出以下内容:

  1. 如果节点位于数组中的索引 i 处,则假设结果索引位于数组的长度内:
  • 它的左孩子将在第 (2i+1) 个位置
  • 左孩子将在 (2i+2) 位置
  1. 如果一个节点被放置在数组中的索引 i 处,它的父节点将位于第 ((i-1)/2) 个索引处。 下图可以更轻松地使用上述信息:

具体实现

注意:在整个实现过程中,我们只会讨论最小堆。稍后我们将看到如何将相同的想法轻松扩展到最大堆。

在我们已经涵盖了表示的细节,让我们想出一个使用数据结构的接口。在堆数据结构的帮助下,我们希望能够实现三个关键点:

  • 向堆中添加一个新键
  • 从堆中删除最大或最小键(取决于它是最小堆还是最大堆)
  • 从堆中获取最小键的最大值(取决于是最小堆还是最大堆)

第三个操作很简单。我们知道对于最小堆,数组中的第一项将是最小键,同样对于最大堆,数组中的第一项将是最大键。所以我们剩下两个操作的实现:

// adds the provided newKey into the min-heap named "heap"
function heappush(heap, newKey){}

// removes the smallest key from the min-heap named "heap"
function heappop(heap){}

实现heappush()

我们如何向堆中添加一个新键?假设我们首先将新键推送到数组中。推送新键仍然让我们遵守堆的第一个要求,即它必须是一个完整的二叉树。但是,我们需要确保它也遵守“堆属性”。 我们可以通过将push的项与其父项进行比较来做到这一点。如果父项大于的push的项,那么我们知道堆属性被违反,因此我们可以交换。我们可以继续进行这种交换,直到找到一个合法的父节点或者我们已经到达堆的顶部。 代码如下

function heappush(heap, newKey){
// push the new key
heap.push(newKey);

// get the current index of pushed key
let curr = heap.length-1;

// keep comparing till root is reached or we terminate in middle
while(curr > 0){
let parent = Math.floor((curr-1)/2)
if( heap[curr] < heap[parent] ){
// quick swap
[ heap[curr], heap[parent] ] = [ heap[parent], heap[curr] ]
// update the index of newKey
curr = parent
} else{
// if no swap, break, since we heap is stable now
break
}
}
}

实现 heappop()

使用 heappop() 我们需要删除堆的最顶层元素。意思是,对于最小堆,最小键将被删除,而对于最大堆,最大键将被删除。从数组的角度来看,它只是意味着我们应该删除数组的第一项。但是哪个节点应该成为根?如果我们随机选择被移除节点的左孩子或右孩子作为新的根节点,则不能保证遵循堆属性。我们可以按照以下步骤(对于最小堆):

  1. 将根节点与最后一个节点交换(数组中的第一个元素与最后一个元素)
  2. 通过从数组中弹出最后一项来删除根节点
  3. 将新根节点的键与其子节点进行比较:
  • 如果键小于它的两个子键,则堆是稳定的
  • 否则,将Key与较小的子Key交换
  1. 重复步骤 3,直到到达最后一个子节点或建立堆属性。

本质上,我们遵循与 heappush() 类似的过程,除了我们试图以从上到下的方式建立堆属性,即从根开始并一直持续到最后一个孩子。在 heappush() 中,我们遵循相反的顺序,即从最后一个孩子开始,一直到根。 代码实现:

function heappop(heap){
// swap root with last node
const n = heap.length;
[heap[0], heap[n-1]] = [ heap[n-1], heap[0]]

// remove the root i.e. the last item (because of swap)
const removedKey = heap.pop();

let curr = 0;

// keep going till atleast left child is possible for current node
while(2*curr + 1 < heap.length){
const leftIndex = 2*curr+1;
const rightIndex = 2*curr+2;
const minChildIndex = (rightIndex < heap.length && heap[rightIndex] < heap[leftIndex] ) ? rightIndex :leftIndex;
if(heap[minChildIndex] < heap[curr]){
// quick swap, if smaller of two children is smaller than the parent (min-heap)
[heap[minChildIndex], heap[curr]] = [heap[curr], heap[minChildIndex]]
curr = minChildIndex
} else {
break
}
}

// finally return the removed key
return removedKey;
}

使用现有数组创建堆

从现有数组创建堆看起来非常简单。只需创建一个空堆,然后遍历数组的所有项并执行 heappush():

function heapify(arr){
const heap = []
for(let item of arr){
heappush(heap, item)
}
return heap;
}

但是我们可以在这里做得更好吗?是的。首先,我们可以完全避免为新堆使用额外的空间。为什么不重新排列数组本身的元素,使其满足堆属性?为此,我们可以遵循与堆弹出类似的逻辑。我们可以查看第一个节点并与它的子节点进行比较,看看它是否是最小的节点,如果不是与较小的子节点交换。下面我们来实现一下:

// follows pretty much the same logic as heappush, except minor modifications
function percolateDown(heap, index){
let curr = index;
// keep going down till heap property is established
while(2*curr + 1 < heap.length){
const leftIndex = 2*curr+1;
const rightIndex = 2*curr+2;
const minChildIndex = (rightIndex < heap.length && heap[rightIndex] < heap[leftIndex] ) ? rightIndex :leftIndex;
if(heap[minChildIndex] < heap[curr]){
// quick swap, if smaller of two children is smaller than the parent (min-heap)
[heap[minChildIndex], heap[curr]] = [heap[curr], heap[minChildIndex]]
curr = minChildIndex
} else {
break
}
}

我们可以对数组中的所有元素使用 percolateDown() 函数,按照堆属性将所有元素按正确顺序排列:

function heapify(heap){
for(let i in heap){
percolateDown(heap, i)
}
return heap
}

这样就为我们节省了一个额外的数组。但是我们能做些什么来改善所花费的时间吗?是的。如果你仔细观察,我们实际上是在做一些重复的工作。假设堆中有 n 个节点,其中 x 是叶节点,那么这意味着我们只需要对 n-x 个节点执行 percolateDown(),因为到那时最后 x 个节点将在正确的位置。

那么在堆的数组表示中,我们应该执行 percolateDown() 操作到哪个索引? 直到最后一个节点的父节点所在的索引。因为一旦最后一个节点的父节点被过滤掉,它也会处理最后一个节点。所以:

  • 如果数组长度为 n
  • 最后一个节点的索引是:n-1
  • 它的父节点的索引是:Math.floor((n-1) - 1 / 2) = Math.floor(n/2 - 1)
function heapify(heap){
const last = Math.floor(heap.length/2 - 1);
for(let i = 0; i <= last; i++){
percolateDown(heap, i)
}
return heap
}

时间和空间复杂度

查看 heappush() 和 heapop() 操作,很明显我们在尝试添加或删除键时正在遍历树的高度。由于堆是一棵平衡树,因此高度是 log(n),其中 n 是节点总数。因此,对于堆的推送和弹出操作,时间复杂度为 O(log(n))。 heapify() 操作的时间复杂度可能看起来像 Onlog(n),因为每次调用都需要 O(log(n))。这个观察结果对于推导 heapify() 的时间复杂度的上限是正确的,但是,渐近(平均)时间复杂度为 O(n)。更多细节在这里。就空间复杂度而言,它是恒定的,因为额外的空间仅被诸如 curr、leftIndex 等大小恒定的变量占用。

最大堆

如果我们有 minHeap 的实现,我们也可以轻松地将它用作最大堆。我们只需要确保在向堆添加值时我们插入键的负数。它将确保堆充当所有键的负数的最小堆,这相当于所有实际键的最大堆。例如:

  • 假设我们有一个数组 const x = [23, 454, 54, 29];
  • 可以使用以下方法创建最小堆:
const heap = [];
for(let el of x) heappush(heap, el);
// min value
const min = heappop(heap)

最大堆可以使用

const heap = [];
for(let el of x) heappush(heap, -el);

// max value const max = -heappop(heap)


· 阅读需 7 分钟

前言

JavaScript 中的数组非常易于使用。但是,你应该注意一个细微差别:某些数组中可能存在漏洞。 在这篇文章中,我将描述 JavaScript 中稀疏数组和密集数组之间的区别。此外,你将找到创建稀疏数组的常用方法。

密集数组

JavaScript 中的数组是一个对象,表示元素的有序集合。数组中的元素有一个确切的顺序。你可以使用索引访问数组的第 n 项。

const names = ['Batman', 'Joker', 'Bane'];
console.log(names[0]); // logs 'Batman'
console.log(names[1]); // logs 'Joker'
console.log(names[2]); // logs 'Bane'
console.log(names.length); // logs 3
  • names[0] 访问索引 0(第一个元素)处的数组项。
  • 数组还有一个属性长度,它表示数组中的项数。在前面的示例中,names.length 为 3,因为数组中的元素个数为 3。
  • 上面创建的名称数组是一个密集数组:这意味着它包含每个索引处的元素,从 0 开始,直到 names.length - 1。 我们定义这是一个函数 isDense(array) ,用于确定数组是否在每个索引处都有元素:
    function isDense(array) {
    for (let index = 0; index < array.length; index++) {
    if (!(index in array)) {
    return false;
    }
    }
    return true;
    }
    const names = ['Batman', 'Joker', 'Bane'];
    console.log(isDense(names)); // logs true
    其中 index in array 确定数组是否在索引位置有一个元素。

这是一个有趣的问题:JavaScript 中的所有数组都是密集的吗?或者当 isDense(array) 返回 false 时可能有数组?

稀疏数组

有些情况下 JavaScript 数组中可能存在漏洞。这样的数组被命名为稀疏数组。 例如,如果你使用数组字面量但省略指示项就会创建了一个稀疏数组:

const names = ['Batman', , 'Bane'];
console.log(names[0]); // logs 'Batman'
console.log(names[1]); // logs undefined
console.log(names[2]); // logs 'Bane'
console.log(isDense(names)); // logs false

['Batman', , 'Bane'] 数组文字创建一个稀疏数组,在 1 索引处有一个缺失。如果你访问这个位置的值——names[1]——它的计算结果是 undefined

要明确检查特定索引处是否有空缺,你可以这样写index in names中:

const names = ['Batman', , 'Bane'];
// No hole
console.log(0 in names); // logs true
// Hole
console.log(1 in names); // logs false

当然,如果你在稀疏数组上运行 isDense() 它将返回 false:

const names = ['Batman', , 'Bane'];
console.log(isDense(names)); // logs false

现在你对稀疏数组有所了解。但是创建稀疏数组的常用方法是什么?

创建稀疏数组的方法

数组字面量

在使用数组字面量时省略一个值会创建一个稀疏数组(注意记录器数组中的空词):

const names = ['Batman', , 'Bane'];
console.log(names); // logs ['Batman', empty, 'Bane']

Array() 构造函数

调用 Array(length)new Array(length)(带有一个数字参数)会创建一个完全稀疏的数组:

const array = Array(3);
console.log(isDense(array)); // logs false
console.log(array); // logs [empty, empty, empty]

删除操作符

在数组上使用 delete array[index] 运算符时:

const names = ['Batman', 'Joker', 'Bane'];
delete names[1];
console.log(isDense(names)); // logs false
console.log(names); // logs ['Batman', empty, 'Bane']

最初,names数组是密集的。 但是执行 delete names[1] 会删除索引 1 处的元素并使 names 数组变得稀疏。

增加length属性

如果你增加数组的长度属性,那么你也会在数组中创建空缺:

const names = ['Batman', 'Joker', 'Bane'];
names.length = 5;
console.log(isDense(names)); // logs false
console.log(names); // logs ['Batman', 'Joker', 'Bane', empty, empty]

最初names数组有3个元素,是一个密集数组。 但是,将names.length 增加到 5 个元素会在 3 和 4 个索引处创建 2 个孔。

附带说明一下,减少 length 属性不会创建稀疏数组,而是从数组末尾删除元素。

数组方法和稀疏数组

稀疏数组的一个问题是许多数组内置方法只是跳过稀疏数组中的空缺。 例如, array.forEach(eachFunc) 不会在孔上调用 eachFunc

const names = ['Batman', , 'Bane'];
names.forEach(name => {
console.log(name);
});
// logs 'Batman'
// logs 'Bane'

以同样的方式 array.map(mapperFunc)array.filter(predicateFunc) 和更多函数跳过这些空缺位置。如果你不小心创建了一个稀疏数组,可能很难理解为什么数组方法不能按预期工作。

总结

在 JavaScript 中,数组可以是密集的或稀疏的。

如果每个索引处都有从 0 开始直到 array.length - 1 的元素,则数组是密集的。否则,如果任何索引处至少缺少一项,则数组是稀疏的。

虽然你不会过多地处理稀疏数组,但你应该了解可以创建一个数组的情况:

  • 跳过数组 [1, , 3] 中的值时
  • 使用 Array(length)
  • 使用delete array[index]
  • 当增加 array.length 属性时

稀疏数组的问题在于某些 JavaScript 函数(如 array.forEach()array.map() 等)在迭代数组项时会跳过空缺值。

拓展

稀疏数组在访问元素的速度上比密集数组慢

const arr = new Array(200000)
arr[19999] = 88
console.time('using[]')
arr[19999]
console.timeEnd('using[]')
// using[]: 0.031982421875ms

const ddd = [...new Array(200000)]
ddd[19999] = 88
console.time('using[]')
ddd[19999]
console.timeEnd('using[]')
// using[]: 0.010009765625ms

具体原因是,对于稀疏数组 V8 引擎访问对象是使用 散列表模式的,该种模式在访问时需要计算一遍哈希值,所以会比较慢,但散列表对于空间利用来说,效率更高。而密集数组,它是申请一段连续的内存空间,访问时可以直接通过「索引」来访问,所以速度比较快。

· 阅读需 8 分钟

前言

我们已经在三篇文章中介绍了树数据结构的基础知识。如果你还没有读过这些,我强烈建议先阅读前三篇文章:

介绍

Trie 是树数据结构的一种变体。它也被称为前缀树或搜索树的变体。就像 n 叉树数据结构一样,trie 可以有 n 个来自单亲的孩子。通常,trie 中的所有节点都会存储一些字符。假设我们只处理英语单词,下面是一个简单的 trie 可能看起来像: 需要注意的事项:

  1. 我们正在尝试使用树来尽可能高效地表示英语单词。

  2. 在上图中,从根节点到任何绿色节点的路径表示一个英文单词。例如:

    • NULL->C->A->T: CAT
    • NULL->D->O: DO
    • NULL->D->O->G: DOG
    • NULL->D->A->R->K: DARK
    • NULL->A: A
    • NULL->A->N: AN
  3. 每个节点最多可以有 26 个子节点(如果我们只处理英文字母)。我们有一个 NULL 节点作为根节点,因为一个单词可以以 26 个字母中的任何一个开头,因此我们需要一个虚拟节点,它可以将任何潜在的第一个字母作为子节点。

  4. 绿色节点,本质上代表“词尾”,同时从根遍历到该节点。

实现节点

现在,让我们尝试提出 Trie 节点的表示。回到树节点,这就是我们呈现它的方式:

function Node(value){
this.value = value
this.left = null
this.right = null
}

因此,我们可以对 Trie 遵循类似的想法,同时确保它满足我们在介绍部分讨论的要求。要了解 Trie 节点的要求,让我们放大任何节点: 所以现在更有意义了。这是最终的代码:

function Node(value){
this.value = value
this.isEndOfWord = false // false by default, a green node means this flag is true
this.children = {} // children are stored as Map, where key is the letter and value is a TrieNode for that letter
}

实现 Trie 数据结构

我们可以使用一个简单的 ES6 类来表示:

class Trie{
constructor(){
this.root = new Node(null)
}

insert(word){
// TODO
}

search(word){
// TODO
}

}

所以我们已经准备好了大概。作为初始化的一部分,每个trie 都会创建它自己的根节点(NULL)。那么我们可以实现这两个方法如下:

  • insert(word):我们可以将单词拆分为字母,并为每个字母创建一个 Node()。然后我们可以开始将这些 Trie 节点中的每一个链接到根节点,以插入单词。最后,我们将最后插入的节点的 isEndOfWord 属性标记为 true。
  • search(word):我们可以将单词拆分为字母。然后我们可以从根开始一个一个地寻找这些字母中的每一个。如果我们能够按顺序找到所有字母,那么我们可以返回 true 否则 false。

让我们直观地理解这两个操作以获得更好的上下文:

  • 首先insert(CAR)然后insert(CAN):
  • 首先search(CAR)然后search(CAN):

实现如下:

class Trie{
constructor(){
this.root = new Node(null)
}

insert(word){
let current = this.root
// iterate through all the characters of word
for(let character of word){
// if node doesn't have the current character as child, insert it
if(current.children[character] === undefined){
current.children[character] = new Node(character)
}
// move down, to insert next character
current = current.children[character]
}
// mark the last inserted character as end of the word
current.isEndOfWord = true
}

search(word){
let current = this.root
// iterate through all the characters of word
for(let character of word){
if(current.children[character] === undefined){
// could not find this character in sequence, return false
return false
}
// move down, to match next character
current = current.children[character]
}
// found all characters, return true if last character is end of a word
return current.isEndOfWord
}
}

使用 Trie

const trie = new Trie();

// insert few words
trie.insert("CAT");
trie.insert("DOG");

// search something
trie.search("MAT") // false
trie.search("DOG") // true

空间复杂度

在最坏的情况下,所有插入单词的每个字符都可以占用 Trie 中的单个节点。所以这意味着最坏的空间复杂度可以是 (W*n),其中 W 是每个单词的平均字符数,n 是 Trie 中的单词总数。

时间复杂度

  • 插入:插入一个有n个字符的单词,只需要遍历n个字符,所以时间复杂度为O(n)
  • 搜索:与插入类似,我们只需要遍历单词的所有字符即可进行搜索。所以时间复杂度是 O(n),其中 n 是单词中的字符数。

现在,想一想,你还能如何在庞大的单词列表中搜索某个单词? -可能使用数组?时间复杂度为 O(m),其中 m 是单词总数,这很糟糕。

  • 如何使用Map(或 JavaScript 中的对象)?这会将时间复杂度降低到 O(1),但是找到具有特定前缀的单词列表有多快?它将是 O(m)。

Trie 不仅将时间复杂度降低到 O(n)(n = 单词中的字符数),而且您还可以有效地搜索具有前缀的单词列表,这对于任何以上两种方法。

应用

  • 自动完成和预先输入:如果您在文本框中键入内容,并且看到具有相同前缀的潜在搜索列表,即自动完成小部件,那么这可能是由后台的 Trie 处理的。同样,Typeahead 也可以使用 Trie 来实现。
  • 拼写检查器:我们可以使用 trie 创建拼写检查器,即给定一个单词列表,我们可以检查给定单词的拼写是否正确。
  • IP 路由(最长前缀匹配):Internet 由多个路由器节点组成,它们决定应该发送的目标数据包。 Internet 上的每个路由器都需要将数据包发送到由给定 IP 目的地决定的适当目标节点。但是每个路由器如何使用给定的 IP 地址决定下一个目标路由器呢?这个问题可以使用IP路由来解决。这是一篇深入探讨这个主题的好文章

· 阅读需 7 分钟

前言

到目前为止,我们已经了解了一些二叉树遍历的方法:

  • 使用递归和迭代算法遍历二叉树
  • 使用父指针遍历二叉树 在本文中,我们将把这些知识用于 n 叉树,即 DOM。我们将看到如何使用各种 CSS 选择器定位 DOM 元素,而无需使用内置 API,如 getElementById、getElementsByClassname 或 querySelector/querySelectorAll。因此,本文将阐明这些 API 可能如何在幕后工作。

DOM 遍历

借用 使用递归和迭代算法遍历二叉树的思路,我们来得出DOM的前序遍历算法:

function walkPreOrder(node){
if(!node) return

// do something here
console.log(node)

for(let child of node.children){
walkPreOrder(child)
}
}

我们可以修改这个算法使之来返回一个迭代器:

function* walkPreOrder(node){
if(!node) return

// do something here
yield node
for(let child of node.children){
yield* walkPreOrder(child)
}
}

// USAGE
for(let node of walkPreOrder(root)){
console.log(node)
}

我们可以使用任何广度优先或深度优先算法(在之前的文章中讨论过)来遍历 DOM。 我们还假设正在处理具有以下 HTML 的文档:

<html>
<head>
<title>DOM selection algorithm</title>
</head>
<body>

<div class="container">
<div class="body">
<div class="row">
<img id="profile" src="xyz.jpg" alt="">
</div>
<div class="row"></div>
<div class="row"></div>
</div>
</div>

</body>
</html>

通过 ID 定位节点

function locateById(nodeId){
// iterate through all nodes in depth first (preOrder) fashion
// return the node as soon as it's found
for(let node of walkPreOrder(document.body)){
if(node.id === nodeId){
return node
}
}
return null
}

我们可以使用 locateById() 函数如下:

const img = locateById('profile')
// returns the image node

通过ClassName 定位节点

浏览器提供 document.getElementsByClassName() API 来实现此结果。我们如何实现类似的东西:

function locateAllByClassName(className){
const result = []
for(let node of walkPreOrder(document.body)){
if(node.classList.contains(className)){
result.push(node)
}
}
return result
}

// USAGE
const elements = locateAllByClassName('row')

浏览器如何优化选择查询

选择 DOM 节点是 Web 应用程序相当常见的操作。为同一个选择器多次遍历树似乎不是最佳选择。浏览器通过使用记忆优化选择。 查看 mozilla 解析器的源代码,即函数 startTag 的摘录:

 // ID uniqueness
@IdType String id = attributes.getId();
if (id != null) {
LocatorImpl oldLoc = idLocations.get(id);
if (oldLoc != null) {
err("Duplicate ID \u201C" + id + "\u201D.");
errorHandler.warning(new SAXParseException(
"The first occurrence of ID \u201C" + id
+ "\u201D was here.", oldLoc));
} else {
idLocations.put(id, new LocatorImpl(tokenizer));
}
}

我们可以看到这些节点 ID 保存在一个简单的哈希映射中。我们可以使用类似的方法来确保对同一 ID 的重复查询不需要完全遍历,相反,我们可以从 hashMap 中查找并返回它。 以下是我们的解决方案:

function getSelectors(){
const idLocations = {}
const classLocations = {}

// updated selector functions
function locateById(nodeId){
if(idLocations.hasOwnProperty(nodeId))
return idLocations[nodeId]

for(let node of walkPreOrder(document.body)){
if(node.id === nodeId){
idLocations[nodeId]= node //memoize
return node
}
}
idLocations[nodeId]= null // memoize
return null
}

function locateAllByClassName(className){
if(classLocations.hasOwnProperty(className))
return classLocations[className]

const result = []
for(let node of walkPreOrder(document.body)){
if(node.classList.contains(className)){
result.push(node)
}
}
classLocations[nodeId]= result
return result
}

return {
locateById,
locateAllByClassName
}

}

// USAGE
const {locateById, locateAllByClassName} = getSelectors();
const result = locateAllByClassName('row') // returns array of elements
const img = locateById('profile') // returns an element, if found

处理更复杂的选择器

让我们尝试实现类似 element.querySelector 的方法。以下是 MDN 的描述:

The querySelector() method of the Element interface returns the first element that is a descendant of the element on which it is invoked that matches the specified group of selectors.

样例

const firstRow = document.querySelector('.container .row:first-child')

在这种情况下,我们可以将任何 CSS 选择器传递给函数,它应该能够遍历 DOM 为我们找到该元素。让我们看看它是如何实现的:

// given a selector and root node, find that selector within the root node
function select(selector, root){
for(let node of walkPreOrder(root)){
if(node.matches(selector)){
return node
}
}
return null;
}

function myQuerySelector(path, node){ // if path is empty, nothing to find if(path.length === 0) return null;

// if node is not provided, let's assume user wants to search within document.body let root = node || document.body;
const selector = path[0];

// if there's only one selector in the path, just traverse using select function above if(path.length === 1) return select(selector, root);

// else, either the current node matches the first selector in path or not // if first selector matches with current node, look through it's children for subsequent selectors only // else, look through it's children for the whole path const newPath = root.matches(selector) ? path.slice(1): path; for(let child of root.children){ const ans = myQuerySelector(newPath, child); if(ans) return ans }

// nothing found return null; }

// USAGE: const firstRow = myQuerySelector([".container", ".row"])

myQuerySelectorAll 的实现(类似于 element.querySelectorAll)也遵循相同的方法,稍作修改:
```javascript
function selectAll(selector, root){
let result = []
for(let node of walkPreOrder(root)){
if(node.matches(selector)){
result.push(node)
}
}
return result;
}

function myQuerySelectorAll(path, node){
let result = [];
if(path.length === 0) return result;

let root = node || document.body;
const selector = path[0];

if(path.length === 1) return selectAll(selector, root);

const newPath = root.matches(selector) ? path.slice(1): path;
for(let child of root.children){
result = [...result, ...myQuerySelectorAll(newPath, child)]

}

return result;
}

进阶

我们可以使用本文开头描述的递归前序遍历方法来克隆任何树。让我们看看我们如何使用它来克隆任何 DOM 树,类似于 element.cloneNode(true) 所做的:

  • 通过创建具有相同 tagName 的新节点然后复制属性来创建源节点的克隆。
  • 对源节点的所有子节点递归调用 cloneTree 方法,并将返回的节点作为子节点附加到克隆节点。
function cloneTree(node){
if(!node) return

const clonedNode = document.createElement(node.tagName.toLowerCase())
const attributes = node.getAttributeNames()

attributes.forEach(attribute => {
clonedNode.setAttribute(attribute, node.getAttribute(attribute))
})

for(const child of node.children){
clonedNode.append(cloneTree(child))
}

return clonedNode
}

· 阅读需 9 分钟

前言

在本系列的第一部分中,我们研究了遍历二叉树的递归和迭代方法。 在实际应用中,树节点有一个父节点是很常见的:一个指向父节点的指针,因此也称为父指针。让我们以浏览器中的 DOM 为例。假设我们使用以下命令选择任何节点:

const element = document.querySelector("#id")

在本文中,我们将研究如何使用这些父指针来提高遍历效率。我稍后会解释我所说的“更高效”是什么意思。在下一篇文章中,我们还将了解如何使用此处学到的经验教训从头开始创建 myQuery 库。

更新节点定义

首先,我们需要更新Node 函数

function Node(value){
this.value = value
this.left = null
this.right = null
this.parent = null // added parent field
}

现在让我们看看如何使用这个新的 Node 定义来创建一个类似的树,就像我们在上一篇文章中所做的那样。

const root = new Node(2)
const left = new Node(1)
root.left = left
left.parent = root

const right = new Node(3)
root.right = right
right.parent = root

我们只需要确保父指针指向父节点。这是我们使用上述代码获得的最终树的视觉参考:

##寻找后继节点

前序后继

假设每个节点都有一个parent指针,如何找出二叉树中任何节点的 前序 后继? 让我们试着分析一下这个问题:

  1. 首先,我们在这里处理前序,这意味着我们正在寻找以下顺序:
root -> left -> right
  1. 这意味着如果我们已经在当前节点,我们想寻找左子节点作为后继节点。
  2. 如果根本没有左子节点怎么办?那么在这种情况下,我们会寻找合适的节点,如果在有左子节点,那就是后继节点。
  3. 如果没有左子节点或右子节点,那么我们需要回溯(继续向上走向父节点)。我们一直回溯,直到通过它的右子节点到达父级(因为这意味着 前序 对于父级下的整个子树是完整的,根据 #1 的定义)。

最终算法实现就是这样:

function preOrderSuccessor(node){
if(!node) return

if(node.left) return node.left
if(node.right) return node.right

let parent = node.parent

while(parent && parent.right === node) {
node = node.parent
parent = parent.parent
}

if(!parent) return null // we backtracked till root, so no successor

return parent.right
}

可以根据下图更好的理解

中序后继

  1. 首先,我们在这里处理中序遍历,这意味着我们正在寻找以下顺序:
root -> left -> right
  1. 如果我们在当前节点,并且它右边有右子节点,那么我们可以通过在右子树上找到最左边的节点来获得后继节点。
  2. 如果没有右子节点,那么我们需要回溯(向上移动)。我们一直向上移动,直到通过它的右子节点到达父节点,因为这意味着已经遍历了整个子树(根据 #1 中的定义)。
  3. 一旦我们找到最近的父节点,它是通过它的左子节点找到的,它就会作为后继节点返回。为什么?因为这意味着它是一个已经探索了左树的节点,所以根据 #1 中的定义,节点本身现在是后继节点。 实现如下:
function inOrderSuccessor(node){
if(!node) return

if(node.right){
let current = node.right
while(current && current.left) current = current.left
return current
}

let parent = node.parent

while(parent && parent.right === node) {
root = node.parent
parent = parent.parent
}

if(!parent) return null

return parent
}

后序后继

  1. 首先,我们在这里处理后序遍历,这意味着我们正在寻找以下顺序:
left -> right -> root
  1. 所以,如果我们在任何节点上,就意味着它的左右子树已经被访问过了。这意味着我们需要查看父级的继任者。
  2. 如果我们从它的右子节点到达父母,这意味着父母本身就是继任者,根据#1 中的定义
  3. 如果我们从它的左子节点到达父母,这意味着接下来要探索父母的右子节点(根据#1 中的定义)。所以现在我们需要简单地返回父节点右子节点中最左边的节点作为后继节点。 实现如下:
function postOrderSuccessor(node){
if(!node) return

let parent = node.parent
if(!parent) return null

if(parent.right === node). return parent

let current = parent.right
while(current && (current.left || current.right)){
current = (current.left || current.right)
}

return current
}

使用后继算法更好地遍历

为什么我们需要使用父指针来提出遍历算法呢?这是一个值得思考的问题,因为我们已经提出了遍历树的递归和迭代方法,而且不需要父指针。

我们这样做的原因是因为我们之前的方法增加了空间复杂性。如果你还记得上一篇文章中我们需要使用一个或两个堆栈(取决于遍历方法)来使任何遍历算法工作。即使在递归方法中,虽然我们不直接使用堆栈,但递归本身基于调用堆栈,因此那里也使用了隐藏的内存中堆栈。问题是这个堆栈的大小会随着我们树的深度而增加,因此这不是最好的解决方案,因为我们有办法在花费更少空间的情况下完成相同的任务。通过使用父指针,我们可以完全摆脱这些堆栈,为我们节省大量空间,即从 O(logN) 的空间复杂度(其中 N 表示平衡树的大小)到 O(1)。让我们看看如何实现。

前序遍历

对于 前序遍历,我们从树的根部开始。之后,我们可以使用上面的算法继续获取前序后继以遍历整棵树:

function preOrder(root){
// first node
console.log(root.value);

let current = root
while(true){
const next = preOrderSuccessor(current)
if(!next) break

// do something
console.log(next.value)

current = next
}
}

中序遍历

对于 中序遍历,起始节点将是树的最左侧节点。此后,我们可以使用上述算法继续获取后继以遍历整棵树:

function inOrder(root){
// start at the left most node
while(root && root.left){
root = root.left
}

// first node
console.log(root.value);

let current = node
while(true){
const next = inOrderSuccessor(current)
if(!next) break

// do something
console.log(current.value)

current = next
}
}

后序遍历

非常类似于上面的中序遍历的方法:

function postOrder(root){
// start at the left most node
while(root && root.left){
root = root.left
}

// first node
console.log(root.value);

let current = node
while(true){
const next = postOrderSuccessor(current)
if(!next) break

// do something
console.log(current.value)

current = next
}
}

进阶

如果每个节点都有一个父指针,你能想出算法来寻找前任(inOrder、preOrder 和 postOrder)吗?

· 阅读需 9 分钟

前言

Tree是一种有趣的数据结构。它在各个领域都有广泛的应用。例如:

  • DOM 是一种Tree状数据结构
  • 我们操作系统中的目录和文件可以表示为Tree
  • 家庭层次结构可以表示为Tree。 Tree的许多变体(如堆、BST 等)可用于解决与调度、图像处理、数据库等相关的问题。许多复杂的问题乍一看似乎与Tree无关,但可以被表示为一个Tree的问题。我们也会(在本系列的后面部分)解决这些问题,从而了解Tree如何使看似复杂的问题更容易理解和解决。

简介

二叉树实现节点非常简单

function Node(value){
this.value = value
this.left = null
this.right = null
}
// usage
const root = new Node(2)
root.left = new Node(1)
root.right = new Node(3)

所以这几行代码将为我们创建一个二叉树,如下所示:

           2  
/ \
/ \
1 3
/ \ / \
null null null null

遍历

让我们从尝试遍历这些连接的树节点(或一棵树)开始。正如我们可以遍历数组一样,如果我们也可以“遍历”树节点。然而,树不是像数组那样的线性数据结构,所以遍历这些的方法不止一种。我们可以将遍历方法大致分为以下几类:

  • 广度优先遍历
  • 深度优先遍历

广度优先遍历(BFS)

在这种方法中,我们逐层遍历树。我们将从根开始,然后覆盖它的所有子级,然后覆盖所有 2 级子级,依此类推。例如对于上面的树,遍历会导致这样的结果:

           2  
/ \
/ \
1 3
/ \ / \
null null null null
2,1,3

下面是一个稍微复杂的树的插图,使这更容易理解:

为了实现这种形式的遍历,我们可以使用队列(先进先出)数据结构。以下是整个算法的过程:

  1. 初始化一个包含 root 的队列
  2. 从队列中删除第一项
  3. 将弹出项的左右节点推入队列
  4. 重复步骤 2 和 3,直到队列为空 下面是这个算法在实现后的样子:
function walkBFS(root){
if(root === null) return

const queue = [root]
while(queue.length){
const item = queue.shift()
// do something
console.log(item)

if(item.left) queue.push(item.left)
if(item.right) queue.push(item.right)
}
}

我们可以稍微修改上面的算法实现为:

function walkBFS(root){
if(root === null) return

const queue = [root], ans = []

while(queue.length){
const len = queue.length, level = []
for(let i = 0; i < len; i++){
const item = queue.shift()
level.push(item)
if(item.left) queue.push(item.left)
if(item.right) queue.push(item.right)
}
ans.push(level)
}
return ans
}

深度优先遍历(DFS)

在 DFS 中,我们取一个节点并继续探索它的子节点,直到深度耗尽为止。它可以通过以下方式之一完成:

 root node -> left node -> right node // pre-order traversal
left node -> root node -> right node // in-order traversal
left node -> right node -> root node // post-order traversal

所有这些遍历技术都可以递归和迭代实现。让我们进入实现细节:

前序遍历(Pre-Order traversal)

分析
 root node -> left node -> right node

技巧:

我们可以使用这个简单的技巧来手动找出任何树的前序遍历:从根节点开始遍历整棵树,保持自己在左边。

实现
  • 递归
function walkPreOrder(root){
if(root === null) return

// do something here
console.log(root.val)

// recurse through child nodes
if(root.left) walkPreOrder(root.left)
if(root.right) walkPreOrder(root.right)
}

  • 迭代 前序遍历的迭代方法与 BFS 非常相似,不同之处在于我们使用堆栈而不是队列,并且我们首先将右节点推入堆栈:
function walkPreOrder(root){
if(root === null) return

const stack = [root]
while(stack.length){
const item = stack.pop()

// do something
console.log(item)

// Left child is pushed after right one, since we want to print left child first hence it must be above right child in the stack
if(item.right) stack.push(item.right)
if(item.left) stack.push(item.left)
}
}

中序遍历(In-Order traversal)

分析

下面是一棵树的中序遍历的过程:

left node -> root node -> right node

技巧

我们可以使用这个简单的技巧来手动找出任何树的中序遍历:在树的底部水平放置一个平面镜,并获取所有节点的投影

实现
  • 递归

    function walkInOrder(root){
    if(root === null) return

    if(root.left) walkInOrder(root.left)

    // do something here
    console.log(root.val)

    if(root.right) walkInOrder(root.right)
    }
  • 迭代 这个算法乍一看可能有点神秘。但它相当直观。让我们这样看:在中序遍历中,最左边的孩子节点首先被打印,然后是根,然后是孩子节点。所以首先想到的是想出这样的东西:

    const curr = root

while(curr){ while(curr.left){ curr = curr.left // get to leftmost child }

console.log(curr) // print it

curr = curr.right // now move to right child }

在上述方法中,我们无法回溯,即返回导致最左侧节点的父节点。所以我们需要一个堆栈来记录这些。因此,我们修订后的方法可能如下所示:
```javascript
const stack = []
const curr = root

while(stack.length || curr){
while(curr){
stack.push(curr) // keep recording the trail, to backtrack
curr = curr.left // get to leftmost child
}
const leftMost = stack.pop()
console.log(leftMost) // print it

curr = leftMost.right // now move to right child
}

现在我们可以使用上面的方法来制定最终的迭代算法:

function walkInOrder(root){
if(root === null) return

const stack = []
let current = root

while(stack.length || current){
while(current){
stack.push(current)
current = current.left
}
const last = stack.pop()

// do something
console.log(last)

current = last.right
}
}

后序遍历(Post-Order traversal)

分析

下面是一棵树的中序遍历的过程:

 left node -> right node -> root node

技巧

对于任何树的快速手动后序遍历:一个接一个地提取所有最左边的孩子节点。

实现

让我们深入研究这种遍历的实际实现。

  • 递归

      function walkPostOrder(root){
    if(root === null) return

    if(root.left) walkPostOrder(root.left)
    if(root.right) walkPostOrder(root.right)

    // do something here
    console.log(root.val)

    }
  • 迭代 我们已经有了用于前序遍历的迭代算法。我们可以用那个吗?因为后序遍历似乎只是前序遍历的反向。让我们来看看:

// PreOrder:
root -> left -> right

// Reverse of PreOrder:
right -> left -> root

// But PostOrder is:
left -> right -> root

从上面分析可见有细微的差别。我们可以通过稍微修改我们的 前序遍历算法然后反转它应该给出 后序遍历结果来适应这一点。总体算法将是:

// record result using 
root -> right -> left

// reverse result
left -> right -> root
  • 使用与上述迭代前序遍历算法类似的方法,使用临时堆栈。
    • 唯一的区别是 root -> right -> left 而不是 root -> left -> right
  • 结果将遍历序列记录在一个array
  • 结果的反转就是后序遍历
function walkPostOrder(root){
if(root === null) return []

const tempStack = [root], result = []

while(tempStack.length){
const last = tempStack.pop()

result.push(last)

if(last.left) tempStack.push(last.left)
if(last.right) tempStack.push(last.right)
}

return result.reverse()
}