二叉树-JZTXT

二叉排序树

class Node {
	constructor(value) {
		this.value = value
		this.left = null
		this.right = null
	}
}

class Tree {
	constructor() {
		this.root = null
		this.travelResult = []
	}
	insertByFather(father, node) {
		if (father.value > node.value) {
			if (father.left === null) {
				father.left = node
			} else {
				this.insertByFather(father.left, node)
			}
		} else {
			if (father.right === null) {
				father.right = node
			} else {
				this.insertByFather(father.right, node)
			}
		}
	}
	insert(value) {
		const node = new Node(value)
		if (this.root === null) {
			this.root = node
		} else {
			this.insertByFather(this.root, node)
		}
	}
	preTravel(node) {
		if (node) {
			this.travelResult.push(node.value)
			this.preTravel(node.left)
			this.preTravel(node.right)
		}
	}
	_preTravel(root) {
		if (root) {
			const stack = []
			stack.push(root)
			while (stack.length > 0) {
				const node = stack.pop()
				this.travelResult.push(node.value)
				if (node.right) {
					stack.push(node.right)
				}
				if (node.left) {
					stack.push(node.left)
				}
			}
		}
	}
	midTravel(node) {
		if (node) {
			this.midTravel(node.left)
			this.travelResult.push(node.value)
			this.midTravel(node.right)
		}
	}
	_midTravel(root) {
		if (root) {
			const stack = []
			let node = root
			while(node || stack.length > 0) {
				while(node) {
					stack.push(node)
					node = node.left
				}
				node = stack.pop()
				this.travelResult.push(node.value)
				node = node.right
			}
		}
	}
	lastTravel(node) {
		if (node) {
			this.lastTravel(node.left)
			this.lastTravel(node.right)
			this.travelResult.push(node.value)
		}
	}
    //后序遍历其实就是前序遍历反转
    //先前序遍历，将结果反转即可
	_lastTravel(root) {
		if (root) {
			const stack = []
			stack.push(root)
			while (stack.length > 0) {
				const node = stack.pop()
				this.travelResult.push(node.value)
				if (node.right) {
					stack.push(node.right)
				}
				if (node.left) {
					stack.push(node.left)
				}
			}
		}
		this.travelResult = this.travelResult.reverse()
	}
}

完全二叉树

class Node {
	constructor(value) {
		this.value = value
		this.left = null
		this.right = null
	}
}

class Tree {
	constructor() {
		this.root = null
		this.travelResult = []
	}

	insert(value) {
		const node = new Node(value)
		if (this.root === null) {
			this.root = node
			return
		}
		const stack = []
		stack.push(this.node)
		while (stack.length > 0) {
			const node = stack.pop()
			if (node.left === null) {
				node.left = node
				return
			} else if (node.right === null) {
				node.right = node
				return
			} else {
				stack.push(node.right)
				stack.push(node.left)
			}
		}
	}

	levelTravel() {
		if (!this.root) {
			return []
		}
		const stack = []
		stack.push(this.root)
		while (stack.length > 0) {
			const node = stack.pop()
			this.travelResult.push(stack.value)
			if (node.right) {
				stack.push(node.right)
			}
			if (node.left) {
				stack.push(node.left)
			}
		}
	}
}