文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

我们一起聊聊序列化二叉树

2024-12-13 15:52

关注

那么如何实现二叉树与字符串之间的相互转换呢?本文就跟大家分享下这个问题的解决方案,欢迎各位感兴趣的开发者阅读本文。

实现思路

在文章重建二叉树中,我们学会了利用前序遍历序列和中序遍历序列将一个字符串构建成一颗二叉树。这个思路有两个缺点:

其实,当我们用前序遍历来读取二叉树时,得到的序列是从根节点开始的,那么反序列化时在根节点读取出来之后就可以开始了。当我们在序列化的时候可能会遇到空节点,我们用一个特殊的字符来标记它(例如"$")。节点值之间的连接也需要用特殊字符标记(例如",")。

序列化的规则捋清楚后,我们举个例子来验证下是否可行,如下所示(一颗二叉树):

根据上面定义的规则,我们使用前序遍历得到的序列为:1,2,4,$,$,$,3,5,$,$,6,$,$。

经过验证,上述方法成功的实现了树的序列化。接下来我们以字符串1,2,4,$,$,$,3,5,$,$,6,$,$为例分析如何反序列化二叉树。

第一个读出的数字是1。由于前序遍历是从根节点开始的,这是根节点的值。紧接着读出的数字是2,根据前序遍历的规则,这是根节点的左子节点的值。同样的,接下来的数字4是值为2的节点的左子节点。

接着从序列化字符串里读出两个字符"$",这表明节点4的左、右子节点均为空,因此它是一个叶节点。

接下来返回至节点2,重建它的右子节点。继续读取字符,下一个字符是"$",这表明节点2的右子节点为空。这个节点的左、右子树都已经构建完毕。

接下来返回至根节点,反序列化根节点的右子树。

下一个序列化字符串中读取出来的数字是3,因此根节点的右子树的值为3。它的左子节点是一个值为5的叶节点,因为接下来的三个字符是"5,$,$"。

同样,它的右子节点是值为6的叶节点,因为最后3个字符是"6,$,$"。

字符串中的所有字符已读取完毕,序列化流程结束,树也完成重建,如下图所示(去掉了分析思路时所画的辅助线)

实现代码

经过前面的分析,我们已经得到了完整的思路,接下来我们来看下代码的实现。

序列化二叉树

我们利用前序遍历即可完成二叉树的序列化。

  public serialize(root: BinaryTreeNode | null): string {
// 空节点用$表示
if (root == null) return "$";
const result: serializeNode = { nodeVal: "" };
this.serializeFn(root, result);
// 末尾会有多余的分隔符,将其去除
return result.nodeVal.substring(0, result.nodeVal.length - 1);
}



private serializeFn(
root: BinaryTreeNode | null | undefined,
strObj: serializeNode
) {
if (root == null) {
strObj.nodeVal += "$,";
return;
}
strObj.nodeVal += root.key + ",";
this.serializeFn(root.left, strObj);
this.serializeFn(root.right, strObj);
}

反序列化

我们序列化的时候用的前序遍历,同样的在反序列化的时候也要使用前序遍历。反序列的时候稍微麻烦些,需要先把字符串中的每个字符放到数组中。随后再按照我们前面的分析:

  
public deserialize(treeStr: string): BinaryTreeNode | null {
if (treeStr === "$") {
return null;
}
return this.deserializeFn(treeStr);
}


private deserializeFn(nodeStrVal: string) {
// 读取字符串的每一个字符,将其转换为数组
const strArr: Array<string> = [];
let readIndex = 0;
while (readIndex < nodeStrVal.length) {
if (nodeStrVal.charAt(readIndex) !== ",") {
strArr.push(nodeStrVal.charAt(readIndex));
}
readIndex++;
}
// 反序列化二叉树
return this.buildTree(strArr, 0);
}


private buildTree(str: Array<string>, index: number) {
this.across++;
// 处理空节点(递归的基线条件)
if (str[index] === "$") return null;
// 构造树节点
const treeNode: BinaryTreeNode = { key: parseInt(str[index]) };
// 当前节点的下一个节点一定为它的左子树
treeNode.left = this.buildTree(str, index + 1);
// 左子树遇到基线条件后,右子树的索引就为已走步长
treeNode.right = this.buildTree(str, this.across);
return treeNode;
}

测试用例

我们用文章开头所列举的例子来验证下上述代码能否正确的解决问题。

const rootNode: BinaryTreeNode = {
key: 1,
left: {
key: 2,
left: {
key: 4
}
},
right: {
key: 3,
left: {
key: 5
},
right: {
key: 6
}
}
};

const serializedBinaryTree = new SerializedBinaryTree();
const treeStr = serializedBinaryTree.serialize(rootNode);
console.log("序列化后的字符串", treeStr);
const result = serializedBinaryTree.deserialize(treeStr);
console.log("反序列化后的树", result);

执行结果如下所示。

示例代码

本文用到的代码完整版请移步:

来源:神奇的程序员内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯