1.1 基本术语
树(Tree)是n(n>=0)个结点的有限集。n=0时称为空树。在任意一棵非空树中：（1）有且仅有一个特定的称为根（Root）的结点；（2）当n>1时，其余结点可以分为互不相交的有限集T1、T2、……Tm，其中每一个集合本身又是一棵树，并且称为根的子树（SubTree）
tree
基本术语
-
节点：
使用树结构存储的每一个数据元素都被称为结点，例如节点A,B,C,D，E,F,G,H,I,J,K,L,M
-
父节点：也叫双亲节点，若一个节点含有子节点，则这个节点称为其子节点的父节点， 例如 节点B，C，D 的父节点是A， B又是E,F 的父节点
-
兄弟节点：拥有相同的父节点的节点，例如A是B，C，D的父节点，所以B,C,D 是彼此的兄弟节点
-
子节点：又称孩子节点， 即与节点相连的下属第一层的节点，例如，B，C，D是A节点的子节点，E，F是B的子节点
-
子孙节点/ 祖先节点 ： 以某节点为根的子树中任一节点都称为该节点的子孙， 例如，B，C，D，E，F，G，H，I，J，K，L，M 都可通过A节点通过路径相连，所以他们都是A的子孙节点， 节点的子节点一定也是子孙节点
-
叶子节点：如果结点没有任何子结点，那么此结点称为叶子结点（叶结点）。例如图中，结点 K、L、F、G、M、I、J 都是这棵树的叶子结点
-
节点的度：节点含有子节点的数量， 例如节点A的度为3， 节点B的度为2
-
节点的层次：也叫节点的深度从一棵树的树根开始，树根所在层为第一层，根的孩子结点所在的层为第二层，依次类推。。。。 A的层为1， B，C，D的层为2.。。。
-
堂兄弟节点：位于同一层的，并且父节点之间是兄弟结点的结点互为堂兄弟结点，上图中，E，G，H为堂兄弟结点，F和G，H也是堂兄弟结点，他们的父节点是兄弟结点
-
树的深度：与树的度对应于结点的度一样，树的深度也是选取结点中的最大深度（或最大层次），上图中的树的深度为4
-
树的度：选取所有结点中最大的度，就是树的度，例如上述树中节点最大的度为3， 所以树的度为3
1.2 二叉树
树中的每一个节点最多有两个子节点的树，或者说是树中的每一个节点的度最大为2 。 二叉树的子节点分别称为左节点和右节点
二叉树
-
二叉树的深度优先遍历：
前序遍历：根结点 ---> 左子树 ---> 右子树 (1,2,4,5,3,6)中序遍历：左子树---> 根结点 ---> 右子树. (4,2,5,1,6,3)
后序遍历：左子树 ---> 右子树 ---> 根结点 (4,5,2,6,3,1)
-
二叉树的层次遍历： 按层从左到右依次遍历(1,2,3,4,5,6)
二叉树具有以下几个性质：
- 二叉树中，第 i 层最多有 2i-1 个结点。
- 如果二叉树的深度为 K，那么此二叉树最多有 2K-1 个结点。
- 二叉树中，终端结点数（叶子结点数）为 n0，度为 2 的结点数为 n2，则 n0=n2+1
1.2.1 满二叉树
所有的非叶子节点都存在左右子节点， 并且所有的叶子节点都在最后一层
image.png
满二叉树除了满足普通二叉树的性质，还具有以下性质：
- 满二叉树中第 i 层的节点数为 2n-1 个。
- 深度为 k 的满二叉树必有 2k-1 个节点 ，叶子数为 2k-1。
- 满二叉树中不存在度为 1 的节点，每一个分支点中都两棵深度相同的子树，且叶子节点都在最底层。
- 具有 n 个节点的满二叉树的深度为 log2(n+1)。
1.2.2 完全二叉树
如果二叉树中除去最后一层节点为满二叉树，且最后一层的结点依次从左到右分布，则此二叉树被称为完全二叉树。 满二叉树一定是完全二叉树
image.png
完全二叉树除了具有普通二叉树的性质，它自身也具有一些独特的性质，比如说，n 个结点的完全二叉树的深度为 ⌊log2 n⌋+1。
⌊log2n⌋ 表示取小于 log2n 的最大整数。例如，⌊log24⌋ = 2，而 ⌊log25⌋ 结果也是 2。
对于任意一个完全二叉树来说，如果将含有的结点按照层次从左到右依次标号（如图 3a)），对于任意一个结点 i ，完全二叉树还有以下几个结论成立：
- 当 i>1 时，父亲结点为结点 [i/2] 。（i=1 时，表示的是根结点，无父亲结点）
- 如果 2i>n（总结点的个数） ，则结点 i 肯定没有左孩子（为叶子结点）；否则其左孩子是结点 2i 。
- 如果 2i+1>n ，则结点 i 肯定没有右孩子；否则右孩子是结点 2i+1
1.2.3 二叉搜索树（binary search tree）
也叫二叉排序树，指除了叶子节点外，左子节点的值要小于当前节点，右子节点的值要大于当前节点
# golang 语言定义bst 树，
type BST struct {
root *Node // 根节点
size int // 节点个数
}
type Node struct {
val int
left *Node // 左节点
right *Node // 右节点
}
- 添加元素
func (bst *BST) AddElement(val int) {
bst.root=bst.addElement(bst.root,val)
}
func (bst *BST)addElement(node *Node, val int) *Node {
if node == nil {
bst.size++
return &Node{
val: val,
}
}
if node.val > val {
// 插入左子树
node.left=bst.addElement(node.left, val)
}else if node.val < val {
// 插入右树
node.right=bst.addElement(node.right,val)
} else {
fmt.Println(node.val,val)
panic("bst tree find equal nums")
}
return node
}
func main(){
bst:=new(BST)
bst.AddElement(3)
bst.AddElement(10)
bst.AddElement(1)
bst.AddElement(7)
bst.AddElement(5)
bst.AddElement(9)
bst.AddElement(12)
fmt.Println(bst.size)
}
- 查找元素
func (bst *BST) Search(val int) *Node {
return search(bst.root, val)
}
func search(node *Node, val int) *Node {
// 未找到
if node == nil {
return nil
}
// 找到
if node.val == val {
return node
}
// 右子树查找
if node.val < val {
return search(node.right, val)
} else {
// 左子树查找
return search(node.left, val)
}
}
func main(){
bst:=new(BST)
bst.AddElement(3)
bst.AddElement(10)
bst.AddElement(1)
bst.AddElement(7)
bst.AddElement(5)
bst.AddElement(9)
bst.AddElement(12)
fmt.Println(bst.Search(1))
}
- 查找父节点
func (bst *BST) SearchParent(val int) *Node {
return searchParent(bst.root, val)
}
func searchParent(node *Node, val int) *Node {
// 未找到
if node == nil {
return nil
}
left := node.left
right := node.right
// 找到父节点
if (left != nil && left.val == val) || (right != nil && right.val == val) {
return node
}
// 未找到,从右子树找
if left != nil && left.val < val {
return searchParent(right, val)
}
// 未找到,从左子树找
if right != nil && right.val > val {
return searchParent(left, val)
}
return nil
}
- 遍历
// 前序遍历
func preOrder(node *Node) {
if node == nil {
return
}
fmt.Printf("%d\t ",node.val)
preOrder(node.left)
preOrder(node.right)
}
// 中序遍历
func midOrder(node *Node) {
if node == nil {
return
}
midOrder(node.left)
fmt.Printf("%d\t ",node.val)
midOrder(node.right)
}
// 后序遍历
func backOrder(node *Node) {
if node == nil {
return
}
backOrder(node.left)
backOrder(node.right)
fmt.Printf("%d\t ",node.val)
}
// 广度优先级遍历，即逐层遍历
func levelOrder(node *Node){
queue:=list.New()
if node==nil{
return
}
queue.PushBack(node)
for queue.Len()!=0{
e:=queue.Front()
n:=e.Value.(*Node)
fmt.Printf("%d\t ",n.val)
queue.Remove(e)
if n.left!=nil{
queue.PushBack(n.left)
}
if n.right!=nil{
queue.PushBack(n.right)
}
}
}
func main(){
bst:=new(BST)
bst.AddElement(7)
bst.AddElement(3)
bst.AddElement(10)
bst.AddElement(1)
bst.AddElement(5)
bst.AddElement(9)
bst.AddElement(12)
bst.Traverse(preOrder)
fmt.Println("前序")
bst.Traverse(midOrder)
fmt.Println("中序")
bst.Traverse(backOrder)
fmt.Println("后序")
bst.Traverse(levelOrder)
fmt.Println("逐层")
- 删除节点
节点处于不同的位置，删除的逻辑也不同- 删除的节点是叶子节点，直接删除即可
- 删除的节点只有一个子节点，删除节点，并将唯一的子树节点上移
- 删除的节点有左右子节点，删除节点，取该节点的左子树中最大的节点代替该节点，或者取右子树的最小的节点代替该节点
func (bst *BST) Remove(val int) {
remove(bst.root, val)
}
func remove(node *Node, val int) *Node {
if node == nil {
return nil
}
// 遍历元素
if node.val > val {
// 遍历左子树
node.left = remove(node.left, val)
return node
} else if node.val < val {
// 遍历右子树
node.right = remove(node.right, val)
return node
} else {
//找到对应的元素，此时对应是叶子节点的，不做单独处理，处理逻辑可用只有一个子节点的逻辑
if node.left == nil {
// 删除节点只有右孩子节点
right := node.right
node.right = nil
return right
}
if node.right == nil {
// 删除的节点只有左孩子
left := node.left
node.left = nil
return left
}
// 有左右子节点的， 这边采用找右子树的最小节点来代替
minNode := minNode(node.right)
// 将新的节点待替代删除的节点
minNode.right = remove(node.right, minNode.val)
minNode.left = node.left
node.left = nil
node.right = nil
return minNode
}
}
网友评论