你的浏览器还没开启 Javascript 功能!

算法题(二)二元查找树转双向链表

前言

听着音乐,看着桌面角落躺着两张图,定睛一看忘记是从哪里捡来的数据结构与算法题目了,正好可以动动脑再写一下。

1.png

2.png

我会分几个文章一题一题的分析思路。

第二题之前已经写过一点文字了,请看 查找最小数栈

这篇文章呢,开始探讨第一题。

题目

二元查找树转变为排序的双向链表:
输入一颗二元查找树,将二元查找树转换成一个排序的双向链表。

要求:需要自己定义二元查找树的结构和双向链表的结构。不能创建任何新的节点,只调整指针指向。

举例:

3.png

转换成双向链表:

4.png

分析

  • 二元查找树
  • 双向链表
  • 转换,不能创建新的节点,只调整指针指向。

ok,大概此题的核心就是考验 自己定义 二元查找树双向链表,实现这两个数据结构,然后 不创建新的节点 完成转换。

二元查找树

故名思意,是一颗二叉树,但是它满足一个条件,比节点小的在左边子节点,反之数值比节点大的放在右子节点,仔细看图,可以看出来。

双向链表

一般链表是单向的,A -> B -> C,双向链表则就是 A <-> B <-> C,比单向链表多处一个可访问上一个节点的指针。

如何转换

由图可见,最后转成 4 <-> 6 <-> 8 …..<-> 16,的链表,是升序的,所以二元查找树得用中序遍历,其遍历过程当中,再对节点做链表双向赋值即可。

实现

分析了个大概,可以尝试来用编码实现两个数据结构了。

二元查找树

节点

class TreeNode {
    // 数值
    public value: number;
    // 左节点
    public left: TreeNode = null;
    // 右节点
    public right: TreeNode = null;
    constructor(n: number) {
        this.value = n;
    }
}
树形

class Tree {
    // 头部
    public head: TreeNode = null;

    /**
     * 快速插入数值
     * @param n 数值
     */
    public insertValue(n: number) {
        this.insert(new TreeNode(n));
    }
    /**
     * 插入节点
     * @param treeNode 待插入的新节点
     */
    public insert(treeNode: TreeNode) {
        if(this.head === null) { // 如果当前头部节点为空
            // 则新节点直接作为头部节点
            this.head = treeNode;
        }else { 
            // 开始做比较插入
            this.insertInto(this.head, treeNode);
        }
    }
    /**
     * 比较节点进行插入
     * @param currentNode 当前待比较节点
     * @param insertNode 新插入节点
     */
    private insertInto(currentNode: TreeNode, insertNode: TreeNode) {
        // 如果新节点的值比当前节点小
        if(insertNode.value < currentNode.value) {
            if(currentNode.left !== null) {
                // 但是左子节点已经有了 继续比较
                this.insertInto(currentNode.left, insertNode);
            }else {
                // 赋值归位
                currentNode.left = insertNode;
            }
        }else {
            if(currentNode.right !== null) {
                // 但是右子节点已经有了 继续比较
                this.insertInto(currentNode.right, insertNode);
            }else {
                // 赋值归位
                currentNode.right = insertNode;
            }
        }
    }
}

OK,我们再来测试一下


const arr = [10, 6, 14, 4, 8, 12, 16];
const tree = new Tree();
arr.forEach(n => {
    tree.insertValue(n);
});
console.log(tree);

看看实现的是不是题中的二叉树

3.png

5.png

中序遍历

可能看console.log不是太直观,索性我们先把中序遍历实现,有所不同的是,我决定不在Tree类里面实现中序遍历,而是使用一个外部类来处理。


class Traverse{
    private tree: Tree;
    constructor(tree: Tree) {
        this.tree = tree;
    }
    // 前序遍历
    // 后序遍历
    /**
     * 中序遍历
     * @param callback 回调函数
     */
    inOrder(callback: (n: number) => void) {
        this.forEachTree(this.tree.head, [null, callback, null]);
    }
    /**
     * 遍历处理
     * @param currentNode 处理节点
     * @param callbackArr [前序回调函数,中序回调函数,后序回调函数]
     */
    private forEachTree(currentNode: TreeNode, callbackArr: Array<(n: number) => void>) {
        if(currentNode === null) {
            return;
        }
        // 前序
        if(callbackArr[0]) {
            callbackArr[0](currentNode.value);
        }
        // 继续处理左子节点
        this.forEachTree(currentNode.left, callbackArr);
        // 中序
        if(callbackArr[1]){
            callbackArr[1](currentNode.value);
        }
        // 继续处理右子节点
        this.forEachTree(currentNode.right, callbackArr);
        if(callbackArr[2]) {
            callbackArr[2](currentNode.value);
        }
    }
}

哈哈,顺便也拓展了一下,支持前中后序遍历,暂时只实现中序的代码。

看看效果:


const arr = [10, 6, 14, 4, 8, 12, 16];
const tree = new Tree();
arr.forEach(n => {
    tree.insertValue(n);
});
new Traverse(tree).inOrder(n => {
    console.log(n); 
});

3.png

6.png

可以的,中序遍历处理已经完成。

双向链表

链表节点

这个节点跟上面树节点结构类似,但是属性名会更有链表的意味


class LinkNode{
    // 数值
    public value: number;
    // 前指向
    public prev: LinkNode = null;
    // 后指向
    public next: LinkNode = null;
    constructor(n: number) {
        this.value = n;
    }
}

解题

其实看到这,基本的两个数据结构已经完成,可以尝试解题了


// 解题
// 链表头部节点
let headNode: LinkNode = null;
// 用于保存遍历时 上一次处理的链表节点
let prevNode: LinkNode = null;
new Traverse(tree).inOrder(n => {
    const linkNode = new LinkNode(n);
    if(prevNode === null) {
        // 记录头部节点
        headNode = linkNode;
    }else{
        // 前后链接
        prevNode.next = linkNode;
        linkNode.prev = prevNode;
    }
    // 更新
    prevNode = linkNode;
});
// 结果
let currentNode = headNode;
// 遍历链表
while(currentNode !== null) {
    console.log(currentNode);
    currentNode = currentNode.next;
}

4.png

7.png