二叉树
二叉树是典型的树状结构，最顶部的节点称为根节点，普通的节点一般称为子节点或者父节点，最底层的节点称为叶子节点，
特点
每个节点最多只有两个子节点, 根据遍历节点的顺序不同分为：先序遍历、中序遍历、后续遍历
- 先看最简单的二叉树是怎么遍历的
先序遍历从父节点开始，然后访问左节点，最后访问右节点
中序遍历先从左节点开始，然后访问根节点，最后访问右节点
后续遍历先从左节点开始，然后访问右节点，最后访问根节点
- 再看看复杂的情况下怎么遍历的
复杂的二叉树遍历可以将整个二叉树分割成多个基础的二叉树
先序遍历：ABDEHCFIG
中序遍历：DBHEAFICG
后序遍历：DHEBIFGCA
方法
| 方法 | 描述 |
| insert | 插入 |
| midOrder | 中序遍历 |
| preOrder | 先序遍历 |
| afteOrder | 后续遍历 |
| find | 查找特定值 |
| findMim | 查找最小值 |
| findMax | 查找最大值 |
实现
class Node { constructor(element, left, right){ this.element = element; this.left = left; this.right = right; } show(){ return this.element; } } class BST { constructor(){ this.root = null; } insert(element){ let node = new Node(element, null, null); if (this.root == null) { this.root = node; }else{ let currNode = this.root; let parent; while(true){ if (currNode.element > element) { currNode = currNode.left; if (currNode.left == null) { currNode.left = node; break; } }else{ currNode = currNode.right; if (currNode.right == null) { currNode.right = node; break; } } } } } // 中序遍历 midOrder(node){ if (node != null) { this,midOrder(node.left); node.show(); this.midOrder(node.right); } } // 先序遍历 preOrder(){ if (node != null) { node.show(); this,preOrder(node.left); this.preOrder(node.right); } } // 后序遍历 afteOrder(){ if (node != null) { this,afteOrder(node.left); this.afteOrder(node.right); node.show(); } } // 寻找最小值 findMim(){ let currNode = this.root; while (currNode.left != null) { currNode = currNode.left; } return currNode.element; } // 寻找最大值 findMax(){ let currNode = this.root; while (currNode.right != null) { currNode = currNode.right; } return currNode.element; } // 寻找给定值 find(element){ let currNode = this.root; while(currNode != null){ if (currNode.element < element) { currNode = currNode.left; }else if(currNode.element > element){ currNode = currNode.right; }else{ return currNode; } } } }
