二叉树
顾名思义，每个节点最多只有 2 度。
树，是数据存储的抽象形态。本质上来说，数据存储的结构仍然是线性的存储方式。
度：与该结点相连接的子结点个数。
叶子：度为 0 的结点。
子结点：连接着双亲结点的孩子指针。
双亲结点：结点的上一级结点。
根结点：最开始的结点，它没有双亲结点。
二叉树的遍历
- 先序遍历（根左右）
- 中序遍历（左根右）
- 后序遍历（左右根）
- 层序遍历（一层一层进行，根算一层）
二叉树实现（js）
let CS = require('./ChainStack.js')
- 二叉树结点声明
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
}
- 二叉树的实现
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)
}
}
- 二叉树测试
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()
后记
- 由于简单，这里就不进行层序遍历的实现。
- 遍历方式均不采用递归。
- 左结点主要用于遍历左子树和数据输出（无左儿子）。
- 右结点主要用于指针位置的移动与检查。
- 遍历的双亲结点返回方式主要用栈进行。
