二叉树
二叉树
前序遍历
- 先访问根节点（父节点）；
- 再访问当前节点的左子树；
- 若当前节点无左子树，则访问当前节点的右子树；
则上述二叉树图中，前序遍历的值为： 1，2，4，5，3，6，7
中序遍历
- 先访问当前节点的左子树；
- 再访问当前节点的父节点；
- 若当前节点无左子树，则访问当前节点的右子树；
则上述二叉树中，中序遍历的值为： 4，2，5，1，6，3，7
后序遍历
- 先访问当前节点的左子树；
- 若当前节点无左子树，则访问当前节点的右子树
- 最后访问当前节点的父节点
则上述二叉树中，后序遍历的值为：4，5，2，6，7，3，1
递归实现方法
首先创建一棵二叉搜索树，所谓二叉搜索树，则左子树节点的值小于父节点，右子树的值大于父节点
function BinTreeNode(data) { // 创建树节点函数
this.data = data;
this.leftChild = null;
this.rightChild = null;
}
function BinaryTree() {
this.root = null;
}
BinaryTree.prototype.insert = function (node) { // 向节点中插入元素
let binTreeNode = new BinTreeNode(node);
if (this.root === null) {
this.root = binTreeNode;
} else {
let curr_node = this.root;
let parent;
while (true) {
parent = curr_node;
// 新加入的值如果小于父节点，则为左子树，否则为右子树
if(node < curr_node.data){
curr_node = curr_node.leftChild;
if(curr_node === null){
parent.leftChild = binTreeNode;
break;
}
} else {
curr_node = curr_node.rightChild;
if(curr_node === null){
parent.rightChild = binTreeNode;
break;
}
}
}
}
}
// 测试数据
var bt = new BinaryTree();
var nums = [12,10,19,3,2,10,15,13];
for(var i = 0;i < nums.length;i ++){
bt.insert(nums[i]);
}
console.log(bt.root);
前序遍历
BinaryTree.prototype.pre_order = function(node){
if(node === null){
return null;
}
console.log(node.data);
this.pre_order(node.leftChild);
this.pre_order(node.rightChild);
}
// 测试
bt.pre_order(bt.root);
中序遍历
BinaryTree.prototype.in_order = function(node){ // 中序遍历
if(node === null){
return null;
}
this.in_order(node.leftChild);
console.log(node.data);
this.in_order(node.rightChild);
}
// 测试
bt.in_order(bt.root);
后序遍历
BinaryTree.prototype.after_order = function(node){ // 后续遍历
if(node === null){
return null;
}
this.after_order(node.leftChild);
this.after_order(node.rightChild);
console.log(node.data);
}
// 测试
bt.after_order(bt.root);
非递归实现方法
递归转为非递归，要使用while循环。
前序遍历
思路： 前序遍历顺序是 父节点>左节点>右节点，故在while循环里第一步是打印父节点数据，因为右节点是最后打印，并且先进入数组中的右节点后打印，这一思想和栈的思想不谋而合，可以用栈来处理右节点，处理左节点的时候，只需要让当前节点指向左节点即可，左节点打印完毕，让栈中右节点一次出栈。
BinaryTree.prototype.pre_order_nodig = function(node){ // 前序遍历
if(node === null){
return null;
}
let stack = [];
let curr_node = node;
while(curr_node){
console.log(curr_node.data);
if(curr_node.rightChild){
stack.push(curr_node.rightChild);
}
if(curr_node.leftChild){
curr_node = curr_node.leftChild;
} else {
curr_node = stack.pop();
}
}
}
// 测试
bt.pre_order_nodig(bt.root);
打印结果
中序遍历
思路： 中序遍历顺序是 左节点>父节点>右节点，用while循环让左节点和左节点的根节点进栈，再外层while循环让栈里面的元素打印，如果该节点有右节点，则右子树进栈，有左节点则先打印左节点，无则打印该右节点
BinaryTree.prototype.in_order_nodig = function(node){ // 中序遍历
if(node === null){
return null;
}
let stack = [];
let curr_node = node;
while(true){
while(curr_node){
stack.push(curr_node);
curr_node = curr_node.leftChild;
}
let pop_node = stack.pop();
console.log(pop_node.data);
curr_node = pop_node.rightChild;
if(!curr_node && stack.length === 0){
break;
}
}
}
// 测试
bt.in_order_nodig (bt.root);
打印结果
后序遍历
思路： 后序遍历顺序是 左节点>右节点>父节点，找到树的最深层，优先打印左节点，其次是右节点，最后是父节点, 如果没有右节点，则先是左节点，再是根节点，故定义一个栈1，用来存放处理的根节点，左节点，右节点，栈2用来存放符合条件的节点，最后将栈2依次从栈顶元素输入
BinaryTree.prototype.after_order_nodig = function(node){ // 后序遍历
if(node === null){
return null;
}
let stack1 = [];
let stack2 = [];
stack1.push(node);
while(stack1.length > 0){
let curr_node = stack1.pop();
stack2.push(curr_node.data);
if(curr_node.leftChild) stack1.push(curr_node.leftChild);
if(curr_node.rightChild) stack1.push(curr_node.rightChild);
}
while(stack2.length > 0){
console.log(stack2.pop());
}
}
// 测试
bt.in_order_nodig (bt.root);
打印结果
以上就是二叉树前序遍历，中序遍历，后序遍历的所有内容。有问题欢迎指出。
