【数据结构】我的学习笔记-二叉树

二叉树

二叉树是典型的树状结构，最顶部的节点称为根节点，普通的节点一般称为子节点或者父节点，最底层的节点称为叶子节点，

特点

每个节点最多只有两个子节点,
根据遍历节点的顺序不同分为：先序遍历、中序遍历、后续遍历

• 先看最简单的二叉树是怎么遍历的

先序遍历从父节点开始，然后访问左节点，最后访问右节点

中序遍历先从左节点开始，然后访问根节点，最后访问右节点

后续遍历先从左节点开始，然后访问右节点，最后访问根节点

• 再看看复杂的情况下怎么遍历的

复杂的二叉树遍历可以将整个二叉树分割成多个基础的二叉树

先序遍历：ABDEHCFIG

中序遍历：DBHEAFICG

后序遍历：DHEBIFGCA

方法

实现

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;
            }
        }
    }
}