数据结构与算法-树与二叉树的相互转换【十一】

悠悠 2023-02-20 13:38 31阅读 0赞

一个普通的树可以转换成一个唯一的二叉树，原则就是：左孩子 右兄弟。

一个节点的左子树的根节点，是这个节点的孩子节点的第一个，这个节点的右子树的根节点，是这个左子树的根节点的兄弟节点。

### 普通的树转化为二叉树 ###

二叉树的节点定义：

// 二叉树的节点定义
    function TreeNode(val, left, right) { 
      this.val = (val===undefined ? 0 : val)
      this.left = (left===undefined ? null : left)
      this.right = (right===undefined ? null : right)
    }

转换方法：

// 将普通的树转换为二叉树 原则就是 左孩子 右兄弟
    const encodeTree = (root) => { 
     if (root.length === 0) { 
       return null
     }
    
     var help = (root) => { 
        let rootNode = new TreeNode(root.val)
        let root = rootNode;
        let children = root.children || []
        if (children.length > 0) { 
          rootNode.left = new TreeNode(children[0].val)
          // rootNode.right = help
          for (let i = 1; i < children.length; i++) { 
            // 为什么没有想到指针迁移
            rootNode.right = help(children[i])
            rootNode = rootNode.right
          }
        }
        return rootNode
        
     }
     return help(root)
    }

--------------------

### 二叉树转化为普通的树 ###

// 普通树的节点定义
    function TreeNode(val, children) { 
      this.val = (val === undefined ? 0 : val)
      this.children = (children == undefined ? [] : children)
    }

转换方法：

// 将二叉树还原为一颗普通的树
    var decodeTree = (root) => { 
       // 二叉树 左孩子 右兄弟 【反推】
       if (!root) return null
       let rootNode = new TreeNode(root.val);
       let cur = root.left // 如果没有左孩子，那么以前的树没有子节点
       while (cur) { 
         rootNode.children.push(decodeTree(cur))
         cur = cur.right
       }
       return rootNode;
    }

参考资料：  
[王卓老师-数据结构课程-5.6 请给老师的视频教程三连击][-_-5.6]  
[https://www.cnblogs.com/grandyang/p/9945345.html][https_www.cnblogs.com_grandyang_p_9945345.html]

[-_-5.6]: https://www.bilibili.com/video/av35340372
[https_www.cnblogs.com_grandyang_p_9945345.html]: https://www.cnblogs.com/grandyang/p/9945345.html