当前位置：网站首页>树和二叉树的转换

树和二叉树的转换

2022-08-01 12:50:00 【51CTO】

树和二叉树是两种不同的数据结构，树实现起来比较麻烦，但是树可以转换为二叉树进行处理，处理完以后再从二叉树还原为树。

下面说说转换的方法：

1. 树转换为二叉树

(1) 树中所有相同双亲结点的兄弟结点之间加一条连线。

(2) 对树中不是双亲结点第一个孩子的结点，只保留新添加的该结点与左兄弟结点之间的连线，删去该结点与双亲结点之间的连线。

(3) 整理所有保留的和添加的连线，使每个结点的第一个孩子结点连线位于左孩子指针位置，使每个结点的右兄弟结点连线位于右孩子指针位置。

如下是树转换为二叉树的过程示例图：

树和二叉树的转换_结点

2.二叉树还原为树

(1) 若某结点是其双亲结点的左孩子，则把该结点的右孩子、右孩子的右孩子……都与该结点的双亲结点用线连起来。

(2) 删除原二叉树中所有双亲结点与右孩子结点的连线。

(3) 整理所有保留的和添加的连线，使每个结点的所有孩子结点位于相同层次高度。

如下是二叉树还原为树的过程示意图：

树和二叉树的转换_结点_02

（由于我自己太懒了，图没有自己画，以上图片来自百度图片搜索）

版权声明
本文为[51CTO]所创，转载请带上原文链接，感谢
https://blog.51cto.com/u_15737520/5532506