在Go语言中设置二叉树的索引。

huangapple
go评论121阅读模式
英文:

Setting an index of a binary tree in go

问题

我正在尝试自学数据结构和算法，并且正在努力找出向二叉树添加索引的最佳方法。

我猜最好的方法是修改中序遍历操作，但我不确定如何实现并在每次插入和删除函数之后链接它。

  1. type BinarySearchNode struct {
  2. 	Left   *BinarySearchNode
  3. 	Right  *BinarySearchNode
  4. 	Parent *BinarySearchNode
  5. 	Data   int
  6. 	Index  int
  7. }
  9. func (BSN *BinarySearchNode) Insert(value int) {
  11. 	if BSN.Data > value {
  12. 		if BSN.Left == nil {
  13. 			BSN.Left = &BinarySearchNode{Data: value, Parent: BSN}
  14. 			return
  15. 		}
  16. 		BSN.Left.Insert(value)
  17. 		return
  18. 	}
  20. 	if BSN.Right == nil {
  21. 		BSN.Right = &BinarySearchNode{Data: value, Parent: BSN}
  22. 		return
  23. 	}
  24. 	BSN.Right.Insert(value)
  25. }
  27. func (BSN *BinarySearchNode) setIndex(node *BinarySearchNode, count int) int {
  28. 	if node == nil {
  29. 		return count
  30. 	}
  32. 	if node.Right == nil && node.Left == nil {
  33. 		node.Index = count
  34. 	}
  35. 	node.setIndex(node.Left, count+1)
  36. 	node.setIndex(node.Right, count+1)
  38. 	return count
  39. }

以上是你提供的代码部分的翻译。

英文:

Im trying to teach myself data structures & algos and I am trying to figure out the best way to add an index to a binary tree

Im guessing the best way to do this is to modify an in orderTraversal operation but im not exactly sure how I would implement this and chain that on after every insert and delete function.

  2. type BinarySearchNode struct {
  3. 	Left *BinarySearchNode
  4. 	Right *BinarySearchNode
  5. 	Parent *BinarySearchNode
  6. 	Data int
  7. 	Index int
  8. }
  10. func (BSN *BinarySearchNode) Insert(value int){
  11. 	
  12. 	if BSN.Data > value {
  13. 		if BSN.Left == nil{
  14. 			BSN.Left = &BinarySearchNode{Data:value, Parent:BSN}
  15. 			return
  16. 		}
  17. 		BSN.Left.Insert(value)
  18. 		return
  19. 	}
  21. 	if BSN.Right == nil{
  22. 		BSN.Right = &BinarySearchNode{Data:value, Parent: BSN}
  23. 		return
  24. 	}
  25. 	BSN.Right.Insert(value)
  26. }
  28. func (BSN *BinarySearchNode) setIndex(node *BinarySearchNode, count int)(int){
  29. 	if node == nil{
  30. 		return count
  31. 	}
  33. 	if node.Right == nil && node.Left == nil{
  34. 		node.Index = count
  35. 	}
  36. 	node.setIndex(node.Left, count+1)
  37. 	node.setIndex(node.Right, count+1)
  38. 	
  39. 	return count
  40. }

答案1

得分: 1

我有一段用于在golang中实现二叉树的代码，可能对你有帮助。

  1. package main
  3. import (
  4. 	"fmt"
  5. 	"math"
  6. )
  8. // 二叉树中的单个节点
  9. type Node struct {
  11. 	// 节点包含的值
  12. 	Value int
  14. 	// 节点的左子节点
  15. 	Left *Node
  17. 	// 节点的右子节点
  18. 	Right *Node
  19. }
  21. type BinaryTree struct {
  22. 	Root *Node
  23. }
  25. // 在二叉树中插入元素
  26. func (tree *BinaryTree) Insert(value int) {
  27. 	if tree.Root == nil {
  28. 		node := new(Node)
  29. 		node.Value = value
  30. 		tree.Root = node
  31. 		return
  32. 	}
  33. 	current := tree.Root
  34. 	for {
  35. 		if value < current.Value {
  36. 			if current.Left == nil {
  38. 				node := new(Node)
  39. 				node.Value = value
  40. 				current.Left = node
  41. 				return
  42. 			} else {
  43. 				current = current.Left
  44. 			}
  46. 		} else {
  47. 			if current.Right == nil {
  49. 				node := new(Node)
  50. 				node.Value = value
  51. 				current.Right = node
  52. 				return
  53. 			} else {
  54. 				current = current.Right
  55. 			}
  56. 		}
  57. 	}
  58. }
  60. // 递归前序遍历
  61. func (tree *BinaryTree) RecursivePreOrder(root *Node) {
  62. 	if root == nil {
  63. 		return
  64. 	}
  65. 	fmt.Println(root.Value)
  66. 	tree.RecursivePreOrder(root.Left)
  67. 	tree.RecursivePreOrder(root.Right)
  69. }
  71. // 迭代前序遍历
  72. func (tree *BinaryTree) IterativePreOrder(root *Node) {
  73. 	stack := []*Node{}
  74. 	for {
  75. 		for root != nil {
  76. 			fmt.Println(root.Value)
  77. 			stack = append([]*Node{root}, stack...)
  78. 			root = root.Left
  79. 		}
  80. 		if len(stack) == 0 {
  81. 			break
  82. 		}
  83. 		root = stack[0]
  84. 		stack = stack[1:]
  85. 		root = root.Right
  86. 	}
  87. }
  89. // 递归中序遍历
  90. func (tree *BinaryTree) RecursiveInOrder(root *Node) {
  91. 	if root == nil {
  92. 		return
  93. 	}
  94. 	tree.RecursiveInOrder(root.Left)
  95. 	fmt.Println(root.Value)
  96. 	tree.RecursiveInOrder(root.Right)
  98. }
  100. // 迭代中序遍历
  101. func (tree *BinaryTree) IterativeInOrder(root *Node) {
  102. 	var stack []*Node
  103. 	for {
  104. 		for root != nil {
  105. 			stack = append([]*Node{root}, stack...)
  106. 			root = root.Left
  107. 		}
  108. 		if len(stack) == 0 {
  109. 			break
  110. 		}
  111. 		root = stack[0]
  112. 		stack = stack[1:]
  113. 		fmt.Println(root.Value)
  114. 		root = root.Right
  115. 	}
  116. }
  118. // 递归后序遍历
  119. func (tree *BinaryTree) RecursivePostOrder(root *Node) {
  120. 	if root == nil {
  121. 		return
  122. 	}
  123. 	tree.RecursivePostOrder(root.Left)
  124. 	tree.RecursivePostOrder(root.Right)
  125. 	fmt.Println(root.Value)
  126. }
  128. // 迭代后序遍历
  129. func (tree *BinaryTree) IterativePostOrder(root *Node) {
  130. 	stack := []*Node{}
  132. 	var previous *Node = nil
  133. 	for {
  134. 		for root != nil {
  135. 			stack = append([]*Node{root}, stack...)
  136. 			root = root.Left
  137. 		}
  138. 		for root == nil && len(stack) != 0 {
  139. 			root = stack[0]
  140. 			if root.Right == nil || root.Right == previous {
  141. 				fmt.Println(root.Value)
  142. 				stack = stack[1:]
  143. 				previous = root
  144. 				root = nil
  145. 			} else {
  146. 				root = root.Right
  147. 			}
  148. 		}
  149. 		if len(stack) == 0 {
  150. 			break
  151. 		}
  152. 	}
  153. }
  155. // 层序遍历
  156. func (tree *BinaryTree) LevelOrder(root *Node) {
  157. 	// 用于执行广度优先遍历的队列
  158. 	queue := []*Node{}
  160. 	if root != nil {
  161. 		queue = append(queue, root)
  162. 	}
  163. 	for len(queue) > 0 {
  164. 		root = queue[0]
  165. 		queue = queue[1:]
  166. 		fmt.Println(root.Value)
  167. 		if root.Left != nil {
  168. 			queue = append(queue, root.Left)
  169. 		}
  170. 		if root.Right != nil {
  171. 			queue = append(queue, root.Right)
  172. 		}
  173. 	}
  174. }
  176. // 计算二叉树的大小（节点数量）
  177. func (tree *BinaryTree) Size(root *Node) int {
  178. 	if root == nil {
  179. 		return 0
  180. 	}
  181. 	sum := tree.Size(root.Left) + 1 + tree.Size(root.Right)
  182. 	return sum
  183. }
  185. // 获取二叉树中指定索引的节点
  186. func (tree *BinaryTree) ElementAt(root *Node, index int) *Node {
  187. 	if index > tree.Size(root)-1 {
  188. 		fmt.Println("索引不存在")
  189. 		return nil
  190. 	}
  191. 	leftSize := tree.Size(root.Left)
  192. 	if index == leftSize {
  193. 		return root
  194. 	} else if index < leftSize {
  195. 		return tree.ElementAt(root.Left, index)
  196. 	} else {
  197. 		return tree.ElementAt(root.Right, index-leftSize-1)
  198. 	}
  199. }
  201. // 计算二叉树的高度
  202. func (tree *BinaryTree) Height(root *Node) int {
  203. 	if root == nil {
  204. 		return -1
  205. 	}
  206. 	return int(math.Max(float64(tree.Height(root.Left)), float64(tree.Height(root.Right)))) + 1
  207. }
  209. // 程序的入口点
  210. func main() {
  211. 	tree := new(BinaryTree)
  212. 	tree.Insert(44)
  213. 	tree.Insert(55)
  214. 	tree.Insert(33)
  215. 	fmt.Println(tree.Height(tree.Root))
  217. }

希望对你有所帮助！

英文:

I have a piece of code for the implementation of binary tree in golang. It may help you.

  1. package main
  2. import (
  3. &quot;fmt&quot;
  4. &quot;math&quot;
  5. )
  6. // A single Node in a binary tree
  7. type Node struct {
  8. // Value contained by the node
  9. Value int
  10. // Left subnode of the node
  11. Left *Node
  12. // Right subnode of the node
  13. Right *Node
  14. }
  15. type BinaryTree struct {
  16. Root *Node
  17. }
  18. // inserting the element in the binary tree
  19. func (tree *BinaryTree) Insert(value int) {
  20. if tree.Root == nil {
  21. node := new(Node)
  22. node.Value = value
  23. tree.Root = node
  24. return
  25. }
  26. current := tree.Root
  27. for {
  28. if value &lt; current.Value {
  29. if current.Left == nil {
  30. node := new(Node)
  31. node.Value = value
  32. current.Left = node
  33. return
  34. } else {
  35. current = current.Left
  36. }
  37. } else {
  38. if current.Right == nil {
  39. node := new(Node)
  40. node.Value = value
  41. current.Right = node
  42. return
  43. } else {
  44. current = current.Right
  45. }
  46. }
  47. }
  48. }
  49. // current left right
  50. func (tree *BinaryTree) RecursivePreOrder(root *Node) {
  51. if root == nil {
  52. return
  53. }
  54. fmt.Println(root.Value)
  55. tree.RecursivePreOrder(root.Left)
  56. tree.RecursivePreOrder(root.Right)
  57. }
  58. func (tree *BinaryTree) IterativePreOrder(root *Node) {
  59. stack := []*Node{}
  60. for {
  61. for root != nil {
  62. fmt.Println(root.Value)
  63. stack = append([]*Node{root}, stack...)
  64. root = root.Left
  65. }
  66. if len(stack) == 0 {
  67. break
  68. }
  69. root = stack[0]
  70. stack = stack[1:]
  71. root = root.Right
  72. }
  73. }
  74. func (tree *BinaryTree) RecursiveInOrder(root *Node) {
  75. if root == nil {
  76. return
  77. }
  78. tree.RecursiveInOrder(root.Left)
  79. fmt.Println(root.Value)
  80. tree.RecursiveInOrder(root.Right)
  81. }
  82. func (tree *BinaryTree) IterativeInOrder(root *Node) {
  83. var stack []*Node
  84. for {
  85. for root != nil {
  86. stack = append([]*Node{root}, stack...)
  87. root = root.Left
  88. }
  89. if len(stack) == 0 {
  90. break
  91. }
  92. root = stack[0]
  93. stack = stack[1:]
  94. fmt.Println(root.Value)
  95. root = root.Right
  96. }
  97. }
  98. func (tree *BinaryTree) RecursivePostOrder(root *Node) {
  99. if root == nil {
  100. return
  101. }
  102. tree.RecursivePostOrder(root.Left)
  103. tree.RecursivePostOrder(root.Right)
  104. fmt.Println(root.Value)
  105. }
  106. func (tree *BinaryTree) IterativePostOrder(root *Node) {
  107. stack := []*Node{}
  108. var previous *Node = nil
  109. for {
  110. for root != nil {
  111. stack = append([]*Node{root}, stack...)
  112. root = root.Left
  113. }
  114. for root == nil &amp;&amp; len(stack) != 0 {
  115. root = stack[0]
  116. if root.Right == nil || root.Right == previous {
  117. fmt.Println(root.Value)
  118. stack = stack[1:]
  119. previous = root
  120. root = nil
  121. } else {
  122. root = root.Right
  123. }
  124. }
  125. if len(stack) == 0 {
  126. break
  127. }
  128. }
  129. }
  130. func (tree *BinaryTree) LevelOrder(root *Node) {
  131. // a queue for performing level order traversal of breadth first traversal
  132. queue := []*Node{}
  133. if root != nil {
  134. queue = append(queue, root)
  135. }
  136. for len(queue) &gt; 0 {
  137. root = queue[0]
  138. queue = queue[1:]
  139. fmt.Println(root.Value)
  140. if root.Left != nil {
  141. queue = append(queue, root.Left)
  142. }
  143. if root.Right != nil {
  144. queue = append(queue, root.Right)
  145. }
  146. }
  147. }
  148. func (tree *BinaryTree) Size(root *Node) int {
  149. if root == nil {
  150. return 0
  151. }
  152. sum := tree.Size(root.Left) + 1 + tree.Size(root.Right)
  153. return sum
  154. }
  155. func (tree *BinaryTree) ElementAt(root *Node, index int) *Node {
  156. if index &gt; tree.Size(root)-1 {
  157. fmt.Println(&quot;Index doesnot exist&quot;)
  158. return nil
  159. }
  160. leftSize := tree.Size(root.Left)
  161. if index == leftSize {
  162. return root
  163. } else if index &lt; leftSize {
  164. return tree.ElementAt(root.Left, index)
  165. } else {
  166. return tree.ElementAt(root.Right, index-leftSize-1)
  167. }
  168. }
  169. func (tree *BinaryTree) Height(root *Node) int {
  170. if root == nil {
  171. return -1
  172. }
  173. return int(math.Max(float64(tree.Height(root.Left)), float64(tree.Height(root.Right)))) + 1
  174. }
  175. // starting point of the program
  176. func main() {
  177. tree := new(BinaryTree)
  178. tree.Insert(44)
  179. tree.Insert(55)
  180. tree.Insert(33)
  181. fmt.Println(tree.Height(tree.Root))
  182. }

huangapple
  • 本文由 发表于 2022年3月13日 03:28:35
  • 转载请务必保留本文链接：https://go.coder-hub.com/71452529.html
  • algorithm
  • binary-search-tree
  • data-structures
  • go
  • recursion
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定