Giả sử, chúng ta có một cây nhị phân được biểu diễn như thế này -
4 / \ 2 7 / \ / \ 1 3 6 9
Chúng tôi được yêu cầu viết một hàm JavaScript lấy gốc của cây nhị phân này và đảo ngược nó.
Phiên bản đảo ngược của cây nhị phân ở trên này sẽ giống như thế này -
4 / \ 7 2 / \ / \ 9 6 3 1
Ví dụ
Mã cho điều này sẽ là -
// class for a single tree node
class Node{
constructor(val){
this.val = val;
this.left = null;
this.right = null;
};
};
// class for binary tree
class BinaryTree{
constructor(){
// root of the binary tree
this.root = null;
};
insert = (data) => {
// creating a new node with data
const newNode = new Node(data);
// if root is null, then this node will be the root
if(this.root === null){
this.root = newNode;
}else{
// otherwise we find the correct position to insert this node
this.insertData(this.root, newNode);
};
};
insertData = (node, newNode) => {
if(newNode.val < node.val){
if(node.left === null){
node.left = newNode;
}else{
this.insertData(node.left, newNode);
}
}else{
if(node.right === null){
node.right = newNode;
}else{
this.insertData(node.right, newNode);
}
}
};
// function to invert the binary tree
invert = (node) => {
if(node === null){
return;
};
[node.left, node.right] = [node.right, node.left];
this.invert(node.right);
this.invert(node.left);
}
traverse = (node) => {
if(node === null){
return;
};
this.traverse(node.right);
console.log(node.val);
this.traverse(node.left);
};
};
const Tree = new BinaryTree();
Tree.insert(2);
Tree.insert(7);
Tree.insert(4);
Tree.insert(1);
Tree.insert(9);
Tree.insert(3);
Tree.insert(6);
// original right to left traversal
Tree.traverse(Tree.root);
Tree.invert(Tree.root);
console.log('after inversion');
// traversal right to left after inversion
Tree.traverse(Tree.root); Đầu ra
Và đầu ra trong bảng điều khiển sẽ là -
9 7 6 4 3 2 1 after inversion 1 2 3 4 6 7 9