javascript数据结构与算法--二叉树遍历（后序）
后序遍历先访问叶子节点，从左子树到右子树，再到根节点。
<span style="color: #008000;">/
<span style="color: #008000;">用来生成一个节点<span style="color: #008000;">/<span style="color: #0000ff;">function<span style="color: #000000;"> Node(data,left,right) {
<span style="color: #0000ff;">this.data = data;<span style="color: #008000;">//<span style="color: #008000;">节点存储的数据
<span style="color: #0000ff;">this.left =<span style="color: #000000;"> left;
<span style="color: #0000ff;">this.right =<span style="color: #000000;"> right;
<span style="color: #0000ff;">this.show =<span style="color: #000000;"> show;
}
<span style="color: #0000ff;">function<span style="color: #000000;"> show() {
<span style="color: #0000ff;">return <span style="color: #0000ff;">this<span style="color: #000000;">.data;
}
<span style="color: #008000;">/<span style="color: #008000;">用来生成一个二叉树<span style="color: #008000;">/
<span style="color: #0000ff;">function<span style="color: #000000;"> BST() {
<span style="color: #0000ff;">this.root = <span style="color: #0000ff;">null<span style="color: #000000;">;
<span style="color: #0000ff;">this.insert =<span style="color: #000000;"> insert;
}
<span style="color: #008000;">/*<span style="color: #008000;">将数据插入二叉树
（1）设根节点为当前节点。
（2）如果待插入节点保存的数据小于当前节点，则设新的当前节点为原节点的左节点；反
之，执行第4步。
（3）如果当前节点的左节点为null，就将新的节点插入这个位置，退出循环；反之，继续
执行下一次循环。
（4）设新的当前节点为原节点的右节点。
（5）如果当前节点的右节点为null，就将新的节点插入这个位置，退出循环；反之，继续
执行下一次循环。
- <span style="color: #008000;">*/
<span style="color: #0000ff;">function<span style="color: #000000;"> insert(data) {
<span style="color: #0000ff;">var n = <span style="color: #0000ff;">new Node(data,<span style="color: #0000ff;">null,<span style="color: #0000ff;">null<span style="color: #000000;">);
<span style="color: #0000ff;">if (<span style="color: #0000ff;">this.root == <span style="color: #0000ff;">null<span style="color: #000000;">) {
<span style="color: #0000ff;">this.root =<span style="color: #000000;"> n;
}
<span style="color: #0000ff;">else<span style="color: #000000;"> {
<span style="color: #0000ff;">var current = <span style="color: #0000ff;">this<span style="color: #000000;">.root;
<span style="color: #0000ff;">var<span style="color: #000000;"> parent;
<span style="color: #0000ff;">while (<span style="color: #0000ff;">true<span style="color: #000000;">) {
parent =<span style="color: #000000;"> current;
<span style="color: #0000ff;">if (data <<span style="color: #000000;"> current.data) {
current = current.left;<span style="color: #008000;">//<span style="color: #008000;">待插入节点保存的数据小于当前节点，则设新的当前节点为原节点的左节点
<span style="color: #0000ff;">if (current == <span style="color: #0000ff;">null) {<span style="color: #008000;">//<span style="color: #008000;">如果当前节点的左节点为null，就将新的节点插入这个位置，退出循环；反之，继续执行下一次while循环。
parent.left =<span style="color: #000000;"> n;
<span style="color: #0000ff;">break<span style="color: #000000;">;
}
}
<span style="color: #0000ff;">else<span style="color: #000000;"> {
current = current.right;<span style="color: #008000;">//<span style="color: #008000;">待插入节点保存的数据小于当前节点，则设新的当前节点为原节点的左节点
<span style="color: #0000ff;">if (current == <span style="color: #0000ff;">null<span style="color: #000000;">) {
parent.right =<span style="color: #000000;"> n;
<span style="color: #0000ff;">break<span style="color: #000000;">;
}
}
}
}
}
<span style="color: #008000;">/<span style="color: #008000;">后序遍历
用递归的方法
<span style="color: #008000;">*/
<span style="color: #0000ff;">function<span style="color: #000000;"> postOrder(node) {
<span style="color: #0000ff;">if (!(node == <span style="color: #0000ff;">null<span style="color: #000000;">)) {
postOrder(node.left);
postOrder(node.right);
console.log(node.show() + " "<span style="color: #000000;">);
}
}
<span style="color: #008000;">/<span style="color: #008000;"> 测试代码 <span style="color: #008000;">/
<span style="color: #0000ff;">var nums = <span style="color: #0000ff;">new<span style="color: #000000;"> BST();
nums.insert(23<span style="color: #000000;">);
nums.insert(45<span style="color: #000000;">);
nums.insert(16<span style="color: #000000;">);
nums.insert(37<span style="color: #000000;">);
nums.insert(3<span style="color: #000000;">);
nums.insert(99<span style="color: #000000;">);
nums.insert(22<span style="color: #000000;">);
console.log("后序遍历: "<span style="color: #000000;">);
postOrder(nums.root);
