"""
二叉搜索树定义：
1,每个节点上都有数据
2,当前节点的左节点数据比当前节点的数据小，并且当前节点的所有左节点数据都比当前节点的数据小
3,当前节点的右节点数据比当前节点的数据大，并且当前节点的所有右节点数据都比当前节点的数据大
"""
class Tree:
def __init__(self):
self.root = None
self.list_data = []
def insert(self, data):
if self.root is None:
self.root = Node(data)
return
current_node = self.root
while current_node is not Node:
if current_node.data == data: # 这个数据已经在里面则跳出
return
elif data > current_node.data: # 当前这个节点的值小于需要插入的值
if current_node.right is None: # 如果右节点为空插入这个节点数据
current_node.right = Node(data)
else: # 不为空的时候需要继续比较下一级
current_node = current_node.right
else: # 当前节点的数据大于需要插入的数据
if current_node.left is None:
current_node.left = Node(data)
else:
current_node = current_node.left
def get_tree_data(self):
self.print_node_data(self.root)
def print_node_data(self, node):
if node.left is not None:
self.print_node_data(node.left)
self.list_data.append(node.data)
if node.right is not None:
self.print_node_data(node.right)
def print_tree(self, list_type=0): # 遍历输出这颗树
self.print_node(self.root, list_type)
def print_node(self, node, list_type):
if list_type == 0: # 前序遍历
if node.left is not None:
self.print_node(node.left, list_type)
print(node.data)
if node.right is not None:
self.print_node(node.right, list_type)
elif list_type == 1: # 前序遍历
print(node.data)
if node.left is not None:
self.print_node(node.left, list_type)
if node.right is not None:
self.print_node(node.right, list_type)
elif list_type == 2: # 后序遍历
if node.left is not None:
self.print_node(node.left, list_type)
if node.right is not None:
self.print_node(node.right, list_type)
print(node.data)
# 判断是否是一颗二叉树
def is_tree(self):
return self.is_tree_detail(self.root)
def is_tree_detail(self, node):
flag = True
if node is None:
return flag
# 处理当前节点的左子树
if node.left is not None:
if node.left.data > node.data:
return False
else:
if self.is_fit(node.data, node.left) is False:
return False
# 处理当前节点的右子树
if node.right is not None:
if node.right.data < node.data:
return False
else:
if self.is_fit(node.data, node.right, 1) is False:
return False
# 处理当前节点的左节点
if self.is_tree_detail(node.left) is False:
return False
# 处理当前节点的右节点
if self.is_tree_detail(node.right) is False:
return False
return flag
def is_fit(self, data, node, type=0):
flag = True
if type == 0: # type=0表示在比较左子树
if node.left is not None:
if data < node.left.data:
return False
else:
if self.is_fit(data, node.left) is False:
return False
if node.right is not None:
if data < node.right.data:
return False
else:
if self.is_fit(data, node.right) is False:
return False
else: # 等于1表示在比较右子树
if node.left is not None:
if data > node.left.data:
return False
else:
if self.is_fit(data, node.left, type) is False:
return False
if node.right is not None:
if data > node.right.data:
return False
else:
if self.is_fit(data, node.right, type) is False:
return False
return flag
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def get_node(data, node_id):
if node_id == 0:
return None
for x in data:
if x[0] == node_id:
# print('get_node:node_id：{}'.format(node_id), x[1])
node = Node(x[1])
node.left = get_node(data, x[2])
node.right = get_node(data, x[3])
return node
return None
def main():
n = int(input())
data = [[int(i) for i in input().split()] for j in range(n)] # 一次性读入所有的数据
# print(data)
# 存储二叉树
tree = Tree()
for i in range(n):
x = data[i]
if x[0] == 1:
node = Node(x[1])
node.left = get_node(data, x[2])
node.right = get_node(data, x[3])
tree.root = node
# tree.print_tree()
# 如果是一颗二叉树的，那么得到的数据和排序后输出的数据肯定是一致的
# flag = True
flag = tree.is_tree()
if flag:
print('T')
else:
print('F')
return
if __name__ == '__main__':
main()
网友评论