二叉树Morris遍历算法golang

前言:

自己写的不BB，思路差很多，这是golang实现版。 可以看一下博客园的图解，要冷静下来思考，还是很有趣的。

package tree
import (
	"container/list"
)
//二叉排序树树
type BSTree struct {
	root *BSTNode
	size int
}
//二叉树节点
type BSTNode struct {
	data   interface{}
	lchild *BSTNode
	rchild *BSTNode
	parent *BSTNode
}
//新建一个节点
func NewBSTNode(e interface{}) *BSTNode {
	return &BSTNode{data: e}
}
func NewBSTree() *BSTree {
	return &BSTree{}
}
// 插入节点
func (tree *BSTree) InsertNode(node *BSTNode) *BSTree {
	if tree.root == nil {
		tree.root = node
		return tree
	}
	thisNode := tree.root
	for {
		if thisNode.data.(int) < node.data.(int) {
			if thisNode.rchild == nil {
				thisNode.rchild = node
				node.parent = thisNode
				break
			} else {
				thisNode = thisNode.rchild
				continue
			}
		} else {
			if thisNode.lchild == nil {
				thisNode.lchild = node
				node.parent = thisNode
				break
			} else {
				thisNode = thisNode.lchild
				continue
			}
		}
	}
	return tree
}
// 中序遍历 morris
func (tree *BSTree) InOrderTraversal() *list.List {
	l := list.New()
	cur := tree.root
	for cur != nil {
		// 左节点为空直接输出
		if cur.lchild == nil {
			l.PushBack(cur.data)
			cur = cur.rchild
		} else {
			// find predecessor
			prev := cur.lchild
			for prev.rchild != nil && prev.rchild != cur {
				prev = prev.rchild
			}
			if prev.rchild == nil {
				prev.rchild = cur
				cur = cur.lchild
			} else {
				l.PushBack(cur.data)
				prev.rchild = nil
				cur = cur.rchild
			}
		}
	}
	return l
}
// 前序遍历 morris
func (tree *BSTree) PerOrderTraversal() *list.List {
	l := list.New()
	cur := tree.root
	for cur != nil {
		// 左节点为空直接输出
		if cur.lchild == nil {
			l.PushBack(cur.data)
			cur = cur.rchild
		} else {
			// find predecessor
			prev := cur.lchild
			for prev.rchild != nil && prev.rchild != cur {
				prev = prev.rchild
			}
			if prev.rchild == nil {
				l.PushBack(cur.data)
				prev.rchild = cur
				cur = cur.lchild
			} else {
				prev.rchild = nil
				cur = cur.rchild
			}
		}
	}
	return l
}
// 后续遍历 morris
func (tree *BSTree) PostOrderTraversal() *list.List {
	l := list.New()
	assistNode := NewBSTNode(0)
	assistNode.lchild = tree.root
	cur := assistNode
	for cur != nil {
		if cur.lchild == nil {
			cur = cur.rchild
		} else {
			prev := cur.lchild
			for prev.rchild != nil && prev.rchild != cur {
				prev = prev.rchild
			}
			if prev.rchild == nil {
				prev.rchild = cur
				cur = cur.lchild
			} else {
				prev.rchild = nil
				getNodeIntoList(cur.lchild, prev, l)
				cur = cur.rchild
			}
		}
	}
	return l
}
func getReverseNodes(from *BSTNode, to *BSTNode) {
	if from == to {
		return
	}
	x := from
	y := from.rchild
	for true {
		z := y.rchild
		y.rchild = x
		x = y
		y = z
		if x == to {
			break
		}
	}
}
func getNodeIntoList(from *BSTNode, to *BSTNode, l *list.List) {
	getReverseNodes(from, to)
	for true {
		l.PushBack(to.data)
		if to == from {
			break
		}
		to = to.rchild
	}
	getReverseNodes(to, from)
}