二叉树实现（js）

二叉树

顾名思义，每个节点最多只有 2 度。
树，是数据存储的抽象形态。本质上来说，数据存储的结构仍然是线性的存储方式。
度：与该结点相连接的子结点个数。
叶子：度为 0 的结点。
子结点：连接着双亲结点的孩子指针。
双亲结点：结点的上一级结点。
根结点：最开始的结点，它没有双亲结点。

二叉树的遍历

1. 先序遍历（根左右）
2. 中序遍历（左根右）
3. 后序遍历（左右根）
4. 层序遍历（一层一层进行，根算一层）

二叉树实现（js）

1. 引入栈（用于遍历）https://www.jianshu.com/p/105983d18a10

let CS = require('./ChainStack.js')

2. 二叉树结点声明

class BTNode
{
    constructor (data)
    {
        this.data = data
        this.lchild = false
        this.rchild = false
        this.counter = 0
    }
    getData = () => this.data
    getLeftChild = () => this.lchild
    getRightChild = () => this.rchild
    getCounter = () => this.counter
    setData = data => this.data = data
    setLeftChild = lchild => this.lchild = lchild
    setRightChild = rchild => this.rchild = rchild
    addCounter = (interval=1) => this.counter+=interval
    subCounter = (interval=1) => this.counter-=interval
}

3. 二叉树的实现

class BinaryTree
{
    constructor ()
    {
        this.root = false
        this.counter = 0
    }
    setRoot = root => this.root = root
    addCounter = () => this.counter++
    length = () => this.counter
    LeftNode (fa, data)
    {
        let temp = new BTNode(data)
        if (fa)
        {
            fa.setLeftChild(temp)
        }
        else
        {
            this.root = temp
        }
        this.addCounter()
        return temp
    }
    RightNode (fa, data)
    {
        let temp = new BTNode(data)
        if (fa)
        {
            fa.setRightChild(temp)
        }
        else
        {
            this.root = temp
        }
        this.addCounter()
        return temp
    }
        
    PrevOrder ()
    {
        let p = this.root
        let stack = new CS.Stack()
        let str = ''
        while (p || !stack.empty())
        {
            while (p)
            {
                str += `${p.getData()} `
                stack.push(p)
                p = p.getLeftChild()
            }
            p = stack.pop().getRightChild()
        }
        console.log(str)
    }
    MidOrder ()
    {
        let p = this.root
        let stack = new CS.Stack()
        let str = ''
        while (p || !stack.empty())
        {
            while (p)
            {
                stack.push(p)
                p = p.getLeftChild()
            }
            p = stack.pop()
            str += `${p.getData()} `
            p = p.getRightChild()
        }
        console.log(str)
    }
    PostOrder ()
    {
        let p = this.root
        let stack = new CS.Stack()
        let str = ''

        while (p || !stack.empty())
        {
            while (p && p.getCounter() === 0)
            {
                stack.push(p)
                p.addCounter()
                p = p.getLeftChild()
            }

            p = stack.pop()

            if (p && p.getCounter() === 2)
            {
                str += `${p.getData()} `
            }
            else if (p && p.getCounter() === 1)
            {
                stack.push(p)
                p.addCounter()
                p = p.getRightChild()
            }
        }
        console.log(str)
    }
}

4. 二叉树测试

let bt = new BinaryTree()

let r = bt.LeftNode(false, 1)
let r1 = bt.LeftNode(r, 2)
let r2 = bt.RightNode(r, 3)
let r3 = bt.LeftNode(r1, 4)
let r4 = bt.LeftNode(r2, 5)
let r5 = bt.RightNode(r2, 6)

bt.PrevOrder()
bt.MidOrder()
bt.PostOrder()

后记

1. 由于简单，这里就不进行层序遍历的实现。
2. 遍历方式均不采用递归。
3. 左结点主要用于遍历左子树和数据输出（无左儿子）。
4. 右结点主要用于指针位置的移动与检查。
5. 遍历的双亲结点返回方式主要用栈进行。