lua二叉树结构详细例子

admin

二叉树是一种树形数据结构，每个节点最多有两个子节点。以下是一个详细的 Lua 二叉树实现示例，涵盖了插入、查找、删除等操作，并展示如何创建和操作二叉树。

1. -- 二叉树节点定义
   
2. local Node = {}
   
3. Node.__index = Node
   
4. 
   
5. -- 创建一个新的节点
   
6. function Node:new(value)
   
7.     local node = setmetatable({}, Node)
   
8.     node.value = value   -- 节点存储的值
   
9.     node.left = nil      -- 左子树
   
10.     node.right = nil     -- 右子树
    
11.     return node
    
12. end
    
13. 
    
14. -- 二叉树定义
    
15. local BinaryTree = {}
    
16. BinaryTree.__index = BinaryTree
    
17. 
    
18. -- 创建一个新的二叉树
    
19. function BinaryTree:new()
    
20.     local tree = setmetatable({}, BinaryTree)
    
21.     tree.root = nil  -- 树的根节点
    
22.     return tree
    
23. end
    
24. 
    
25. -- 插入一个值到二叉树中
    
26. function BinaryTree:insert(value)
    
27.     local newNode = Node:new(value)
    
28.     if not self.root then
    
29.         self.root = newNode
    
30.     else
    
31.         self:_insertRecursive(self.root, newNode)
    
32.     end
    
33. end
    
34. 
    
35. -- 递归插入节点
    
36. function BinaryTree:_insertRecursive(node, newNode)
    
37.     if newNode.value < node.value then
    
38.         if not node.left then
    
39.             node.left = newNode
    
40.         else
    
41.             self:_insertRecursive(node.left, newNode)
    
42.         end
    
43.     else
    
44.         if not node.right then
    
45.             node.right = newNode
    
46.         else
    
47.             self:_insertRecursive(node.right, newNode)
    
48.         end
    
49.     end
    
50. end
    
51. 
    
52. -- 查找一个值
    
53. function BinaryTree:search(value)
    
54.     return self:_searchRecursive(self.root, value)
    
55. end
    
56. 
    
57. -- 递归查找
    
58. function BinaryTree:_searchRecursive(node, value)
    
59.     if not node then
    
60.         return nil  -- 找不到
    
61.     end
    
62. 
    
63.     if value == node.value then
    
64.         return node  -- 找到节点
    
65.     elseif value < node.value then
    
66.         return self:_searchRecursive(node.left, value)  -- 继续在左子树查找
    
67.     else
    
68.         return self:_searchRecursive(node.right, value)  -- 继续在右子树查找
    
69.     end
    
70. end
    
71. 
    
72. -- 删除一个值
    
73. function BinaryTree:delete(value)
    
74.     self.root = self:_deleteRecursive(self.root, value)
    
75. end
    
76. 
    
77. -- 递归删除节点
    
78. function BinaryTree:_deleteRecursive(node, value)
    
79.     if not node then
    
80.         return nil
    
81.     end
    
82. 
    
83.     if value < node.value then
    
84.         node.left = self:_deleteRecursive(node.left, value)
    
85.     elseif value > node.value then
    
86.         node.right = self:_deleteRecursive(node.right, value)
    
87.     else
    
88.         -- 找到要删除的节点
    
89.         if not node.left then
    
90.             return node.right
    
91.         elseif not node.right then
    
92.             return node.left
    
93.         else
    
94.             -- 节点有两个子节点
    
95.             local minNode = self:_findMin(node.right)
    
96.             node.value = minNode.value
    
97.             node.right = self:_deleteRecursive(node.right, minNode.value)
    
98.         end
    
99.     end
    
100. 
     
101.     return node
     
102. end
     
103. 
     
104. -- 查找最小值节点
     
105. function BinaryTree:_findMin(node)
     
106.     while node.left do
     
107.         node = node.left
     
108.     end
     
109.     return node
     
110. end
     
111. 
     
112. -- 中序遍历（递增顺序）
     
113. function BinaryTree:inOrderTraversal()
     
114.     self:_inOrderRecursive(self.root)
     
115.     print()  -- 换行
     
116. end
     
117. 
     
118. -- 递归中序遍历
     
119. function BinaryTree:_inOrderRecursive(node)
     
120.     if node then
     
121.         self:_inOrderRecursive(node.left)
     
122.         io.write(node.value .. " ")
     
123.         self:_inOrderRecursive(node.right)
     
124.     end
     
125. end
     
126. 
     
127. -- 前序遍历
     
128. function BinaryTree:preOrderTraversal()
     
129.     self:_preOrderRecursive(self.root)
     
130.     print()
     
131. end
     
132. 
     
133. -- 递归前序遍历
     
134. function BinaryTree:_preOrderRecursive(node)
     
135.     if node then
     
136.         io.write(node.value .. " ")
     
137.         self:_preOrderRecursive(node.left)
     
138.         self:_preOrderRecursive(node.right)
     
139.     end
     
140. end
     
141. 
     
142. -- 后序遍历
     
143. function BinaryTree:postOrderTraversal()
     
144.     self:_postOrderRecursive(self.root)
     
145.     print()
     
146. end
     
147. 
     
148. -- 递归后序遍历
     
149. function BinaryTree:_postOrderRecursive(node)
     
150.     if node then
     
151.         self:_postOrderRecursive(node.left)
     
152.         self:_postOrderRecursive(node.right)
     
153.         io.write(node.value .. " ")
     
154.     end
     
155. end
     

复制代码

代码解释

• 节点 (Node):
  
  • Node 类代表树中的一个节点。每个节点有一个 value 值，以及指向左子节点 (left) 和右子节点 (right) 的指针。
    
• 二叉树 (BinaryTree):
  
  • BinaryTree 类表示整棵树，它有一个指向根节点 (root) 的指针。
  • 该类包含了 insert, search, delete, 以及几种遍历方法。
    
• 插入操作 (insert):
  
  • 插入一个新的节点，如果树为空则将新节点作为根节点。
  • 否则，通过 _insertRecursive 方法递归地将新节点插入合适的位置。
    
• 查找操作 (search):
  
  • 通过 _searchRecursive 方法递归查找节点。如果节点值小于当前节点，继续在左子树查找；如果节点值大于当前节点，继续在右子树查找。
    
• 删除操作 (delete):
  
  • 使用 _deleteRecursive 方法递归删除节点。如果节点只有一个子节点，则直接替换该节点为子节点；如果节点有两个子节点，则找到右子树中的最小节点，将其值替换当前节点，然后递归删除该最小节点。
    
• 遍历操作:
  
  • 中序遍历 (inOrderTraversal): 按照左子树-根节点-右子树的顺序遍历树，返回递增的顺序。
  • 前序遍历 (preOrderTraversal): 按照根节点-左子树-右子树的顺序遍历。
  • 后序遍历 (postOrderTraversal): 按照左子树-右子树-根节点的顺序遍历。
    

使用示例

1. -- 创建一个二叉树
   
2. local tree = BinaryTree:new()
   
3. 
   
4. -- 插入节点
   
5. tree:insert(50)
   
6. tree:insert(30)
   
7. tree:insert(70)
   
8. tree:insert(20)
   
9. tree:insert(40)
   
10. tree:insert(60)
    
11. tree:insert(80)
    
12. 
    
13. -- 打印树的中序遍历结果
    
14. print("中序遍历结果：")
    
15. tree:inOrderTraversal()  -- 输出: 20 30 40 50 60 70 80
    
16. 
    
17. -- 查找某个节点
    
18. local result = tree:search(60)
    
19. if result then
    
20.     print("找到节点: " .. result.value)
    
21. else
    
22.     print("节点未找到")
    
23. end
    
24. 
    
25. -- 删除节点
    
26. tree:delete(50)
    
27. 
    
28. -- 打印删除后的中序遍历结果
    
29. print("删除50后的中序遍历结果：")
    
30. tree:inOrderTraversal()  -- 输出: 20 30 40 60 70 80
    

复制代码

解释:

• 创建一个 BinaryTree 对象，并使用 insert 方法插入一些值。
• 使用 inOrderTraversal 输出树的中序遍历（即递增排序的节点）。
• 查找节点值为 60 的节点，找到后输出其值。
• 删除节点 50，并打印删除后的树的中序遍历结果。
  

扩展：

• 你可以添加其他功能，比如计算树的高度、计算节点的数量、检查树是否平衡等。
  

admin

+1

dfghhdsgfafgdfg

感谢分享

admin

6666666

学编程的闹钟

谢谢分享