用python实现数据结构树的
时间: 2023-11-26 08:46:35 浏览: 34
树是一种非线性数据结构,它由节点和边组成,每个节点可能有零个或多个子节点。树的一个节点称为根节点,它没有父节点。树的节点可以分为内部节点和叶节点,内部节点是有子节点的节点,而叶节点是没有子节点的节点。树的深度是指从根节点到最远叶节点的距离,而树的高度是指从最底层叶节点到根节点的距离。
在Python中,可以使用类来实现树的数据结构。下面是一个示例代码,其中包含了树的基本操作,如添加节点、查找节点、删除节点等。
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
class Tree:
def __init__(self):
self.root = None
def add_node(self, val):
node = TreeNode(val)
if self.root is None:
self.root = node
else:
queue = [self.root]
while queue:
curr = queue.pop(0)
if curr.left is None:
curr.left = node
return
elif curr.right is None:
curr.right = node
return
else:
queue.append(curr.left)
queue.append(curr.right)
def find_node(self, val):
if self.root is None:
return None
else:
queue = [self.root]
while queue:
curr = queue.pop(0)
if curr.val == val:
return curr
if curr.left is not None:
queue.append(curr.left)
if curr.right is not None:
queue.append(curr.right)
return None
def delete_node(self, val):
node = self.find_node(val)
if node is None:
return False
else:
queue = [self.root]
while queue:
curr = queue.pop(0)
if curr.left is node:
curr.left = None
return True
elif curr.right is node:
curr.right = None
return True
else:
if curr.left is not None:
queue.append(curr.left)
if curr.right is not None:
queue.append(curr.right)
return False
```
以上代码实现了一个基本的树结构,包括添加节点、查找节点和删除节点等操作。可以通过创建一个Tree对象来使用这些操作。