Javascript实现二叉树算法

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

目录

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

二叉树定义

中序遍历

前序遍历

后序遍历

二叉树节点查找

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

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

二叉树定义

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvXzkyMTExMA_size_16_color_FFFFFF_t_70

8：二叉树的根节点

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

其他：中间节点

排序二叉树：

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

代码实现：

  1. <!DOCTYPE html>
  2. <html>
  3.   <head>
  4.     <title>binaryTree</title>
  5.   </head>
  6.   <body>
  7.     <script type="text/javascript">
  8.       function BinaryTree() {
  9.         var Node = function(key) {
  10.           this.key = key;
  11.           this.left = null;
  12.           this.right = null;
  13.         }
  15.         var root = null;
  17.         var insertNode = function (node, newNode) {
  18.           if(newNode.key < node.key) {
  19.             if(node.left === null) {
  20.               node.left = newNode;
  21.             } else {
  22.               insertNode(node.left,newNode);
  23.             }
  24.           } else {
  25.             if(node.right === null) {
  26.               node.right = newNode;
  27.             } else {
  28.               insertNode(node.right, newNode)
  29.             }
  30.           }
  31.         }
  33.         this.insert = function (key) {
  34.           var NewNode = new Node(key)
  35.           if(root === null) {
  36.             root = NewNode
  37.           } else {
  38.             insertNode(root, NewNode);
  39.           }
  40.         }
  41.       }
  43.       var nodes = [8,3,10,1,6,14,4,7,13];
  44.       var binaryTree = new BinaryTree();
  45.       nodes.forEach(function(key){
  46.         binaryTree.insert(key)
  47.       })
  48.     </script>
  49.   </body>
  50. </html>

中序遍历

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

代码实现：

  1. <!DOCTYPE html>
  2. <html>
  3.   <head>
  4.     <title>binaryTree</title>
  5.   </head>
  6.   <body>
  7.     <script type="text/javascript">
  8.       function BinaryTree() {
  9.         var Node = function(key) {
  10.           this.key = key;
  11.           this.left = null;
  12.           this.right = null;
  13.         }
  15.         var root = null;
  17.         var insertNode = function (node, newNode) {
  18.           if(newNode.key < node.key) {
  19.             if(node.left === null) {
  20.               node.left = newNode;
  21.             } else {
  22.               insertNode(node.left,newNode);
  23.             }
  24.           } else {
  25.             if(node.right === null) {
  26.               node.right = newNode;
  27.             } else {
  28.               insertNode(node.right, newNode)
  29.             }
  30.           }
  31.         }
  33.         this.insert = function (key) {
  34.           var NewNode = new Node(key)
  35.           if(root === null) {
  36.             root = NewNode
  37.           } else {
  38.             insertNode(root, NewNode);
  39.           }
  40.         };
  42.         var inOrderTraverseNode = function (node,callback) {
  43.           if(node !== null) {
  44.             inOrderTraverseNode(node.left,callback);
  45.             callback(node.key);
  46.             inOrderTraverseNode(node.right,callback)
  47.           }
  48.         }
  50.         this.inOrderTraverse = function(callback) {
  51.           inOrderTraverseNode(root,callback);
  52.         }
  53.       }
  55.       var nodes = [8,3,10,1,6,14,4,7,13];
  56.       var binaryTree = new BinaryTree();
  57.       nodes.forEach(function(key){
  58.         binaryTree.insert(key);
  59.       })
  61.       var callback = function (key) {
  62.         console.log(key);
  63.       }
  65.       binaryTree.inOrderTraverse(callback);
  66.     </script>
  67.   </body>
  68. </html>

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

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvXzkyMTExMA_size_16_color_FFFFFF_t_70 1

执行结果：

20191118114911861.png

前序遍历

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

代码实现：

  1. <!DOCTYPE html>
  2. <html>
  3.   <head>
  4.     <title>binaryTree</title>
  5.   </head>
  6.   <body>
  7.     <script type="text/javascript">
  8.       function BinaryTree() {
  9.         var Node = function(key) {
  10.           this.key = key;
  11.           this.left = null;
  12.           this.right = null;
  13.         }
  15.         var root = null;
  17.         var insertNode = function (node, newNode) {
  18.           if(newNode.key < node.key) {
  19.             if(node.left === null) {
  20.               node.left = newNode;
  21.             } else {
  22.               insertNode(node.left,newNode);
  23.             }
  24.           } else {
  25.             if(node.right === null) {
  26.               node.right = newNode;
  27.             } else {
  28.               insertNode(node.right, newNode)
  29.             }
  30.           }
  31.         }
  33.         this.insert = function (key) {
  34.           var NewNode = new Node(key)
  35.           if(root === null) {
  36.             root = NewNode
  37.           } else {
  38.             insertNode(root, NewNode);
  39.           }
  40.         };
  42.         var preOrderTraverseNode = function (node,callback) {
  43.           if(node !== null) {
  44.             callback(node.key);
  45.             preOrderTraverseNode(node.left,callback);
  46.             preOrderTraverseNode(node.right,callback)
  47.           }
  48.         }
  50.         this.preOrderTraverse = function (callback) {
  51.           preOrderTraverseNode(root, callback)
  52.         }
  53.       }
  55.       var nodes = [8,3,10,1,6,14,4,7,13];
  56.       var binaryTree = new BinaryTree();
  57.       nodes.forEach(function(key){
  58.         binaryTree.insert(key);
  59.       })
  61.       var callback = function (key) {
  62.         console.log(key);
  63.       }
  65.       binaryTree.preOrderTraverse(callback);
  66.     </script>
  67.   </body>
  68. </html>

后序遍历

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

代码实现：

  1. <!DOCTYPE html>
  2. <html>
  3.   <head>
  4.     <title>binaryTree</title>
  5.   </head>
  6.   <body>
  7.     <script type="text/javascript">
  8.       function BinaryTree() {
  9.         var Node = function(key) {
  10.           this.key = key;
  11.           this.left = null;
  12.           this.right = null;
  13.         }
  15.         var root = null;
  17.         var insertNode = function (node, newNode) {
  18.           if(newNode.key < node.key) {
  19.             if(node.left === null) {
  20.               node.left = newNode;
  21.             } else {
  22.               insertNode(node.left,newNode);
  23.             }
  24.           } else {
  25.             if(node.right === null) {
  26.               node.right = newNode;
  27.             } else {
  28.               insertNode(node.right, newNode)
  29.             }
  30.           }
  31.         }
  33.         this.insert = function (key) {
  34.           var NewNode = new Node(key)
  35.           if(root === null) {
  36.             root = NewNode
  37.           } else {
  38.             insertNode(root, NewNode);
  39.           }
  40.         };
  42.         var postOrderTraverseNode = function (node,callback) {
  43.           if(node !== null) {
  44.             postOrderTraverseNode(node.left,callback);
  45.             postOrderTraverseNode(node.right,callback);
  46.             callback(node.key);
  47.           }
  48.         }
  50.         this.postOrderTraverse = function (callback) {
  51.           postOrderTraverseNode(root, callback)
  52.         }
  53.       }
  55.       var nodes = [8,3,10,1,6,14,4,7,13];
  56.       var binaryTree = new BinaryTree();
  57.       nodes.forEach(function(key){
  58.         binaryTree.insert(key);
  59.       })
  61.       var callback = function (key) {
  62.         console.log(key);
  63.       }
  65.       binaryTree.postOrderTraverse(callback);
  66.     </script>
  67.   </body>
  68. </html>

二叉树节点查找

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

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

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvXzkyMTExMA_size_16_color_FFFFFF_t_70

查找二叉树节点的最小值

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

  1. <!DOCTYPE html>
  2. <html>
  3.   <head>
  4.     <title>binaryTree</title>
  5.   </head>
  6.   <body>
  7.     <script type="text/javascript">
  8.       function BinaryTree() {
  9.         var Node = function(key) {
  10.           this.key = key;
  11.           this.left = null;
  12.           this.right = null;
  13.         }
  15.         var root = null;
  17.         var insertNode = function (node, newNode) {
  18.           if(newNode.key < node.key) {
  19.             if(node.left === null) {
  20.               node.left = newNode;
  21.             } else {
  22.               insertNode(node.left,newNode);
  23.             }
  24.           } else {
  25.             if(node.right === null) {
  26.               node.right = newNode;
  27.             } else {
  28.               insertNode(node.right, newNode)
  29.             }
  30.           }
  31.         }
  33.         this.insert = function (key) {
  34.           var NewNode = new Node(key)
  35.           if(root === null) {
  36.             root = NewNode
  37.           } else {
  38.             insertNode(root, NewNode);
  39.           }
  40.         };
  42.         var minNode = function (node) {
  43.           if (node) {
  44.             while (node && node.left !== null) {
  45.               node = node.left; 
  46.             }
  47.             return node.key
  48.           }
  49.           return null;
  50.         }
  52.         this.min = function () {
  53.           return minNode(root)
  54.         }
  55.       }
  57.       var nodes = [8,3,10,1,6,14,4,7,13];
  58.       var binaryTree = new BinaryTree();
  59.       nodes.forEach(function(key){
  60.         binaryTree.insert(key);
  61.       })
  63.       var callback = function (key) {
  64.         console.log(key);
  65.       }
  66.       console.log('min node is:' + binaryTree.min());
  68.     </script>
  69.   </body>
  70. </html>

查找二叉树节点的最大值

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

  1. <!DOCTYPE html>
  2. <html>
  3.   <head>
  4.     <title>binaryTree</title>
  5.   </head>
  6.   <body>
  7.     <script type="text/javascript">
  8.       function BinaryTree() {
  9.         var Node = function(key) {
  10.           this.key = key;
  11.           this.left = null;
  12.           this.right = null;
  13.         }
  15.         var root = null;
  17.         var insertNode = function (node, newNode) {
  18.           if(newNode.key < node.key) {
  19.             if(node.left === null) {
  20.               node.left = newNode;
  21.             } else {
  22.               insertNode(node.left,newNode);
  23.             }
  24.           } else {
  25.             if(node.right === null) {
  26.               node.right = newNode;
  27.             } else {
  28.               insertNode(node.right, newNode)
  29.             }
  30.           }
  31.         }
  33.         this.insert = function (key) {
  34.           var NewNode = new Node(key)
  35.           if(root === null) {
  36.             root = NewNode
  37.           } else {
  38.             insertNode(root, NewNode);
  39.           }
  40.         };
  42.         var maxNode = function (node) {
  43.           if (node) {
  44.             while (node && node.right !== null) {
  45.               node = node.right; 
  46.             }
  47.             return node.key
  48.           }
  49.           return null;
  50.         }
  52.         this.max = function () {
  53.           return maxNode(root)
  54.         }
  55.       }
  57.       var nodes = [8,3,10,1,6,14,4,7,13];
  58.       var binaryTree = new BinaryTree();
  59.       nodes.forEach(function(key){
  60.         binaryTree.insert(key);
  61.       })
  63.       var callback = function (key) {
  64.         console.log(key);
  65.       }
  66.       console.log('max node is:' + binaryTree.max());
  68.     </script>
  69.   </body>
  70. </html>

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

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

  1. <!DOCTYPE html>
  2. <html>
  3.   <head>
  4.     <title>binaryTree</title>
  5.   </head>
  6.   <body>
  7.     <script type="text/javascript">
  8.       function BinaryTree() {
  9.         var Node = function(key) {
  10.           this.key = key;
  11.           this.left = null;
  12.           this.right = null;
  13.         }
  15.         var root = null;
  17.         var insertNode = function (node, newNode) {
  18.           if(newNode.key < node.key) {
  19.             if(node.left === null) {
  20.               node.left = newNode;
  21.             } else {
  22.               insertNode(node.left,newNode);
  23.             }
  24.           } else {
  25.             if(node.right === null) {
  26.               node.right = newNode;
  27.             } else {
  28.               insertNode(node.right, newNode)
  29.             }
  30.           }
  31.         }
  33.         this.insert = function (key) {
  34.           var NewNode = new Node(key)
  35.           if(root === null) {
  36.             root = NewNode
  37.           } else {
  38.             insertNode(root, NewNode);
  39.           }
  40.         };
  42.         var searchNode = function (node,key) {
  43.           if (node === null) {
  44.             return false
  45.           }
  46.           if( key < node.key) {
  47.             return searchNode(node.left, key)
  48.           } else if(key > node.key) {
  49.             return searchNode(node.right, key)
  50.           } else {
  51.             return true
  52.           }
  53.         }
  55.         this.search = function (key) {
  56.           return searchNode(root, key)
  57.         }
  58.       }
  60.       var nodes = [8,3,10,1,6,14,4,7,13];
  61.       var binaryTree = new BinaryTree();
  62.       nodes.forEach(function(key){
  63.         binaryTree.insert(key);
  64.       })
  66.       var callback = function (key) {
  67.         console.log(key);
  68.       }
  69.       console.log(binaryTree.search(7) ? 'key 7 is found' : 'key 7 is not found');
  70.       console.log(binaryTree.search(9) ? 'key 9 is found' : 'key 9 is not found');
  71.     </script>
  72.   </body>
  73. </html>

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

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

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

被删除节点为叶子节点

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

被删除节点仅有一个子树

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

被删除节点有两个子树

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

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

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

  1. <!DOCTYPE html>
  2. <html>
  3.   <head>
  4.     <title>binaryTree</title>
  5.   </head>
  6.   <body>
  7.     <script type="text/javascript">
  8.       function BinaryTree() {
  9.         var Node = function(key) {
  10.           this.key = key;
  11.           this.left = null;
  12.           this.right = null;
  13.         }
  15.         var root = null;
  17.         var insertNode = function (node, newNode) {
  18.           if(newNode.key < node.key) {
  19.             if(node.left === null) {
  20.               node.left = newNode;
  21.             } else {
  22.               insertNode(node.left,newNode);
  23.             }
  24.           } else {
  25.             if(node.right === null) {
  26.               node.right = newNode;
  27.             } else {
  28.               insertNode(node.right, newNode)
  29.             }
  30.           }
  31.         }
  33.         this.insert = function (key) {
  34.           var NewNode = new Node(key)
  35.           if(root === null) {
  36.             root = NewNode
  37.           } else {
  38.             insertNode(root, NewNode);
  39.           }
  40.         };
  41.         var findMinNode = function(node) {
  42.           if(node) {
  43.             while (node && node.left !== null) {
  44.               node = node.left;
  45.             }
  46.             return node
  47.           }
  48.         }
  49.         var removeNode = function (node,key) {
  50.           if (node === null) {
  51.             return false
  52.           }
  53.           if( key < node.key) {
  54.             node.left = removeNode(node.left, key)
  55.             return node
  56.           } else if(key > node.key) {
  57.             node.right = removeNode(node.right, key)
  58.             return node
  59.           } else {
  60.             // 没有子节点（子树）
  61.             if(node.left === null && node.right === null) {
  62.               node = null;
  63.               return node
  64.             }
  65.             // 只有右子节点（子树）
  66.             if(node.left === null) {
  67.               node = node.right;
  68.               return node;
  69.             // 只有左子节点（子树）
  70.             } else if (node.right === null) {
  71.               node = node.left;
  72.               return node;
  73.             }
  74.             // 有两个子节点（子树）
  75.             var aux = findMinNode(node.right);
  76.             node.key = aux.key;
  77.             node.right = removeNode(node.right, aux.key);
  78.             return node;
  79.           }
  80.         }
  82.         this.remove = function (key) {
  83.           return removeNode(root, key)
  84.         }
  85.       }
  87.       var nodes = [8,3,10,1,6,14,4,7,13];
  88.       var binaryTree = new BinaryTree();
  89.       nodes.forEach(function(key){
  90.         binaryTree.insert(key);
  91.       })
  93.       var callback = function (key) {
  94.         console.log(key);
  95.       }
  96.       binaryTree.remove(3)
  97.     </script>
  98.   </body>
  99. </html>

gitHub地址：排序二叉树的代码实现

发表评论

表情：
评论列表 （有 0 条评论，65人围观）

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

相关阅读

    相关 【算法】二叉树

    二叉树的种类 一个根节点下面只有两个子节点，称为二叉树 满二叉树 每一层的结点数都达到最大值，则这个二叉树就是满二叉树。 也就是说，如果一个二叉树的层数为K（

    逃离我推掉我的手逃离我推掉我的手/ 0 赞/ 113 阅读

    相关 二叉树算法

    二叉树是一种常用的数据结构。它有以下几个重要的性质： 1. 每个节点最多有两个子节点。 2. 左子节点和右子节点的值都要小于父节点的值。 二叉树的一些常用算法包括：

    落日映苍穹つ落日映苍穹つ/ 0 赞/ 122 阅读

    相关 iOS 二叉树相关算法实现

    什么是二叉树？ 在计算机科学中，二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”和“右子树”，左子树和右子树同时也是二叉树。二叉树的子树有左右之分，并且次

    桃扇骨桃扇骨/ 0 赞/ 357 阅读