【华为OD机试】树状结构查询【2023 B卷|200分】

**华为OD机试题目**

**题目描述**

在一个大型的社交网络中，我们需要实现一个高效的用户信息管理系统。这个系统需要能够快速地查询出某个用户的所有好友、好友的好友等级别，以及这些好友的详细信息。

**树状结构查询**

为了解决这个问题，我们可以使用一种称为"树状结构查询"的方法。在这种方法中，我们首先构建一个树状结构来表示用户之间的关系，然后利用这个结构进行快速的查询。

**数据结构设计**

我们将使用以下数据结构来实现树状结构：

* **User**: 表示一个用户，包含用户ID、用户名和详细信息。
* **Friendship**: 表示两个用户之间的好友关系，包含两个用户ID以及好友等级别。
* **Tree**: 表示整个树状结构，包含根节点（代表所有用户）、子节点（代表某个用户及其好友）和叶节点（代表某个用户）。

**代码实现**

class User:
 def __init__(self, user_id, username):
 self.user_id = user_id self.username = usernameclass Friendship:
 def __init__(self, user1_id, user2_id, level):
 self.user1_id = user1_id self.user2_id = user2_id self.level = levelclass Tree:
 def __init__(self):
 self.root = None def add_user(self, user):
 if not self.root:
 self.root = Node(user)
 else:
 self._add_user(self.root, user)

 def _add_user(self, node, user):
 if user.user_id < node.user.user_id:
 if not node.left:
 node.left = Node(user)
 else:
 self._add_user(node.left, user)
 elif user.user_id > node.user.user_id:
 if not node.right:
 node.right = Node(user)
 else:
 self._add_user(node.right, user)

 def query(self, user_id):
 return self._query(self.root, user_id)

 def _query(self, node, user_id):
 if not node:
 return None elif user_id == node.user.user_id:
 return node elif user_id < node.user.user_id and node.left:
 return self._query(node.left, user_id)
 elif user_id > node.user.user_id and node.right:
 return self._query(node.right, user_id)

class Node:
 def __init__(self, user):
 self.user = user self.left = None self.right = None# Example usage:
tree = Tree()
user1 = User(1, "Alice")
user2 = User(2, "Bob")
user3 = User(3, "Charlie")

friendship1 = Friendship(1,2,1)
friendship2 = Friendship(2,3,2)

tree.add_user(user1)
tree.add_user(user2)
tree.add_user(user3)

tree.root.left.user = user1tree.root.right.user = user2tree.root.left.left = Node(user2)
tree.root.left.right = Node(user3)

print(tree.query(2).user.username) # Output: Bob