Mỗi nút được coi là nút gốc của cây trái và phải. Viết một lớp để tạo các nút dễ dàng
class _Node:
#slots are class level member,efficiently allocates memory for instance variables
__slots__='_element','_left','_right'
def __init__[self,element,left=None,right=None]:
# left is not a node, left is the left sub Binary Tree
# right is the right sub Binary Tree
self._element=element
self._left=left
self._right=right
Ở đây chúng tôi viết lớp nhị phân
class BinaryTree:
def __init__[self]:
self._root=None
def make_tree[self,e,left,right]: # left=left-subtree, right=right-subtree
# we start the tree from leaf nodes. since it has no left and right subtrees, left and right null
# x.maketree[B,null,null]=[Q,B,Q] this is node x
# y.maketree[C,null,null]=[Q,C,Q]
# z.maketree[A,x,y] "z" is the parent of "x" and "y"
# each node is the root of the binary tree
# each subtree is also considered to be Binary Tree
self._root=_Node[e,left._root,right._root]
# inorder similar to infix:A+B. visit left first, then root, then right
def inorder[self,troot]:
if troot:
self.inorder[troot._left]
print[troot._element,end=' ']
self.inorder[troot._right]
# preorder similar to prefix. +AB, visit root first,then left, then right
def preorder[self,troot]:
if troot:
print[troot._element,end=' ']
self.preorder[troot._left]
self.preorder[troot._right]
# postorder similar to postfix. left first, then right, then root
def postorder[self,troot]:
if troot:
self.postorder[troot._left]
self.postorder[troot._right]
print[troot._element,end=' ']
# count the number of nodes recursively
# recursive calls break the problem into smallest sub problems
# we are recursively asking each node, how many children does each node have
# if a node does not have any child, we count that node, that is why add +1. x+y+1
def count[self,troot]:
if troot:
x=self.count[troot._left]
print["x",x]
y=self.count[troot._right]
print["y",y]
print["x+y",x+y]
# we add +1 because we have to count the root
return x+y+1
return 0
def height[self,troot]:
if troot:
x=self.height[troot._left]
y=self.height[troot._right]
if x>y:
return x+1
else:
return y+1
return 0
bây giờ tạo cây nhị phân
tạo 6 cây nhị phân phụ
x=BinaryTree[]
y=BinaryTree[]
z=BinaryTree[]
r=BinaryTree[]
s=BinaryTree[]
t=BinaryTree[]
a=BinaryTree[] # null binary tree
đầu tiên tạo các nút lá, 40 và 60
# if a tree has only root node, it is still binary tree
x.make_tree[40,a,a]
y.make_tree[60,a,a]
tạo các nút bên trong
z.make_tree[20,x,a] #left internal
r.make_tree[50,a,y] #right internal
s.make_tree[30,r,a]
t.make_tree[10,z,s]
Cây nhị phân là một cấu trúc dữ liệu phi tuyến tính được sử dụng để tìm kiếm và tổ chức dữ liệu. Cây nhị phân bao gồm các nút. Mỗi nút là một thành phần dữ liệu, một nút con bên trái và nút còn lại là con bên phải. Hãy để chúng tôi đi sâu vào các khái niệm liên quan đến cây cối và triển khai chúng vào ngôn ngữ lập trình Python
Để biết thêm thông tin cơ bản về các loại cấu trúc dữ liệu khác nhau trong Python, hãy xem các bài viết sau
- Giới thiệu về cấu trúc dữ liệu
- Danh sách
- Cây rơm
- Xếp hàng
- Danh sách liên kết
Ghi chú. Điều kiện tiên quyết – Đảm bảo bạn có kiến thức Python cơ bản trước khi đi sâu vào bài viết này. Bạn cũng nên kiểm tra một số cấu trúc dữ liệu tuyến tính. [liên kết được đưa ra ở trên]
Mục lục
cây nhị phân. Giới thiệu
Nhân vật. Cây nhị phân, Nguồn hình ảnh
Một nút cây nhị phân bao gồm các thành phần sau
- Dữ liệu
- Con trỏ tới con trái
- Con trỏ tới con phải
Dưới đây là một số thuật ngữ chính liên quan đến cây nhị phân
- Nút – Đơn vị cơ bản nhất của cây nhị phân
- Gốc - Gốc của nhị phân là phần tử trên cùng. Chỉ có một gốc trong cây nhị phân
- Lá - Lá của cây nhị phân là các nút không có con
- Cấp độ - Cấp độ là thế hệ của nút tương ứng. Nút gốc có cấp 0, nút con của nút gốc ở cấp 1, cháu của nút gốc ở cấp 2, v.v.
- Parent – Cha mẹ của một nút là nút cao hơn một cấp so với nút đó
- Con – Con của một nút là các nút nằm dưới một cấp của nút
Ứng dụng của cây nhị phân
Cây nhị phân là một cấu trúc dữ liệu phân cấp, một hệ thống tệp được tổ chức dưới dạng cây. Cây có thể được sử dụng để tìm kiếm hiệu quả, khi các phần tử được sắp xếp theo thứ tự nhất định. Một số ví dụ bao gồm
Mô hình đối tượng tài liệu HTML/XML được tổ chức dưới dạng cây
Cây cú pháp trừu tượng và Cây phân tích cú pháp được trình biên dịch xây dựng như một phần của quá trình biên dịch
Cây cũng được sử dụng để lập chỉ mục cơ sở dữ liệu hiệu quả
Thực hiện một cây nhị phân
Khởi tạo một lớp nút
Trước tiên chúng ta hãy định nghĩa lớp Node
# The Node Class defines the structure of a Node
class Node:
# Initialize the attributes of Node
def __init__[self, data]:
self.left = None # Left Child
self.right = None # Right Child
self.data = data # Node Data
Khi chúng tôi đã xác định lớp Node, chúng tôi có thể khởi tạo Cây nhị phân của mình
class Node:
def __init__[self, data]:
self.left = None
self.right = None
self.data = data
root = Node[10] # Instantiating the Tree
# Tree Structure
# 10
# / \
# None None
root.left = Node[34] # Setting the left child of the root to 34
root.right = Node[89] # Setting the right child of the root to 89
# Tree Structure
# 10
# / \
# 34 89
# / \ / \
# None None None None
Đi ngang
Vì cây nhị phân là cấu trúc dữ liệu phi tuyến tính nên có nhiều cách để duyệt qua dữ liệu cây. Hãy xem xét các loại truyền tải khác nhau trong cây nhị phân, bao gồm truyền tải theo thứ tự, truyền tải theo thứ tự trước và truyền tải theo thứ tự sau
Truyền đơn đặt hàng
Trong một lần duyệt theo thứ tự, nút con bên trái được truy cập trước, tiếp theo là nút cha, sau đó là nút con bên phải
def inorder[node]:
if node:
# Recursively call inorder on the left subtree until it reaches a leaf node
inorder[node.left]
# Once we reach a leaf, we print the data
print[node.data]
# Now, since the left subtree and the root has been printed, call inorder on right subtree recursively until we reach a leaf node.
inorder[node.right]
# For the tree,
# 10
# / \
# 34 89
# / \ / \
# 20 45 56 54
# Inorder traversal: 20 34 45 10 56 89 54
Truyền tải đặt hàng trước
Trong quá trình truyền tải theo thứ tự trước, nút gốc được truy cập trước, tiếp theo là nút con bên trái, sau đó là nút con bên phải
________số 8
Truyền tải sau khi đặt hàng
Trong quá trình duyệt theo thứ tự sau, nút con bên trái được truy cập trước, tiếp theo là nút con bên phải, sau đó là nút gốc
def postorder[node]:
if node:
# Recursively call postorder on the left subtree until we reach a leaf node.
postorder[node.left]
# Recursively call postorder on the right subtree until we reach a leaf node.
postorder[node.right]
# Print the value of the root node
print[node.data]
# For the tree,
# 10
# / \
# 34 89
# / \ / \
# 20 45 56 54
# Postorder traversal: 20 45 34 56 54 89 10
Thực hành cây nhị phân
Khi bạn đã hiểu các khái niệm cốt lõi của cây nhị phân, hãy thực hành các bộ bài toán dưới đây để củng cố và kiểm tra kiến thức của bạn về cây
Làm phẳng cây nhị phân thành danh sách được liên kết - LeetCode
Tính tổng từ gốc đến số lá - LeetCode
Cây đối xứng - LeetCode
Cây nhị phân - Đại học Carnegie Mellon
Phần kết luận
Việc triển khai cây nhị phân trong Python có thể khá đơn giản, như chúng ta đã thấy với các ví dụ ở trên trong bài viết này. Cây nhị phân được sử dụng rộng rãi trong các ứng dụng và phần mềm và có kiến thức vững chắc về các khái niệm này sẽ giúp bất kỳ nhà phát triển nào có lợi thế trong cuộc phỏng vấn