Javascript实现二叉树算法

浅浅的花香味﹌ 2023-06-06 12:07 7阅读 0赞

**目录**

二叉树算法原理及代码实现

二叉树定义

中序遍历

前序遍历

后序遍历

二叉树节点查找

二叉树叶子节点的删除原理及实现

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

## 二叉树算法原理及代码实现 ##

### 二叉树定义 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvXzkyMTExMA_size_16_color_FFFFFF_t_70][]

8：二叉树的根节点

4、7、13：二叉树的叶子节点

其他：中间节点

**排序二叉树：**

特点：节点的左子节点小于当前节点，节点的右子节点大于当前节点

代码实现：

### 中序遍历 ###

原理：判断当前节点是否有左子节点，有的话，先遍历整个的左子树，再输出当前节点，最后遍历整个右子树

代码实现：

注意打断点可以看到执行过程

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvXzkyMTExMA_size_16_color_FFFFFF_t_70 1][]

执行结果：

![20191118114911861.png][]

### 前序遍历 ###

原理：先打印当前节点，然后找到当前节点的左子树，然后再打印当前节点的左子树，然后找到左子树的左子树，最后打印右子树(可以复制当前的二叉树，效率更高)

代码实现：

### 后序遍历 ###

原理：判断当前节点是否有左子节点，有的话，先遍历整个的左子树，再遍历整个右子树，最后输出当前节点（用于操作系统和文件系统中）

代码实现：

### 二叉树节点查找 ###

二叉树的节点查找分为三种：

1.  查找二叉树节点的最小值
2.  查找二叉树节点的最大值
3.  给定一个值，判断二叉树节点中是否存在

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvXzkyMTExMA_size_16_color_FFFFFF_t_70][]

**查找二叉树节点的最小值**

先判断当前节点是否有左孩子，然后进入节点3，判断现在的节点3是否有左孩子，然后有进入节点1，判断节点1是否有左孩子，没有，所有二叉树节点的最小值是节点1

**查找二叉树节点的最大值**

先判断当前节点是否有右孩子，然后进入节点10，判断现在的节点10是否有右孩子，然后有进入节点14，判断节点14是否有右孩子，没有，所有二叉树节点的最大值是节点14

**给定一个值，判断二叉树节点中是否存在**

假如给定的值是7，然后先判断与当前节点8的大小，比当前节点小就进入当前节点的左子树，进入节点3，判断节点3大小，然后进入节点3的右子树，进入节点6，判断节点6大小，然后进入节点6的右子树

<!DOCTYPE html>
    <html>
      <head>
        <title>binaryTree</title>
      </head>
      <body>
        <script type="text/javascript">
          function BinaryTree() {
            var Node = function(key) {
              this.key = key;
              this.left = null;
              this.right = null;
            }
    
            var root = null;
            
            var insertNode = function (node, newNode) {
              if(newNode.key < node.key) {
                if(node.left === null) {
                  node.left = newNode;
                } else {
                  insertNode(node.left,newNode);
                }
              } else {
                if(node.right === null) {
                  node.right = newNode;
                } else {
                  insertNode(node.right, newNode)
                }
              }
            }
    
            this.insert = function (key) {
              var NewNode = new Node(key)
              if(root === null) {
                root = NewNode
              } else {
                insertNode(root, NewNode);
              }
            };
    
            var searchNode = function (node,key) {
              if (node === null) {
                return false
              }
              if( key < node.key) {
                return searchNode(node.left, key)
              } else if(key > node.key) {
                return searchNode(node.right, key)
              } else {
                return true
              }
            }
    
            this.search = function (key) {
              return searchNode(root, key)
            }
          }
    
          var nodes = [8,3,10,1,6,14,4,7,13];
          var binaryTree = new BinaryTree();
          nodes.forEach(function(key){
            binaryTree.insert(key);
          })
    
          var callback = function (key) {
            console.log(key);
          }
          console.log(binaryTree.search(7) ? 'key 7 is found' : 'key 7 is not found');
          console.log(binaryTree.search(9) ? 'key 9 is found' : 'key 9 is not found');
        </script>
      </body>
    </html>

### 二叉树叶子节点的删除原理及实现 ###

二叉树节点的删除也是可以分为几种情况:

*  被删除节点为叶子节点；
 *  被删除节点仅有一个子节点（子树）；
 *  被删除节点有两个子节点（子树）

被删除节点为叶子节点

思路：将该叶子节点的父节点指向的子节点的引用值设为空

**被删除节点仅有一个子树**

思路：将该节点的父节点指向该节点的引用改成指向该节点的子节点。

**被删除节点有两个子树**

思路：处理这种情况有两种方法：

*  从待删除节点的左子树找节点值最大的节点A，替换待删除节点，并删除节点A；
 *  从待删除节点的右子树找节点值最小的节点A，替换待删除节点，并删除节点A。

**PS：我们这里选择第二种方法。**  
以下图的二叉树为例，删除节点3。

<!DOCTYPE html>
    <html>
      <head>
        <title>binaryTree</title>
      </head>
      <body>
        <script type="text/javascript">
          function BinaryTree() {
            var Node = function(key) {
              this.key = key;
              this.left = null;
              this.right = null;
            }
    
            var root = null;
            
            var insertNode = function (node, newNode) {
              if(newNode.key < node.key) {
                if(node.left === null) {
                  node.left = newNode;
                } else {
                  insertNode(node.left,newNode);
                }
              } else {
                if(node.right === null) {
                  node.right = newNode;
                } else {
                  insertNode(node.right, newNode)
                }
              }
            }
    
            this.insert = function (key) {
              var NewNode = new Node(key)
              if(root === null) {
                root = NewNode
              } else {
                insertNode(root, NewNode);
              }
            };
            var findMinNode = function(node) {
              if(node) {
                while (node && node.left !== null) {
                  node = node.left;
                }
                return node
              }
            }
            var removeNode = function (node,key) {
              if (node === null) {
                return false
              }
              if( key < node.key) {
                node.left = removeNode(node.left, key)
                return node
              } else if(key > node.key) {
                node.right = removeNode(node.right, key)
                return node
              } else {
                // 没有子节点（子树）
                if(node.left === null && node.right === null) {
                  node = null;
                  return node
                }
                // 只有右子节点（子树）
                if(node.left === null) {
                  node = node.right;
                  return node;
                // 只有左子节点（子树）
                } else if (node.right === null) {
                  node = node.left;
                  return node;
                }
                // 有两个子节点（子树）
                var aux = findMinNode(node.right);
                node.key = aux.key;
                node.right = removeNode(node.right, aux.key);
                return node;
              }
            }
    
            this.remove = function (key) {
              return removeNode(root, key)
            }
          }
    
          var nodes = [8,3,10,1,6,14,4,7,13];
          var binaryTree = new BinaryTree();
          nodes.forEach(function(key){
            binaryTree.insert(key);
          })
    
          var callback = function (key) {
            console.log(key);
          }
          binaryTree.remove(3)
        </script>
      </body>
    </html>

gitHub地址：[排序二叉树的代码实现][Link 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvXzkyMTExMA_size_16_color_FFFFFF_t_70]: /images/20230601/a55d4e8659b143e49faaf02f4e7e13e6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvXzkyMTExMA_size_16_color_FFFFFF_t_70 1]: /images/20230601/1cf08350709c4b28a7c147a24284b962.png
[20191118114911861.png]: /images/20230601/54bc3023beae432aaaecf1662a56e061.png
[Link 1]: https://github.com/HZhen/binaryTtree