二叉樹遍歷：
- 前序遍歷：先輸出當前節點；然后遍歷左子樹，如果左子樹不為空，遞回前序遍歷；接著遍歷右子樹，如果右子樹不為空，遞回前序遍歷
- 中序遍歷：先遍歷當前節點左子樹，如果不為空，遞回中序遍歷；輸出當前節點，接著遍歷當前節點右子樹，如果不為空，遞回中序遍歷
- 后序遍歷：先遍歷當前節點左子樹，如果不為空，遞回后序遍歷；在遍歷當前節點右子樹，不過不為空，遞回后序遍歷，輸出當前節點
怎么區分何種遍歷，就是看當前節點的輸出順序
class HeroNode {
constructor(no,name){
this.no = no
this.name = name
}
setLeft(left){
this.left = left
}
setRight(right){
this.right = right
}
toString(){
console.log(this.name)
}
preOrder(){
if(this.no == 2) {
return false
}
if(this.left){
this.left.preOrder()
}
if(this.right){
this.right.preOrder()
}
}
preOrderSearch(no){
if(this.no == no) {
return this
}
let res = null
if(this.left){
res = this.left.preOrderSearch(no)
}
if(res) return res
if(this.right){
return this.right.preOrderSearch(no)
}
return res
}
infixOrder(){
if(this.left){
this.left.infixOrder()
}
console.log(this.toString())
if(this.right){
this.right.infixOrder()
}
}
postOrder(){
if(this.left){
this.left.postOrder()
}
if(this.right){
this.right.postOrder()
}
console.log(this.toString())
}
}
class BinaryTree {
constructor(root){
this.root = root
}
setRoot(root){
this.root = root
}
preOrder(){
if(this.root){
this.root.preOrder()
}
}
infixOrder(){
if(this.root){
this.root.infixOrder()
}
}
postOrder(){
if(this.root){
this.root.postOrder()
}
}
preOrderSearch(no){
if(this.root){
return this.root.preOrderSearch(no)
}
}
}
function exec(){
// 創建二叉樹
const bt = new BinaryTree()
// 創建節點
const root = new HeroNode(1,'劉備')
const h2 = new HeroNode(2,'關羽')
const h3 = new HeroNode(3,'張飛')
const h4 = new HeroNode(4,'趙云')
root.setLeft(h2)
root.setRight(h3)
h3.setRight(h4)
bt.setRoot(root)
return bt.preOrderSearch(4)
}
console.log(exec())
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/423832.html
標籤：其他