二叉树

  1package tree
  2
  3import (
  4	"bytes"
  5	"container/list"
  6	"fmt"
  7	"strconv"
  8)
  9
 10type Node struct {
 11	Data  int
 12	Left  *Node
 13	Right *Node
 14}
 15
 16type BinaryTree struct {
 17	Root *Node // 根节点
 18	Size int   // 树中节点的个数
 19}
 20
 21// 新建一个二叉树
 22func NewBinaryTree() *BinaryTree {
 23	return &BinaryTree{
 24		Root: nil,
 25		Size: 0,
 26	}
 27}
 28
 29// 获取二叉树大小
 30func (bst *BinaryTree) GetSize() int {
 31	return bst.Size
 32}
 33
 34// 判断是否为空
 35func (bst *BinaryTree) IsEmpty() bool {
 36	return bst.Size == 0
 37}
 38
 39// 根节点插入
 40func (bst *BinaryTree) Add(data int) {
 41	bst.Root = bst.add(bst.Root, data)
 42}
 43
 44// 插入节点
 45func (bst *BinaryTree) add(n *Node, data int) *Node {
 46	if n == nil {
 47		bst.Size++
 48		return &Node{Data: data, Left: nil, Right: nil}
 49	}
 50	if data < n.Data {
 51		n.Left = bst.add(n.Left, data) //比我小，左边
 52	} else if data > n.Data {
 53		n.Right = bst.add(n.Right, data)
 54	}
 55	return n
 56}
 57
 58// 二分查找 查找节点
 59func (bst *BinaryTree) isIn(n *Node, data int) bool {
 60	if n == nil {
 61		return false
 62	}
 63	if data == n.Data {
 64		return true
 65	}
 66	if data < n.Data {
 67		return bst.isIn(n.Left, data)
 68	}
 69	return bst.isIn(n.Right, data)
 70}
 71
 72// 最大元素
 73func (bsg *BinaryTree) FindMax() int {
 74	if bsg.Root == nil {
 75		panic("根节点不存在")
 76	}
 77	return bsg.findMax(bsg.Root).Data
 78}
 79
 80// 最大元素
 81func (bst *BinaryTree) findMax(n *Node) *Node {
 82	if n.Right == nil {
 83		return n
 84	}
 85	return bst.findMax(n.Right)
 86}
 87
 88// 最小元素
 89func (bsg *BinaryTree) FindMin() int {
 90	if bsg.Root == nil {
 91		panic("根节点不存在")
 92	}
 93	return bsg.findMin(bsg.Root).Data
 94}
 95
 96// 最小元素
 97func (bst *BinaryTree) findMin(n *Node) *Node {
 98	if n.Left == nil {
 99		return n
100	}
101	return bst.findMin(n.Left)
102}
103
104// 前序遍历
105func (bst *BinaryTree) PreOrder() {
106	bst.preOrder(bst.Root)
107}
108func (bst *BinaryTree) preOrder(n *Node) {
109	if n == nil {
110		return
111	}
112	fmt.Println(n.Data)
113	bst.preOrder(n.Left)
114	bst.preOrder(n.Right)
115}
116
117// 中序遍历
118func (bst *BinaryTree) InOrder() {
119	bst.inOrder(bst.Root)
120}
121func (bst *BinaryTree) inOrder(n *Node) {
122	if n == nil {
123		return
124	}
125	bst.preOrder(n.Left)
126	fmt.Println(n.Data)
127	bst.preOrder(n.Right)
128}
129
130// 后序遍历
131func (bst *BinaryTree) PostOrder() {
132	bst.postOrder(bst.Root)
133}
134func (bst *BinaryTree) postOrder(n *Node) {
135	if n == nil {
136		return
137	}
138	bst.preOrder(n.Left)
139	bst.preOrder(n.Right)
140	fmt.Println(n.Data)
141}
142
143// 打印数形 中序遍历
144func (bst *BinaryTree) String() string {
145	var buffer bytes.Buffer                     //保存字符串
146	bst.GenerateBSTstring(bst.Root, 0, &buffer) //调用函数实现遍历
147	return buffer.String()
148}
149
150func (bst *BinaryTree) GenerateBSTstring(node *Node, depth int, buffer *bytes.Buffer) {
151	if node == nil {
152		//buffer.WriteString(bst.GenerateDepthstring(depth)+"nil\n")//空节点
153		return
154	}
155	//写入字符串，保存树的深度
156	bst.GenerateBSTstring(node.Left, depth+1, buffer)
157	buffer.WriteString(bst.GenerateDepthstring(depth) + strconv.Itoa(node.Data) + "\n")
158	bst.GenerateBSTstring(node.Right, depth+1, buffer)
159}
160
161func (bst *BinaryTree) GenerateDepthstring(depth int) string {
162	var buffer bytes.Buffer //保存字符串
163	for i := 0; i < depth; i++ {
164		buffer.WriteString("--") //深度为0，1-- 2----
165	}
166	return buffer.String()
167}
168
169// 移除最大节点
170func (bst *BinaryTree) RemoveMax() int {
171	max := bst.FindMax()
172	bst.Root = bst.removeMax(bst.Root)
173	return max
174}
175func (bst *BinaryTree) removeMax(n *Node) *Node {
176	if n.Right == nil {
177		leftNode := n.Left
178		bst.Size--
179		return leftNode
180	}
181	n.Right = bst.removeMax(n.Right)
182	return n
183}
184
185// 移除最小节点
186func (bst *BinaryTree) RemoveMin() int {
187	min := bst.FindMin()
188	bst.Root = bst.removeMin(bst.Root)
189	return min
190}
191func (bst *BinaryTree) removeMin(n *Node) *Node {
192	if n.Left == nil {
193		rightNode := n.Right
194		bst.Size--
195		return rightNode
196	}
197	n.Left = bst.removeMin(n.Left)
198	return n
199}
200
201// 移除节点
202func (bst *BinaryTree) Remove(data int) {
203	bst.Root = bst.remove(bst.Root, data) //删除数据
204}
205
206func (bst *BinaryTree) remove(n *Node, data int) *Node {
207	if n == nil {
208		return nil //节点为空，不需要干活
209	}
210	if data < n.Data {
211		n.Left = bst.remove(n.Left, data) //递归左边
212		return n
213	} else if data > n.Data {
214		n.Right = bst.remove(n.Right, data) //递归右边
215		return n
216	} else {
217		//处理左边为空
218		if n.Left == nil {
219			rightNode := n.Right //备份右边节点
220			n.Right = nil
221			bst.Size-- //删除
222			return rightNode
223		}
224		//处理右边为空
225		if n.Right == nil {
226			leftNode := n.Left //备份右边节点
227			n.Left = nil       //处理节点返回
228			bst.Size--         //删除
229			return leftNode
230		}
231		//左右节点都不为空
232		oknode := bst.findMin(n.Right)        //找出比我小的节点顶替我， 右边的最小 也是比自己大的。
233		oknode.Right = bst.removeMin(n.Right) // 移除  右边 自身这个小的
234		oknode.Left = n.Left                  // 小节点左边，连接原来的左边。
235		n.Left = nil                          //删除的清空
236		n.Right = nil
237		return oknode //实现删除
238
239	}
240}
241
242// 非递归中序
243func (bst *BinaryTree) InOrderNoRecursion() []int {
244	mybst := bst.Root     //备份二叉树
245	mystack := list.New() //生成一个栈
246	res := make([]int, 0) //生成数组，容纳中序的数据
247	for mybst != nil || mystack.Len() != 0 {
248		for mybst != nil {
249			mystack.PushBack(mybst) //首先左边压入栈中
250			mybst = mybst.Left
251		}
252		if mystack.Len() != 0 {
253			v := mystack.Back()           //挨个取出节点
254			mybst = v.Value.(*Node)       //实例化
255			res = append(res, mybst.Data) //压入数据
256			mybst = mybst.Right           //追加
257			mystack.Remove(v)             //删除
258		}
259	}
260	return res
261}
262
263// 非递归前序
264func (bst *BinaryTree) PreOrderNoRecursion() []int {
265	mybst := bst.Root     //备份二叉树
266	mystack := list.New() //生成一个栈
267	res := make([]int, 0) //生成数组，容纳中序的数据
268	for mybst != nil || mystack.Len() != 0 {
269		for mybst != nil {
270			res = append(res, mybst.Data) //压入数据
271			mystack.PushBack(mybst)       //首先左边压入栈中
272			mybst = mybst.Left
273		}
274		if mystack.Len() != 0 {
275			v := mystack.Back()     //挨个取出节点
276			mybst = v.Value.(*Node) //实例化
277			//res=append(res,mybst.Data)//压入数据
278			mybst = mybst.Right //追加
279			mystack.Remove(v)   //删除
280		}
281	}
282	return res
283}
284
285// 后序非递归
286func (bst *BinaryTree) PostOrderNoRecursion() []int {
287	mybst := bst.Root     //备份二叉树
288	mystack := list.New() //生成一个栈
289	res := make([]int, 0) //生成数组，容纳中序的数据
290	var PreVisited *Node  //提前访问的节点 , 后续 要记录下 之前的节点， 不然无法反回去了
291
292	for mybst != nil || mystack.Len() != 0 {
293		for mybst != nil {
294			mystack.PushBack(mybst) //首先左边压入栈中
295			mybst = mybst.Left      //左边
296		}
297		v := mystack.Back() //取出节点
298		top := v.Value.(*Node)
299		// 循环到了尽头.
300		if (top.Left == nil && top.Right == nil) || (top.Right == nil && PreVisited == top.Left) || (PreVisited == top.Right) {
301			res = append(res, top.Data) //压入数据
302			PreVisited = top            //记录上一个节点
303			mystack.Remove(v)           //处理完了在栈中删除
304		} else {
305			mybst = top.Right //右边循环
306		}
307	}
308	return res
309}
310
311func (bst *BinaryTree) Levelshow() {
312	bst.levelshow(bst.Root)
313}
314
315// 广度遍历
316func (bst *BinaryTree) levelshow(n *Node) {
317	myqueue := list.New() //新建一个list模拟队列
318	myqueue.PushBack(n)   //后面压入数据
319	for myqueue.Len() > 0 {
320		left := myqueue.Front() //前面取出数据
321		right := left.Value
322		myqueue.Remove(left) //删除
323		if v, ok := right.(*Node); ok && v != nil {
324			fmt.Println(v.Data) //打印数据
325			myqueue.PushBack(v.Left)
326			myqueue.PushBack(v.Right)
327		}
328	}
329}
330
331// 深度遍历
332func (bst *BinaryTree) Stackshow(n *Node) {
333	myqueue := list.New() //新建一个list模拟队列
334	myqueue.PushBack(n)   //后面压入数据
335	for myqueue.Len() > 0 {
336		left := myqueue.Back() //前面取出数据 ,此时是栈
337		right := left.Value
338		myqueue.Remove(left) //删除
339		if v, ok := right.(*Node); ok && v != nil {
340			fmt.Println(v.Data) //打印数据
341			myqueue.PushBack(v.Left)
342			myqueue.PushBack(v.Right)
343		}
344	}
345}
346
347// 最小公共祖先
348func (bst *BinaryTree) FindlowerstAncestor(root *Node, nodea *Node, nodeb *Node) *Node {
349	if root == nil {
350		return nil
351	}
352	if root == nodea || root == nodeb {
353		return root //有一个节点是根节点，
354	}
355	left := bst.FindlowerstAncestor(root.Left, nodea, nodeb)   //递归查找
356	right := bst.FindlowerstAncestor(root.Right, nodea, nodeb) //递归查找
357	if left != nil && right != nil {
358		return root
359	}
360	if left != nil {
361		return left
362	} else {
363		return right
364	}
365}
366
367// 递归二叉树深度
368func (bst *BinaryTree) GetDepth(root *Node) int {
369	if root == nil {
370		return 0
371	}
372	if root.Right == nil && root.Left == nil {
373		return 1
374	}
375	lengthleft := bst.GetDepth(root.Left)
376	rightlength := bst.GetDepth(root.Right)
377	if lengthleft > rightlength {
378		return lengthleft + 1
379	} else {
380		return rightlength + 1
381	}
382}

 1package tree
 2
 3import (
 4	"fmt"
 5	"testing"
 6)
 7
 8func TestBinaryTree(t *testing.T) {
 9
10	/*
11			    4(node1)
12			2(node2)                   6(node3)
13		1(node4)	  3(node5)      5(node6)  7 (node7)
14			                      17(node8)
15	*/
16	bst := NewBinaryTree()
17	node1 := &Node{4, nil, nil}
18	node2 := &Node{2, nil, nil}
19	node3 := &Node{6, nil, nil}
20	node4 := &Node{1, nil, nil}
21	node5 := &Node{3, nil, nil}
22	node6 := &Node{5, nil, nil}
23	node7 := &Node{7, nil, nil}
24	//node8 := &Node{17, nil, nil}
25	bst.Root = node1
26	node1.Left = node2
27	node1.Right = node3
28	node2.Left = node4
29	node2.Right = node5
30	node3.Left = node6
31	node3.Right = node7
32	//node6.Left = node8
33	bst.Size = 7
34
35	fmt.Println(bst.FindMax(), "max")
36	fmt.Println(bst.FindMin(), "min")
37	fmt.Println("中序----------------------")
38	bst.InOrder()
39	fmt.Println("前序----------------------")
40	bst.PreOrder()
41	fmt.Println("后序----------------------")
42	bst.PostOrder()
43	fmt.Println("last ----------------------")
44	fmt.Println(bst)
45	//// 移除最大节点
46	//bst.RemoveMax()
47	//fmt.Println(bst)
48	//// 移除最小节点
49	//bst.RemoveMin()
50	//fmt.Println(bst)
51	// 广度遍历
52	fmt.Println("广度遍历----------------------")
53	bst.Levelshow()
54	// 深度遍历
55	fmt.Println("深度遍历----------------------")
56	bst.Stackshow(bst.Root)
57	// 最小公共祖先
58	fmt.Println(bst.FindlowerstAncestor(bst.Root, node2, node6).Data)
59
60}