创建二叉树类。二叉树的存储结构使用链表。提供操作:前序遍历、中序遍历、后序遍历、层次遍历、计算二叉树结点数目、计算二叉树高度。
时间: 2023-04-25 08:06:20 浏览: 178
好的,以下是用中文回复的创建二叉树类,包括提供的操作:
1. 前序遍历
2. 中序遍历
3. 后序遍历
4. 层次遍历
5. 计算二叉树结点数目
6. 计算二叉树高度
二叉树类的存储结构使用链表,具体实现如下:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
class BinaryTree:
def __init__(self):
self.root = None
# 前序遍历
def preorderTraversal(self, node):
if node:
print(node.val, end=' ')
self.preorderTraversal(node.left)
self.preorderTraversal(node.right)
# 中序遍历
def inorderTraversal(self, node):
if node:
self.inorderTraversal(node.left)
print(node.val, end=' ')
self.inorderTraversal(node.right)
# 后序遍历
def postorderTraversal(self, node):
if node:
self.postorderTraversal(node.left)
self.postorderTraversal(node.right)
print(node.val, end=' ')
# 层次遍历
def levelorderTraversal(self, node):
if not node:
return
queue = [node]
while queue:
cur_node = queue.pop()
print(cur_node.val, end=' ')
if cur_node.left:
queue.append(cur_node.left)
if cur_node.right:
queue.append(cur_node.right)
# 计算二叉树结点数目
def countNodes(self, node):
if not node:
return
return 1 + self.countNodes(node.left) + self.countNodes(node.right)
# 计算二叉树高度
def getHeight(self, node):
if not node:
return
left_height = self.getHeight(node.left)
right_height = self.getHeight(node.right)
return max(left_height, right_height) + 1
```
以上就是创建二叉树类并提供前序遍历、中序遍历、后序遍历、层次遍历、计算二叉树结点数目、计算二叉树高度的操作。
阅读全文