定义二叉树建立函数 greateRT(self Roat),建立一棵二叉树: 2)定义递归函数 preQrder(self, Root),输出二叉树的先序遍历序列: 3)定义递归函数pastOrder(self, Root),输出二叉树的中序遍历序列; 4)定义递归西数 middleOrder(self,Root),输出二叉树的后序遍历序列:, 5)定义西数 levelorder(self, Root),输出二叉树的层次遍历。 6)参照层次遍历函数,定义一个新函数tind财(self, Root, X),输入一个指定的字符x,在 指定的一棵二叉树中查找值为 x 的结点,如果查找成功,则输出“OK”,否则输出 ‘‘ERROR”; 7)参照层次遍历函数,定义一个新函数 cauntNode(self, Root),求二叉树的节点个数:— 8) 参照层次遍历函数,定义一个新函数 cauntleafNode(self, Root),求二叉树的叶子节点 的个数。 9)定义和执行主函数main(),在主函数中,依次调用上面8个函数,实现二叉树的创 建、遍历、节点查找、节点统计等。。
时间: 2024-03-18 11:42:04 浏览: 61
很抱歉,我是一个语言模型AI,无法直接执行代码。不过,我可以为您解答相关问题并提供相关思路:
1. 定义二叉树建立函数 greateRT(self Roat),建立一棵二叉树:
```
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
class BinaryTree:
def __init__(self):
self.root = None
def createBT(self, arr):
n = len(arr)
if n == 0: # 如果数组为空,则返回None
return None
mid = n // 2 # 取中间值作为根节点
root = TreeNode(arr[mid])
root.left = self.createBT(arr[:mid]) # 递归构建左子树
root.right = self.createBT(arr[mid+1:]) # 递归构建右子树
self.root = root
```
2. 定义递归函数 preOrder(self, Root),输出二叉树的先序遍历序列:
```
def preOrder(self, root):
if root:
print(root.val, end=' ')
self.preOrder(root.left)
self.preOrder(root.right)
```
3. 定义递归函数 inOrder(self, Root),输出二叉树的中序遍历序列:
```
def inOrder(self, root):
if root:
self.inOrder(root.left)
print(root.val, end=' ')
self.inOrder(root.right)
```
4. 定义递归函数 postOrder(self, Root),输出二叉树的后序遍历序列:
```
def postOrder(self, root):
if root:
self.postOrder(root.left)
self.postOrder(root.right)
print(root.val, end=' ')
```
5. 定义函数 levelOrder(self, Root),输出二叉树的层次遍历:
```
def levelOrder(self, root):
if not root:
return []
res = []
queue = [root]
while queue:
level = []
size = len(queue)
for i in range(size):
node = queue.pop(0)
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
res.append(level)
return res
```
6. 定义函数 findNode(self, root, x),输入一个指定的字符 x,在指定的一棵二叉树中查找值为 x 的结点,如果查找成功,则输出“OK”,否则输出 “ERROR”:
```
def findNode(self, root, x):
if not root:
return "ERROR"
if root.val == x:
return "OK"
res = self.findNode(root.left, x)
if res == "OK":
return "OK"
else:
return self.findNode(root.right, x)
```
7. 定义函数 countNode(self, root),求二叉树的节点个数:
```
def countNode(self, root):
if not root:
return 0
return 1 + self.countNode(root.left) + self.countNode(root.right)
```
8. 定义函数 countLeafNode(self, root),求二叉树的叶子节点的个数:
```
def countLeafNode(self, root):
if not root:
return 0
if not root.left and not root.right:
return 1
return self.countLeafNode(root.left) + self.countLeafNode(root.right)
```
9. 定义和执行主函数 main(),在主函数中,依次调用上面8个函数,实现二叉树的创建、遍历、节点查找、节点统计等:
```
def main():
# 创建二叉树
bt = BinaryTree()
arr = [1, 2, 3, 4, 5, 6, 7]
bt.createBT(arr)
# 先序遍历
print("先序遍历:")
bt.preOrder(bt.root)
print()
# 中序遍历
print("中序遍历:")
bt.inOrder(bt.root)
print()
# 后序遍历
print("后序遍历:")
bt.postOrder(bt.root)
print()
# 层次遍历
print("层次遍历:")
print(bt.levelOrder(bt.root))
# 查找节点
x = 3
print("查找节点 {}:{}".format(x, bt.findNode(bt.root, x)))
# 节点个数
print("节点个数:", bt.countNode(bt.root))
# 叶子节点个数
print("叶子节点个数:", bt.countLeafNode(bt.root))
if __name__ == '__main__':
main()
```
阅读全文