二叉樹

顧名思義，每個節(jié)點最多只有 2 度。
樹，是數(shù)據(jù)存儲的抽象形態(tài)。本質(zhì)上來說，數(shù)據(jù)存儲的結(jié)構(gòu)仍然是線性的存儲方式。
度：與該結(jié)點相連接的子結(jié)點個數(shù)。
葉子：度為 0 的結(jié)點。
子結(jié)點：連接著雙親結(jié)點的孩子指針。
雙親結(jié)點：結(jié)點的上一級結(jié)點。
根結(jié)點：最開始的結(jié)點，它沒有雙親結(jié)點。

二叉樹的遍歷

1. 先序遍歷（根左右）
2. 中序遍歷（左根右）
3. 后序遍歷（左右根）
4. 層序遍歷（一層一層進(jìn)行，根算一層）

二叉樹實現(xiàn)（js）

1. 引入棧（用于遍歷）http://www.itdecent.cn/p/105983d18a10

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

2. 二叉樹結(jié)點聲明

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. 二叉樹的實現(xiàn)

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. 由于簡單，這里就不進(jìn)行層序遍歷的實現(xiàn)。
2. 遍歷方式均不采用遞歸。
3. 左結(jié)點主要用于遍歷左子樹和數(shù)據(jù)輸出（無左兒子）。
4. 右結(jié)點主要用于指針位置的移動與檢查。
5. 遍歷的雙親結(jié)點返回方式主要用棧進(jìn)行。