1) 定义二叉树建立函数 createBT(self,Root),建立一棵二叉树; 2) 定义递归函数preOrder(self, Root),输出二叉树的先序遍历序列; 3) 定义递归函数postOrder(self, Root),输出二叉树的中序遍历序列; 4) 定义递归函数middleOrder(self, Root),输出二叉树的后序遍历序列; 5) 定义函数levelOrder(self, Root),输出二叉树的层次遍历。 6) 参照层次遍历函数,定义一个新函数 findBt(self, Root, x),输入一个指定的字符x,在指定的一棵二叉树中查找值为x的结点,如果查找成功,则输出“OK”,否则输出“ERROR”; 7) 参照层次遍历函数,定义一个新函数countNode(self, Root),求二叉树的节点个数; 8) 参照层次遍历函数,定义一个新函数countLeafNode(self, Root),求二叉树的叶子节点的个数。 9) 定义和执行主函数 main( ),在主函数中,依次调用上面8个函数,实现二叉树的创建、遍历、节点查找、节点统计等。
时间: 2024-03-17 14:42:15 浏览: 56
好的,以下是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 createBT(self, Root):
val = input("请输入节点的值:")
if val == '#':
Root = None
else:
Root = Node(val)
Root.left = self.createBT(Root.left)
Root.right = self.createBT(Root.right)
return Root
def preOrder(self, Root):
if Root:
print(Root.val, end=' ')
self.preOrder(Root.left)
self.preOrder(Root.right)
def postOrder(self, Root):
if Root:
self.postOrder(Root.left)
print(Root.val, end=' ')
self.postOrder(Root.right)
def middleOrder(self, Root):
if Root:
self.middleOrder(Root.left)
print(Root.val, end=' ')
self.middleOrder(Root.right)
def levelOrder(self, Root):
if Root is None:
return
queue = [Root]
while queue:
node = queue.pop(0)
print(node.val, end=' ')
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
def findBt(self, Root, x):
if Root is None:
return False
queue = [Root]
while queue:
node = queue.pop(0)
if node.val == x:
return True
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return False
def countNode(self, Root):
if Root is None:
return 0
queue = [Root]
count = 0
while queue:
node = queue.pop(0)
count += 1
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return count
def countLeafNode(self, Root):
if Root is None:
return 0
if Root.left is None and Root.right is None:
return 1
return self.countLeafNode(Root.left) + self.countLeafNode(Root.right)
def main():
bt = BinaryTree()
bt.root = bt.createBT(bt.root)
print("先序遍历:", end=' ')
bt.preOrder(bt.root)
print("\n中序遍历:", end=' ')
bt.middleOrder(bt.root)
print("\n后序遍历:", end=' ')
bt.postOrder(bt.root)
print("\n层次遍历:", end=' ')
bt.levelOrder(bt.root)
x = input("\n请输入要查找的节点的值:")
if bt.findBt(bt.root, x):
print("OK")
else:
print("ERROR")
print("节点数:", bt.countNode(bt.root))
print("叶子节点数:", bt.countLeafNode(bt.root))
if __name__ == '__main__':
main()
```
在主函数中,依次调用各个函数,输出二叉树的遍历结果、查找结果和节点统计结果。您可以根据需要修改节点的值和数量,自己测试一下代码的运行情况。
阅读全文