function preOrder(node){
//前序遍历
if(node == null) return;
console.log(node.data);
preOrder(node.left);
preOrder(node.right);
}
function inOrder(node){
//中序遍历
if(node == null) return;
inOrder(node.left);
console.log(node.data);
inOrder(node.right);
}
function postOrder(node){
//后序遍历
if(node == null) return ;
postOrder(node.left);
postOrder(node.right);
console.log(node.data);
}
class Node{
constructor(data){
this.data = data;
this.left = null;
this.right = null;
}
}
class BinaryTree{
constructor(data){
this.tree = new Node(data);
}
binaryFind(data){
let p = this.tree;
while(p != null){
if(p.data == data) {
return p;
}else if(p.data > data){
p = p.right;
}else {
p = p.left;
}
}
return null;
}
binaryInsert(data){
let p = this.tree;
while( p != null){
if(data > p.data){
if(p.right == null){
p.right = new Node(data);
return;
}else{
p = p.right;
}
}else{
if(p.left == null){
p.left = new Node(data);
return;
}else{
p = p.left;
}
}
}
}
binaryDelete(data){
let p = this.tree,pp = null;//pp用来记录节点的父节点
while(p != null && p.data != data){
pp = p;
if(p.data > data){
p = p.right;
}else{
p = p.left;
}
}
if(p == null) return;//没有找到这个节点
//找到了要删除的节点，如果他有两个子节点 -> 查找右子树中最小的节点(找到右子树中最左边的叶节点)
if(p.left != null && p.right != null){
let minp = p.right,minpp = p;
while(minp.left != null){
minpp = minp;
minp = minp.left;
}
//找到了最左边的叶节点 进行迁移哦
p.data = minp.data;
p = minp;//为了兼容下面的删除操作哦
pp = minpp;
}
let child;
if(p.left != null) child = p.left;
else if(p.right != null) child = p.right;
else child = null;
if(pp == null){this.tree = child}
else if(pp.left == p) pp.left = child;
else pp.right = child;
}
}
var inorderTraversal = function(root) {
let result = [],p = root;
if(p == null) return [];
if(p.left!=null){
let leftresult = inorderTraversal(p.left);
result = result.concat(leftresult)
}
result.push(p.val);
if(p.right != null){
let rightresult = inorderTraversal(p.right);
result = result.concat(rightresult);
}
return result;
};
var isSameTree = function(p, q) {
if(p == null && q == null) return true;
if(p == null && q != null) return false;
if(p != null && q == null) return false;
if(p!= null && q != null){
if(p.val != q.val){
return false
}
return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);//左右相等
}
};
var maxDepth = function(root) {
if(root == null) return 0;
let left = maxDepth(root.left);
let right = maxDepth(root.right);
return Math.max(left,right)+1;
};
