树的定义
一棵树（tree）是一些节点的集合。这个集合可以是空集；若不是空集，则树由称作根（root）的节点r以及0个或多个非空的（子）树T1，T2,.....Tk组成，这些子树中每一棵的根都被来自根r的一条有有向的边（edge）所连结。
一般的树.png
一棵树.png
树的结构体：
type TreeNode struct {
element interface{},
firstChild *TreeNode, // 儿子
nextSibling *TreeNode, // 兄弟}二叉树
二叉树是一棵树，其中每个节点都不能有多于两个的儿子。
二叉树的结构体：
// BinaryNode 二叉树节点type BinaryNode struct {
element int
leftChildNode *BinaryNode
rightChildNode *BinaryNode
}// BinaryTree 二叉书type BinaryTree struct {
root *BinaryNode
}// inorderTraversal 中序遍历func inorderTraversal(root *BinaryNode) { if root == nil { return
}
inorderTraversal(root.leftChildNode)
fmt.Println(root.element)
inorderTraversal(root.rightChildNode)
}// prefixraversal 前序遍历func prefixraversal(root *BinaryNode) { if root == nil { return
}
fmt.Println(root.element)
prefixraversal(root.leftChildNode)
prefixraversal(root.rightChildNode)
}// prefixravel 前序遍历非递归func prefixravel(root *BinaryNode) { if root == nil { return
}
p := root stack := new(Stack) stack.push(p) for { if len(stack.Elements) == 0 { break
}
p = stack.pop() if p.rightChildNode != nil { stack.push(p.rightChildNode)
} if p.leftChildNode != nil { stack.push(p.leftChildNode)
}
}
}// inordertravel 中序遍历func inordertravel(root *BinaryNode) { if root == nil { return
}
p := root stack := new(Stack) for { for { if p != nil { stack.push(p)
p = p.leftChildNode
} else { break
}
}
p = stack.pop() if p.rightChildNode != nil {
p = p.rightChildNode
} else {
p = nil
} if len(stack.Elements) == 0 { break
}
}
}// postOrder 后序遍历func postOrder(root *BinaryNode) { if root == nil { return
}
p := root stack := new(Stack) for { for { if p != nil { stack.push(p)
p = p.leftChildNode
} else { break
}
}
p = stack.pop() if len(stack.Elements) == 0 { break
} //这里需要判断一下，当前p是否为栈顶的左子树，如果是的话那么还需要先访问右子树才能访问根节点
//如果已经是不是左子树的话，那么说明左右子书都已经访问完毕，可以访问根节点了，所以讲p复制为NULL
//取根节点
if p == stack.peek().leftChildNode {
p = stack.peek().rightChildNode
} else {
p = nil
}
}
}
作者：one_zheng
链接：https://www.jianshu.com/p/d5addaaf3959