建议大家使用FireFox、Opera、Safri、IE8+等主流浏览器访问本站,否则可能会出现不兼容等问题!

二叉树Morris遍历算法golang

golang 凶恶的方块 2157次浏览 已收录 0个评论

前言:

自己写的不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)
}


方块网络 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明二叉树Morris遍历算法golang
喜欢 (2)or分享 (0)
avatar
发表我的评论
取消评论
表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址