怎么样制作个网站,沂南网站开发,apache 搭建多个网站,discuz 转 wordpress二叉树
前言
完全二叉树 最底层节点按顺序从左到右排列。 满二叉树 一颗二叉树只有0度和2度的节点。 二叉搜索树 左子树上的所有节点的值均小于根节点的值。右子树上的所有节点的值均大于根节点的值。 平衡二叉搜索树 左右两个子树的高度差的绝对值不超过1 。
二叉树的存储…二叉树
前言
完全二叉树 最底层节点按顺序从左到右排列。 满二叉树 一颗二叉树只有0度和2度的节点。 二叉搜索树 左子树上的所有节点的值均小于根节点的值。右子树上的所有节点的值均大于根节点的值。 平衡二叉搜索树 左右两个子树的高度差的绝对值不超过1 。
二叉树的存储方式有链式存储和数组存储。线索二叉树、红黑树等
1、链表存储方式
type TreeNode struct {Val intLeft *TreeNodeRight *TreeNode
}func NewTreeNode(val int) *TreeNode {return TreeNode{Val: val}
}2、数组存储方式 // 完全二叉树 1// / \// 2 3// / \ / \// 4 5 6 7// 以下为前中后序遍历,以下例子也是这个结果// 1245367 // 4251637// 4526731左子树2 * i 1
右子树2 * i 2
i是数组的下标元素值为arr[ 2 * i 1 ]或arr[ 2 * i 2 ]
接下来将讲解二叉树的几种遍历方式我全篇使用链式存储结构。
一、深度优先遍历
1、前序遍历
1、递归遍历
// 前序遍历根 - 左 - 右
func preorderTraversal(root *TreeNode) {if root ! nil {fmt.Println(root.Val) // 访问根节点preorderTraversal(root.Left) // 递归遍历左子树preorderTraversal(root.Right) // 递归遍历右子树}
}2、迭代遍历
深度优先遍历的递归版本都是简洁易读的相较于迭代版本更直观。迭代版本使用到了一种数据结构栈以下我使用的栈是自己封装的库函数如果有感兴趣的朋友可以看shard库介绍写shard库主要还是由于Golang没提供更多的数据结构模版。
// 前序遍历根 - 左 - 右迭代实现
func preorderTraversal(root *TreeNode) {if root nil {return}// 栈存放的全是 *TreeNodes : shard.NewStackArray[*TreeNode]()s.Push(root)for s.Len() 0 {// 栈顶弹出并删除node, _ : s.Pop()fmt.Println(node.Val)// 先压右子节点再压左子节点因为栈是后进先出LIFOif node.Right ! nil {s.Push(node.Right)}if node.Left ! nil {s.Push(node.Left)}}
}2、中序遍历
1、递归遍历
// 中序遍历左 - 根 - 右
func inorderTraversal(root *TreeNode) {if root ! nil {inorderTraversal(root.Left) // 递归遍历左子树fmt.Println(root.Val) // 访问根节点inorderTraversal(root.Right) // 递归遍历右子树}
}2、迭代遍历
// 中序遍历左 - 根 - 右迭代实现
func inorderTraversal(root *TreeNode) {if root nil {return}// 栈存放的全是 *TreeNodes : shard.NewStackArray[*TreeNode]()cur : rootfor cur ! nil || !s.IsEmpty() {for cur ! nil {s.Push(cur)cur cur.Left}node, _ : s.Pop()fmt.Println(node.Val)cur node.Right}
}3、后序遍历
1、递归遍历
// 后序遍历左 - 右 - 根
func postorderTraversal(root *TreeNode) {if root ! nil {postorderTraversal(root.Left) // 递归遍历左子树postorderTraversal(root.Right) // 递归遍历右子树fmt.Println(root.Val) // 访问根节点}
}2、迭代遍历
// 后序遍历左 - 右 - 根迭代实现
func postorderTraversal(root *TreeNode) {if root nil {return}// 栈存放的全是 *TreeNodes1 : shard.NewStackArray[*TreeNode]()s1.Push(root)s2 : shard.NewStackArray[*TreeNode]()for !s1.IsEmpty() {node, _ : s1.Pop()s2.Push(node)if node.Left ! nil {s1.Push(node.Left)}if node.Right ! nil {s1.Push(node.Right)}}for !s2.IsEmpty() {node, _ : s2.Pop()fmt.Println(node.Val)}
}二、广度优先遍历
1、层序遍历
// 层序遍历
func postorderTraversal(root *TreeNode) {if root nil {return}q : shard.NewQueueArray[*TreeNode]()q.Enqueue(root)for !q.IsEmpty() {node, _ : q.Dequeue()fmt.Print(node.Val, )if node.Left ! nil {q.Enqueue(node.Left)}if node.Right ! nil {q.Enqueue(node.Right)}}
}三、shard库介绍
GitHub链接https://github.com/xzhHas/shard
shard库获取
go get -u github.com/xzhHas/shardlatest关于使用Golang写一个数据结构的库目前只支持栈、队列、堆。
