由目录搜索想到的多叉树向二叉树的转换

发表于 | 更新于: | | 阅读次数:
字数统计: 1.8k字 | 阅读时长 ≈ 7分钟

目录搜索

在上个星期一轮迭代之后， 自己手上暂时还没有工作要做，在上一期迭代中， 需求表示目录太长了，用户不好操作，虽然这个问题通过添加滚动条解决了，但是我想着加一个搜索框实现对于目录的搜索， 效果如下： 如上面所示我们想要进行一个对于目录的搜索，其中目录部分的结构如下：
1
2
3
4
5
6
7
8
9
{
    children: [
        children: [...],
      	title: ...,
        ...
    ],
    title: ...,
    ...
}
这里 title 表示目录的名字， children 表示当前目录下的子目录，如果当前目录没有子目录， 那么 children 属性就不会存在。html 部分：
1
<el-input v-model="searchContent"></el-input>
vue 部分
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
export default {
  data () {
      searchContent: "",
      originMenus: ""
  },
  watch： {
    "route": function () {
  		// 这里用来保存原始数组
  		this.originMenus = Util.clone(this.menus);
	},
    "searchContent": function (val) {
        if (val.trim().length === 0) {
        	this.menus = this.originMenus;
        } else {
            this.filterMenus(val, this.orginMenus);
        }
    },
    methods: {
      filterMenus(val, menus) {
        const filterVal = val;
        // 深拷贝对象
        const filterMenus = Util.clone(menus);
        const filterFn = theMenus => {
          if (theMenus.children) {
            let spliceIndex = 0;
            // 当我们想要对于一个数组进行条件判断并且删除数组中的元素的时候， 可以使用 Array.splice 进行操作
            while (spliceIndex < theMenus.children.length) {
              if (Array.isArray(theMenus.children[spliceIndex].children) &&theMenus.children[spliceIndex].children.length !== 0) {
                // 这里使用递归， 因为对于children 下的各个目录， 判断条件也是基本上一样的
                filterFn(theMenus.children[spliceIndex]);
                // 如果当前目录下存在符合条件的， spliceIndex ++ 使用 continue 跳过当前的 while 循环
                if (theMenus.children[spliceIndex].children.length !== 0) {
                  spliceIndex++;
                  continue;
                }
              }
              // 这一部分， 如何实现有选择性的删除的？
              // 使用 splice 用于数组的删除，如果满足某一个条件， splice 跳过条件删除
              if (theMenus.children[spliceIndex] && theMenus.children[spliceIndex].title && theMenus.children[spliceIndex].title.indexOf(val) > -1) {
                spliceIndex++;
              } else {
                theMenus.children.splice(spliceIndex, 1);
              }
            }
          }
        };
        filterFn(filterMenus);
        return filterMenus;
      }
    }
  }
}
在上面的代码中， 使用到了 while 循环以及一些递归的东西。

由多叉树向二叉树的转换

在上面的目录搜索中，其实自己想要将目录搜索转化为二叉树进行搜索的， 只不过后面发现没有必要，但是自己也是做了一个多叉树转化二叉树的函数。

二叉树

二叉树是这样的一种树：
二叉树是 n ( n >=0 ) 个结点的有限集合， 该集合或者为空集( 空二叉树 ), 或者有一个根节点和两棵互不相交的， 分别称为根节点和左子树和右子树的二叉树组成。

二叉树的特点

每一个节点最多有两棵子树， 二叉树中每一个节点都是一个对象， 对于一个完整的二叉树而言， 每一个二叉树节点存在三个指针， 分别指向父母， 左孩子以及右孩子的指针， 每一个节点都是通过指针相互连接的， 连接指针的关系都是父子关系。二叉树节点的代码定义：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
node {
  value: "",
  // 左孩子
  left: {
    left : {
      ...
    },
    right ： {
      ...
    }
  },
  // 右孩子
  right: {
    ...
  }
}

二叉树的遍历

对于二叉树而言， 存在三种遍历方式：
  1. 前序遍历： 首先访问根节点， 然后遍历左子树， 最后遍历右子树。
  2. 中序遍历：首先遍历左子树， 然后访问根节点，最后遍历右子树。
  3. 后序遍历：首先遍历左子树， 然后遍历右子树， 最后访问根节点。
下面是三种遍历的示意图：前序遍历：​ 代码实现：
1
2
3
4
5
6
7
function preOrder (node) {
    if (node !== null) {
      getNode(node);
      preOrder(node.left);
      preOrder(node.right);
    }
}
中序遍历：代码实现：
1
2
3
4
5
6
7
8
9
10
function inOrder (node) {
  if (node !== null) {
    // 先访问左子树
    inOrder(node.left);
    // 访问根节点
    getNode(node);
    // 访问右子树
    inOrder(node.right);
  }
}
后序遍历：代码实现：
1
2
3
4
5
6
7
8
9
function postOrder (node) {
  if (node !== null) {
    // 先访问左节点
    postOrder(node.left);
    // 再访问右节点
    postOrder(node.right);
    getNode(node);
  }
}

使用二叉树的目的

上面说了这么多， 那么我们为什么构建二叉树呢？二叉树相对于其它的数据结构而言具有什么优点呢？
对于数组而言， 实现数组的搜索比较方便， 可以直接使用下标访问到， 但是如果对于数组进行删除和插入就比较麻烦了， 而对于链表而言， 插入和删除比较简单， 但是访问却相对来说慢了一些。
对于有序数组而言， 对于有序数组在查找的时候有较高的效率。而无序链表在插入的时候具有较高的灵敏性。而对于二叉树而言， 二叉树综合了上面两种数据结构的优点。

二叉查找树

二叉查找数用来寻找到一组数组中的值的大小是非常有用的，因为二叉查找树在定义的时候定义到节点的左节点的值要小于右节点的值。如下使用数组建立一个二叉查找树：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
// 构建左节点
function setLeftNode(array, node) {
  const len = array.length;
  if (len % 2 !== 0) {
    if (array[(len - 1) / 2]) {
      node.left = {
        value: array[(len - 1) / 2]
      };
    }
    return;
  }
  if (array[len / 2]) {
    node.left = {
      value: array[len / 2]
    };
  }
}
// 构建右节点
function setRightNode(array, node) {
  const len = array.length;
  if (len % 2 !== 0) {
    if (array[(len - 1) / 2]) {
      node.right = {
        value: array[(len - 1) / 2]
      };
    }
    return;
  }
  if (array[len / 2]) {
    node.right = {
      value: array[len / 2]
    };
  }
}
// 将数组转化为二叉树
function arrayToTree(array, node) {
  const len = array.length;
  array.sort();
  node.value = (len % 2) !== 0 ? array[(len - 1) / 2] : array[len / 2];
  const leftArr = array.slice(0, (len % 2) !== 0 ? (len - 1) / 2 : len / 2);
  const rightArr = array.slice(((len) % 2) !== 0 ? (len + 1) / 2 : ((len / 2) + 1), array.length);
  setLeftNode(leftArr, node);
  setRightNode(rightArr, node);
  (leftArr.length !== 0) && arrayToTree(leftArr, node.left);
  (rightArr.length !== 0) && arrayToTree(rightArr, node.right);
  return node;
}
1
2
3
const arr = [1, 9, 2, 6, 3, 4, 7, 8];
let tree = {};
console.log(arrayToTree(arr, tree));
最终结果如下：

多叉树

如果一个节点下面有多个节点， 那么可以称这样的数据结构为多叉树,这里可以类比二叉树中的两个子节点：例如上面中的目录部分就是一个多叉树，根目录下面有多个子目录， 子目录下面还有可能有别的目录，如果将这样的多叉树转换为二叉树呢？只要记住一个转换原则就可以了：
多叉树向二叉树转换的原则是： 左孩子，右兄弟。也就是说，一颗转换完成的二叉树的任意一个节点的左节点都是在转换之前的多叉树中的子节点， 任意一个节点的右节点都是当前节点在转换之前的多叉树中的兄弟节点。
转化示意图如下：转化代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const treeRight = (tree, fatherChild) => {
  if (fatherChild && fatherChild.length !== 0) {
    fatherChild.splice(0, 1);
    tree.right = fatherChild[0];
    treeLeft(tree.right, fatherChild);
    treeRight(tree.right, fatherChild);
  }
};
const treeLeft = (tree) => {
  if (tree && tree.children) {
    tree.left = tree.children[0];
    treeLeft(tree.left);
    treeRight(tree.left, tree.children);
  }
};