编写一个程序,实现功能具体如下: 1.以二叉链表表示二叉树,建立一棵二叉树; 2.输出二叉树的中序遍历结果; 3.输出二叉树的前序遍历结果; 4.输出二叉树的后序遍历结果; 5.计算二叉树的深度; 6.统计二叉树的结点个数; 7.统计二叉树的叶结点个数。
时间: 2023-11-14 16:26:26 浏览: 36
好的,以下是 Python 语言的代码实现:
```python
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
class BinaryTree:
def __init__(self):
self.root = None
def buildTree(self, vals):
if not vals:
return None
self.root = Node(vals[0])
queue = [self.root]
i = 1
while queue and i < len(vals):
cur = queue.pop(0)
if vals[i] is not None:
cur.left = Node(vals[i])
queue.append(cur.left)
i += 1
if i >= len(vals):
break
if vals[i] is not None:
cur.right = Node(vals[i])
queue.append(cur.right)
i += 1
def inorderTraversal(self):
def dfs(node):
if not node:
return
dfs(node.left)
res.append(node.val)
dfs(node.right)
res = []
dfs(self.root)
return res
def preorderTraversal(self):
def dfs(node):
if not node:
return
res.append(node.val)
dfs(node.left)
dfs(node.right)
res = []
dfs(self.root)
return res
def postorderTraversal(self):
def dfs(node):
if not node:
return
dfs(node.left)
dfs(node.right)
res.append(node.val)
res = []
dfs(self.root)
return res
def maxDepth(self):
def dfs(node, depth):
if not node:
return depth
depth += 1
return max(dfs(node.left, depth), dfs(node.right, depth))
return dfs(self.root, 0)
def countNodes(self):
def dfs(node):
if not node:
return 0
return 1 + dfs(node.left) + dfs(node.right)
return dfs(self.root)
def countLeaves(self):
def dfs(node):
if not node:
return 0
if not node.left and not node.right:
return 1
return dfs(node.left) + dfs(node.right)
return dfs(self.root)
```
以上代码实现了建立二叉树、中序遍历、前序遍历、后序遍历、计算深度、统计结点个数和统计叶结点个数等功能。其中,建立二叉树的函数 `buildTree` 接受一个列表作为参数,这个列表是按照从上到下、从左到右的顺序存储二叉树节点的值,如果该节点为空,则用 `None` 占位。例如,列表 `[1, 2, 3, None, 4]` 表示以下二叉树:
```
1
/ \
2 3
/
4
```
如果你想要测试一下代码的功能,可以这样写:
```python
tree = BinaryTree()
tree.buildTree([1, 2, 3, None, 4])
print(tree.inorderTraversal()) # [2, 1, 4, 3]
print(tree.preorderTraversal()) # [1, 2, 3, 4]
print(tree.postorderTraversal()) # [2, 4, 3, 1]
print(tree.maxDepth()) # 3
print(tree.countNodes()) # 4
print(tree.countLeaves()) # 2
```
希望这个程序能够帮助到你!