POJ OD360. 计算三叉搜索树的高度
原题链接
简单
作者:
YrMrYu
,
2024-03-21 02:08:59
,
所有人可见
,
阅读 3
class TreeNode:
def __init__(self,val,height=0,left=None,mid=None,right=None):
self.val = val # 节点值
self.height = height # 节点所在高度
self.left = left # 左子树
self.mid = mid # 中子树
self.right = right # 右子树
class Tree:
def __init__(self,root=None,height=0):
self.root = root # 树的根节点
self.height = height# 树的高度
def add(self,val):
node = TreeNode(val)
if self.root is None:
# 如果树是空的,则当前创建的节点将作为根节点
node.height = 1 # 根节点的高度为1
self.root = node
self.height = 1
else:
# 如果树不是空的,则从根节点开始比较
cur = self.root
while True:
# 假设创建的节点node是当前节点cur的子节点,则node节点高度值 = cur节点高度值 + 1
node.height = cur.height + 1
# 如果创建的node进入新层,则更新树的高度
self.height = max(node.height,self.height)
if val < cur.val - 500:
# 如果树小于节点的树减去500,则将树插入cur节点的左子树
if cur.left is None:
# 如果cur节点没有左子树,则node作为cur节点的左子树
cur.left = node
# 停止搜索
break
else:
# 否则继续搜索
cur = cur.left
elif val > cur.val + 500:
# 如果数大于节点的树加上500,则将树插入节点的右子树
if cur.right is None:
cur.right = node
break
else:
cur = cur.right
else:
# 如果树等于节点的树加上500,则将树插入节点的中子树
if cur.mid is None:
cur.mid = node
break
else:
cur = cur.mid
while True:
try:
n = int(input())
nums = list(map(int,input().split()))
tree = Tree()
for num in nums:
tree.add(num)
print(tree.height)
except:
break