js实现二叉查找树的建立、插入、删除、遍历操作

╰半夏微凉° 2022-05-14 04:39 238阅读 0赞

## 1 概念 ##

二叉排序树（二叉查找树），它或者是一颗空树，或者是具有以下性质的二叉树：

*  任意一个结点左子树上的所有结点值均小于该结点值
 *  任意一个结点右子树上的所有结点值均大于该结点值

例如下图：  
![这里写图片描述][1184971-20180429232041394-466861398.png]

## 2 插入和建立二叉排序树 ##

**结点的数据结构**

function newNode(value){
        this.value = value;
        this.left = null;
        this.right = null;
    }

**插入操作**  
插入操作很简单，即用递归依次比较插入值与结点值的大小，找到插入的位置

function InsertNode(root, key){
        if (!root.value){   //如果根结点不存在，则建立根结点
            root.value = key;
            return true; 
        }
    
        if (root.value > key){  //当前结点值比插入值大，说明插入位置在当前结点值的左子树中
            if (root.left){  //如果有左孩子结点，继续比较
                InsertNode(root.left, key);
            }else{   //插入操作
                root.left = new newNode(key);
            }
        }else if (root.value < key){ //当前结点值比插入值小，说明插入位置在当前结点值的右子树中
            if (root.right){ //如果有右孩子结点，继续比较
                InsertNode(root.right, key);
            }else{  //插入操作
                root.right = new newNode(key);
            }
        }else{  //树中已存在插入值的结点
            return false;
        }
    
        return true;
    }

**建立操作**  
二叉排序树的建立就是多次执行插入操作

function create(array){ 
        var tree = new newNode(null);  //建立根节点
        for (let i=0; i < array.length; i++){
            InsertNode(tree, array[i]);
        }
        return tree;
    }

## 3 遍历 ##

二叉排序树中序遍历的输出结果就是结点值从小到大排序的结果

function InOrderTraverse(root){ 
        if (!root) return;
        InOrderTraverse(root.left);
        console.log(root.value);
        InOrderTraverse(root.right);
    }

## 4 删除操作 ##

删除操作稍微复杂一些。思路在于首先找到删除值的结点，若该结点是叶子结点，则直接将其置为`null`，若其具有左子树或右子树，则将左孩子结点或右孩子结点赋值给当前结点。若当前结点既有左子树，又有右子树，则在其左子树中，寻找一个和当前结点值最接近的孩子结点（即中序遍历结果中当前结点的前驱），将当前结点的值替换为该孩子结点的值，替换后，树中此时就有两个重复的值，因此，再利用递归删除重复的孩子结点，依次类推。。。

function deleteNode(root, key){
        if (!root){
            console.log("删除失败");
            return root;
        }
    
        if (root.value > key){  //若当前结点值大于删除值，则继续在左子树中寻找删除值
            root.left = deleteNode(root.left, key);
        }else if (root.value < key){  //若当前结点值小于删除值，则继续在右子树中寻找删除值
            root.right = deleteNode(root.right, key);
        }else{  //找到与删除中相等的结点
            if (root.left === null & root.right === null){  //叶子结点
                root = null;
            }else if (root.left === null){  //只有右子树
                root = root.right;
            }else if (root.right === null){  //只有左子树
                root = root.left;
            }else{  //同时具有左右子树
                let prevNode = root.left;
                while(prevNode.right){  //寻找不大于当前结点值的最大结点值
                    prevNode = prevNode.right;
                }
                root.value = prevNode.value;  //替换值
                root.left = deleteNode(root.left, prevNode.value);  //递归左子树，删除重复值的结点
            }
        } 
        return root;
    }

[1184971-20180429232041394-466861398.png]: /images/20220514/1156dd4281294ba29e5f7a6c300d33e2.png

发表评论取消回复

表情：

评论列表（有 0 条评论，238人围观）

还没有评论，来说两句吧...

相关阅读

相关二叉树的建立与遍历

1.1 给定一棵二叉树的先序遍历序列和中序遍历序列，建立这棵二叉树，并得出层序遍历序列和后序遍历序列。【分析】找出根结点，分别划分出左子树和右子树的先序、中序遍历序列，进

末蓝、/ 2023年01月19日 13:59/ 0 赞/ 153 阅读

相关二叉树建立与遍历递归操作c++实现

\include <iostream> \include <cstdio> \include <string> using namespace std;

爱被打了一巴掌/ 2022年09月19日 04:13/ 0 赞/ 133 阅读

相关二叉树遍历、插入、删除等常见操作

本文总结了二叉树常见的题目。如下是头文件的部分声明： //tree.h ifndef TEST_TREE_H define TEST_TR

落日映苍穹つ/ 2022年08月05日 19:27/ 0 赞/ 153 阅读

相关二叉搜索树的插入、删除与遍历

二叉搜索树的插入二叉搜索树是有序的，插入之后要使插入后的树还是有序的，就必须比较每个节点的值，然后再选择合适的位置插入，首先先将树的节点设计如下： typed

柔光的暖阳◎/ 2022年06月17日 01:10/ 0 赞/ 164 阅读

相关二叉树的遍历操作

include<iostream> include<queue> include<stack> using namespace std; //定义二叉树的节点数据类型

一时失言乱红尘/ 2022年06月14日 23:09/ 0 赞/ 186 阅读

相关二叉树的建立，删除，查找，插入，输出（数据结构）

1. 建立二叉树 void pre_crt(tree &bt)//按先序顺序输入二叉树中节点的值，生成 { char c

秒速五厘米/ 2022年06月09日 07:10/ 0 赞/ 180 阅读

相关二叉树的建立和遍历

一、基本概念 ![BinaryTree.png][] 二叉树：每个结点的子结点个数不大于2的树，叫做二叉树。根结点：最顶部的那个结点叫做根结点，根结点是所有子结点

r囧r小猫/ 2022年05月26日 04:40/ 0 赞/ 176 阅读

相关 js实现二叉查找树的建立、插入、删除、遍历操作

1 概念二叉排序树（二叉查找树），它或者是一颗空树，或者是具有以下性质的二叉树：任意一个结点左子树上的所有结点值均小于该结点值任意一个结点右子树上的所

╰半夏微凉°/ 2022年05月14日 04:39/ 0 赞/ 239 阅读

相关二叉查找树（BST）及二叉树的遍历

二叉查找树（BST）及二叉树的遍历一、二叉查找树（BST） 1、二叉查找树的特征二叉查找树（BST）也称为二叉搜索树或二叉排序树。二叉查找树的节点包含键值

雨点打透心脏的1/2处/ 2021年11月05日 04:02/ 0 赞/ 379 阅读

相关二叉树的建立与遍历

二叉树的建立与遍历 1.所谓树的遍历，就是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。 2.广度优先遍历（层序遍历）从最高层（或最底层）开始，向下（

忘是亡心i/ 2021年09月26日 07:36/ 0 赞/ 349 阅读