树型结构的基础概念和操作

字数统计: 1.6k   |   阅读时长≈ 7 分钟

这篇小笔记主要记录了树型结构的各个节点学术名称，树的种类，树的前中后三序遍历以及树的插入删除查找。

个人感觉比较难的是树节点的删除操作，文字描述比较少。代码比较直观的描述

基本定义

二叉树（Binary tree）：二叉树特点是每个结点最多只能有两棵子树，且
有左右之分，一个连通的无环图。

名称 定义
根节点 一颗树最上面的节点
父节点 如果一个节点下面有多个节点，那他就是下面子节点的父节点
子节点 如果节点上面还有节点，那它就是上层父节点的子节点
叶子节点 没有子节点的节点
兄弟节点 多个节点有同一父节
节点高度 节点到叶子节点的最长路径
树的深度 根节点到这个节点所经历的边个数
层 根节点到尾节点的数量

ps: 高度和深度可以依靠记忆去联想，高度是自下而上的，深度是自上而下的。

树的分类

类型 定义
满二叉树 叶子节点都在同一层，除叶子节点都有左右节点
完全二叉树 除叶子节点以外的左节点都必须有值
平衡二叉树 AVL树，它是一颗空树或左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树
二叉搜索树 左节点数据小于 父节点 右节点大于父节点
红黑树 自平衡二叉查找树

基础算法

树的前/中/后 遍历 && 计算深度

遍历二叉树主要是依靠递归公式，代码本身并没有什么特别之处理解就好

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111

package main

import (
	"fmt"
	"math"
)

type treeNode struct {
	name  string
	left  *treeNode
	right *treeNode 
}

func main()  {
	node := treeNode{
		name:  "A",
		left:  nil,
		right: nil,
	}

	node.addLeftNode("B")
	node.left.addLeftNode("D")
	node.left.addRightNode("E")

	node.addRightNode("C")
	node.right.addRightNode("G")
	node.right.addLeftNode("F")

	fmt.Println("-------前序遍历--------")
	node.preOrder()
	fmt.Println("-------中序遍历--------")
	node.inOrder()
	fmt.Println("-------后序遍历--------")
	node.postOrder()
	fmt.Println("-------计算深度--------")
	fmt.Println(maxDepth(&node))
}

//前序遍历是指，对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。
// Print r -> preOrder(left) -> preOrder(right)

func (node *treeNode) preOrder() {
	if node == nil {
		return
	}

	fmt.Println(node.name)

	node.left.preOrder()
	node.right.preOrder()

}

// max(left) max(right)
func maxDepth(root *treeNode) int {

	if root == nil {
		return 0
	}

	return  int(math.Max(float64(maxDepth(root.right)), float64(maxDepth(root.left))) + 1)

}

//中序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它本身，最后打印它的右子树。
// print inOrder(r.left) ->  print r.name -> print inOrder(r.right)
func (node *treeNode) inOrder() {

	if node == nil {
		return
	}

	node.left.inOrder()
	fmt.Println(node.name)
	node.right.inOrder()

}


//后序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印这个节点本身。
// print postOrder(left) -> postOrder(right)  -> print r.name
func (node *treeNode) postOrder() {
	if node == nil {
		return
	}

	node.left.postOrder()
	node.right.postOrder()
	fmt.Println(node.name)
}


func (node *treeNode) addLeftNode (value string){
	leftNode := treeNode{
		name:  fmt.Sprintf("左边->%s", value),
		left:  nil,
		right: nil,
	}
	node.left = &leftNode
}


func (node *treeNode) addRightNode (value string) {
	reightNode := treeNode{
		name:  fmt.Sprintf("右边->%s", value),
		left:  nil,
		right: nil,
	}
	node.right = &reightNode
}

##二叉搜索树

二叉搜索树是一种特殊的树结构,定义比较简单 比父节点小的值放右节点，比父节点大的放右边。用中序遍历的时候就是一个从小到大的有序数列了。

ps: 二叉搜索树在遇见 连续有规律的排序时会退化成单向链表

二叉搜索树

  • 写入 ： 注意比父节点大放右边小放左边
  • 查找 ： 和二分查和写入的找思想相同
  • 删除 ： 删除分如下3种方案
情况 方案
删除值下面没有子节点 直接删除
删除值下面有一个子节点 父节点指向这个值的下个节点
删除值下面有子节点 把左子节点最大的值放当前位置或者把右子节点最小值放最大位置 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
package main

import "fmt"

type treeNode struct {
	data int
	leftNode,rightNode *treeNode
}

func main()  {

	numbers := []int{8, 3, 10, 1, 6, 14, 4, 7, 13, 200, 100, 99, 201}
	node := treeNode{}


	for i:=0 ; i < len(numbers); i++ {
		insert(&node, numbers[i])
	}


	node.rightNode.inOrder()

	fmt.Println(search(&node, 201))

	node.delete(4)


	node.rightNode.inOrder()

}

func insert(node *treeNode,data int) {
	if (node.data > data) {

		if(node.leftNode == nil) {

			node.leftNode = &treeNode{
				data:      data,
				leftNode:  nil,
				rightNode: nil,
			}

		} else  {
			insert(node.leftNode, data)
		}

	} else {
		if (node.rightNode == nil) {
			node.rightNode = &treeNode{
				data:      data,
				leftNode:  nil,
				rightNode: nil,
			}
		} else {
			insert(node.rightNode, data)
		}
	}
}

func search(node *treeNode, data int) bool{

	p := node

	for p != nil {

		if p.data > data {
			p = p.leftNode
		} else if (p.data < data)  {
			p = p.rightNode
		} else {
			return true
		}
	}

	return  false
}

func (node *treeNode) delete (data int) {
	p,pp := node,node// PP：父节点  p 当前节点

	for  p != nil && p.data != data {
		pp = p
		if p.data > data {
			p = p.leftNode
		} else {
			p = p.rightNode
		}
	}

	if pp == nil {
		return
	}

	//删除值下面没有子节点|直接删除
	if p.leftNode == nil && p.rightNode == nil{
		pp.leftNode =nil
		pp.rightNode =nil
	} else if  p.leftNode != nil && p.rightNode != nil {
		//TODO 回来再琢磨下
	} else if p.leftNode != nil || p.rightNode !=nil {

		if p.leftNode != nil {
			p = p.leftNode
		} else {
			p = p.rightNode
		}

		if pp.rightNode != nil && pp.rightNode.data == data {
			pp.rightNode = p
		} else {
			pp.leftNode = p
		}


	}
		node =  pp


}

func (node *treeNode) addLeftNode (value int){
	left := treeNode{
		data:      value,
		leftNode:  nil,
		rightNode: nil,
	}
	node.leftNode = &left
}

func (node *treeNode) addRightNode (value int){
	right := treeNode{
		data:      value,
		leftNode:  nil,
		rightNode: nil,
	}
	node.rightNode = &right
}

func (node *treeNode) inOrder() {

	if node == nil {
		return
	}


	node.leftNode.inOrder()
	fmt.Println(node.data)
	node.rightNode.inOrder()

}

插图工具 ： https://app.diagrams.net/
插图下载 ： https://github.com/zhangjunjie6b/diagramsResource

参考 ：

https://time.geekbang.org/column/article/67856?utm_source=pinpaizhuanqu&utm_medium=geektime&utm_campaign=guanwang&utm_term=guanwang&utm_content=0511

https://baike.baidu.com/item/%E4%BA%8C%E5%8F%89%E6%A0%91/1602879?fr=aladdin

https://zh.wikipedia.org/wiki/%E4%BA%8C%E5%8F%89%E6%A0%91#%E5%9C%96%E8%AB%96%E4%B8%AD%E7%9A%84%E5%AE%9A%E7%BE%A9

  • 版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！

请我喝杯咖啡吧~