二叉树的三种遍历操作及在某种遍历结构下进行二叉树的操作,如求树的深度、叶子节点个 数、总节点数等 完整代码
时间: 2024-02-15 19:02:46 浏览: 11
以下是基于 Python 语言的二叉树遍历操作和相关的节点操作的完整代码:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class BinaryTree:
def __init__(self):
self.root = None
# 前序遍历
def preorderTraversal(self, root):
if not root:
return
print(root.val)
self.preorderTraversal(root.left)
self.preorderTraversal(root.right)
# 中序遍历
def inorderTraversal(self, root):
if not root:
return
self.inorderTraversal(root.left)
print(root.val)
self.inorderTraversal(root.right)
# 后序遍历
def postorderTraversal(self, root):
if not root:
return
self.postorderTraversal(root.left)
self.postorderTraversal(root.right)
print(root.val)
# 求树的深度
def maxDepth(self, root):
if not root:
return 0
return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1
# 求叶子节点个数
def countLeaves(self, root):
if not root:
return 0
if not root.left and not root.right:
return 1
return self.countLeaves(root.left) + self.countLeaves(root.right)
# 求总节点数
def countNodes(self, root):
if not root:
return 0
return self.countNodes(root.left) + self.countNodes(root.right) + 1
```
可以通过以下代码创建一棵二叉树并测试以上方法:
```python
tree = BinaryTree()
tree.root = TreeNode(1)
tree.root.left = TreeNode(2)
tree.root.right = TreeNode(3)
tree.root.left.left = TreeNode(4)
tree.root.left.right = TreeNode(5)
# 测试遍历方法
print("前序遍历:")
tree.preorderTraversal(tree.root)
print("中序遍历:")
tree.inorderTraversal(tree.root)
print("后序遍历:")
tree.postorderTraversal(tree.root)
# 测试节点操作方法
print("树的深度:", tree.maxDepth(tree.root))
print("叶子节点个数:", tree.countLeaves(tree.root))
print("总节点数:", tree.countNodes(tree.root))
```