二叉树查找树

[lsyf]

1. 需求

• 二叉树查找树(简单)

2. 设计

• 结构
  1. 树，根节点和长度；节点，左右节点，值
• 行为
  1. 插入，删除，查找
  2. 遍历：
     • 通用方案，每个节点都会入栈两次，对节点加状态用于判断是否打印，通过出栈顺序控制先中后序遍历
     • 变种通用，不更改节点或栈的数据结构，由于节点首次遍历都不会打印，可用map保存节点允许打印状态
• 边界条件
  1. 删除的节点， 无子节点
  2. 删除的节点， 只有单个子节点
  3. 删除的节点，有双子节点，去左子树右下节点或者右子树左下节点替换

3. 代码

package tree

import (
	"container/list"
	"strconv"
	"strings"
)

type node struct {
	left, right *node
	Value       int
}

type BiTree struct {
	root *node
	len  int
}

func NewBiTree() *BiTree {
	return &BiTree{}
}

func (t *BiTree) Add(v int) {
	n := t.root
	if n == nil {
		t.root = &node{Value: v}
		t.len++
		return
	}
	for {
		switch {
		case v < n.Value:
			if n.left == nil {
				new := &node{Value: v}
				n.left = new
				t.len++
				return
			}
			n = n.left
		default:
			if n.right == nil {
				new := &node{Value: v}
				n.right = new
				t.len++
				return
			}
			n = n.right
		}
	}

}

func (t *BiTree) Delete(v int) *node {
	p, n := find(t.root, v)

	switch {
	case n == nil:
		return nil
	case n.left == nil || n.right == nil:
		a := If(n.left == nil, n.right, n.left)
		replace(p, n, a)
		return n
	default:
		maxP, max := findMax(n.left)
		replace(maxP, max, nil)
		if n != t.root {
			replace(p, n, max)
		} else {
			t.root = max
		}
		if n.left != max {
			max.left = n.left
		}
		max.right = n.right
		return n
	}
}

func replace(p, a, b *node) {
	switch {
	case p == nil:
		return
	case p.left == a:
		p.left = b
	default:
		p.right = b
	}
}

func If(condition bool, v1, v2 *node) *node {
	if condition {
		return v1
	}
	return v2
}

func findMax(root *node) (p, n *node) {
	n = root
	for {
		switch {
		case n == nil:
			return nil, nil
		case n.right == nil:
			return p, n
		default:
			p = n
			n = n.right
		}
	}
}
func find(root *node, v int) (p, n *node) {
	n = root
	for {
		switch {
		case n == nil:
			return nil, nil
		case v == n.Value:
			return p, n
		case v < n.Value:
			p = n
			n = n.left
			continue
		default:
			p = n
			n = n.right
			continue
		}
	}

}

func (t *BiTree) Search(v int) *node {
	_, n := find(t.root, v)
	return n
}

func (t *BiTree) Print(a int) string {

	if t.root == nil {
		return ""
	}
	data := make([]string, 0, t.len)
	s := &stack{list.New()}
	switch a {
	case 10:
		n := t.root
		m := make(map[*node]bool)
		s.push(t.root)
		for !s.empty() {
			n = s.pop()
			if n == nil {
				continue
			}
			if m[n] { //由于每个节点都会入栈两次，第一次标记，第二次打印值
				data = append(data, strconv.Itoa(n.Value))
			} else {
				s.push(n.right)
				s.push(n.left)
				s.push(n)
				m[n] = true
			}
		}
	case 20:
		n := t.root
		m := make(map[*node]bool)
		s.push(t.root)
		for !s.empty() {
			n = s.pop()
			if n == nil {
				continue
			}
			if m[n] {
				data = append(data, strconv.Itoa(n.Value))
			} else {
				s.push(n.right)
				s.push(n)
				s.push(n.left)
				m[n] = true
			}
		}
	case 30:
		n := t.root
		m := make(map[*node]bool)
		s.push(t.root)
		for !s.empty() {
			n = s.pop()
			if n == nil {
				continue
			}
			if m[n] {
				data = append(data, strconv.Itoa(n.Value))
			} else {
				s.push(n)
				s.push(n.right)
				s.push(n.left)
				m[n] = true
			}
		}

	case 11:
		//先序遍历方案1：
		//对每个节点压入栈，打印值，同样处理左孩子；
		//到达左下角后，栈弹出节点处理右孩子

		n := t.root
		for !s.empty() || n != nil { //如果栈为空并且节点为空，代表没有节点能够处理
			if n != nil { //节点不为空的话处理左孩子
				data = append(data, strconv.Itoa(n.Value))
				s.push(n)
				n = n.left
			} else { //节点为空的话 弹出栈顶节点，处理其右孩子
				n = s.pop().right
			}
		}
	case 12:
		//先序遍历方案2：
		//按照栈先入后出结构，对每个节点打印值，先压入右孩子，再压入左孩子
		//栈弹出各个节点依次处理

		n := t.root
		s.push(t.root)
		for !s.empty() {
			n = s.pop()
			data = append(data, strconv.Itoa(n.Value))
			if n.right != nil {
				s.push(n.right)
			}
			if n.left != nil {
				s.push(n.left)
			}
		}
	case 21:
		//中序遍历方案1：
		//对每个节点压入栈，同样处理左孩子；
		//到达左下角后，栈弹出节点，打印值，处理右孩子
		n := t.root
		for !s.empty() || n != nil {
			if n != nil {
				s.push(n)
				n = n.left
			} else {
				n = s.pop()
				data = append(data, strconv.Itoa(n.Value))
				n = n.right
			}
		}
	case 31:
		//后序遍历方案1：
		// 左右根 翻转是 根右左
		//按照栈先入后出结构，对每个节点打印值，先压入左孩子，再压入右孩子
		//栈弹出各个节点依次处理
		//最后翻转
		n := t.root
		s.push(t.root)
		for !s.empty() {
			n = s.pop()
			data = append(data, strconv.Itoa(n.Value))
			if n.left != nil {
				s.push(n.left)
			}
			if n.right != nil {
				s.push(n.right)
			}
		}
		for i, j := 0, len(data)-1; i < j; i, j = i+1, j-1 {
			data[i], data[j] = data[j], data[i]
		}

	case 4:
		n := t.root
		s.push(t.root)
		q := &queue{list.New()}
		q.put(t.root)
		for !q.empty() {
			n = q.poll()
			if n == nil {
				continue
			}
			data = append(data, strconv.Itoa(n.Value))
			q.put(n.left)
			q.put(n.right)
		}
	}
	return strings.Join(data, ",")
}

type stack struct {
	list *list.List
}

func (s *stack) push(v *node) {
	s.list.PushBack(v)
}

func (s *stack) empty() bool {
	return s.list.Len() == 0
}
func (s *stack) pop() *node {
	e := s.list.Back()
	if e != nil {
		s.list.Remove(e)
		return e.Value.(*node)
	}
	return nil
}

type queue struct {
	list *list.List
}

func (s *queue) put(v *node) {
	s.list.PushBack(v)
}

func (s *queue) empty() bool {
	return s.list.Len() == 0
}
func (s *queue) poll() *node {
	e := s.list.Front()
	if e != nil {
		s.list.Remove(e)
		return e.Value.(*node)
	}
	return nil
}