二叉鏈樹是一種樹狀數據結構，其中每個節點最多有兩個子節點，分別稱為左子節點和右子節點。每個節點包含一個數據元素和指向其左右子節點的指針。二叉鏈樹可以是空樹，也可以是具有以下特點的非空樹：
1. 每個節點最多有兩個子節點。
2. 左子節點和右子節點的順序是固定的，即左子節點始終位于父節點的左側，右子節點始終位于父節點的右側。
3. 每個節點的子節點也可以是空節點，表示該節點沒有對應的子節點。

二叉鏈樹常用于實現二叉搜索樹、堆、表達式樹等數據結構和算法。

廣度優先遍歷：

二叉樹的廣度優先遍歷（BFS）是從樹的根節點開始，按照層次的順序依次訪問每一層的節點，直到遍歷完整棵樹為止。具體步驟如下：

1. 首先將根節點入隊列。
2. 從隊列中取出一個節點，訪問該節點，并將其所有子節點依次入隊列。
3. 重復步驟2，直到隊列為空。

在遍歷過程中，節點的訪問順序是按照從上到下、從左到右的順序進行的。通過這種方式，可以逐層地訪問二叉樹的所有節點，實現廣度優先遍歷。

    def breadth_travel(self):"""廣度遍歷"""if self.root == None:returnqueue=[self.root]while queue:cur_node = queue.pop(0)print(cur_node.data,end=" ")if cur_node.lchild is not None:queue.append(cur_node.lchild)if cur_node.rchild is not None:queue.append(cur_node.rchild)

先序遍歷：

二叉樹的先序遍歷（preorder traversal）是一種深度優先遍歷方式，具體步驟如下：

1. 訪問根節點。
2. 遞歸地對根節點的左子樹進行先序遍歷。
3. 遞歸地對根節點的右子樹進行先序遍歷。

在遍歷過程中，節點的訪問順序是根節點、左子樹、右子樹。通過先序遍歷，可以按照根節點、左子樹、右子樹的順序訪問二叉樹的所有節點。

    def preorder(self, root):"""先序遍歷"""if root is None:returnprint(root.data, end=" ")self.preorder(root.lchild)self.preorder(root.rchild)

中序遍歷：

二叉樹的中序遍歷（inorder traversal）是一種深度優先遍歷方式，具體步驟如下：

1. 遞歸地對根節點的左子樹進行中序遍歷。
2. 訪問根節點。
3. 遞歸地對根節點的右子樹進行中序遍歷。

在遍歷過程中，節點的訪問順序是左子樹、根節點、右子樹。通過中序遍歷，可以按照左子樹、根節點、右子樹的順序訪問二叉樹的所有節點。

    def inorder(self, root):"""中序遍歷"""if root is None:returnself.inorder(root.lchild)print(root.data, end=" ")self.inorder(root.rchild)

?后續遍歷：

二叉樹的后序遍歷（postorder traversal）是一種深度優先遍歷方式，具體步驟如下：

1. 遞歸地對根節點的左子樹進行后序遍歷。
2. 遞歸地對根節點的右子樹進行后序遍歷。
3. 訪問根節點。

在遍歷過程中，節點的訪問順序是左子樹、右子樹、根節點。通過后序遍歷，可以按照左子樹、右子樹、根節點的順序訪問二叉樹的所有節點。

    def postorder(self, root):"""后序遍歷"""if root is None:returnself.postorder(root.lchild)self.postorder(root.rchild)print(root.data, end=" ")

全部代碼：?

class Node:def __init__(self,data):self.data = dataself.lchild = Noneself.rchild = None
class Tree:def __init__(self):self.root = Nonedef add(self,data):node = Node(data)if self.root is None:self.root = nodereturnqueue = [self.root]while queue:cur_node = queue.pop(0)if cur_node.lchild is None:cur_node.lchild = nodereturnelse:queue.append(cur_node.lchild)if cur_node.rchild is None:cur_node.rchild = nodereturnelse:queue.append(cur_node.rchild)def breadth_travel(self):"""廣度遍歷"""if self.root == None:returnqueue=[self.root]while queue:cur_node = queue.pop(0)print(cur_node.data,end=" ")if cur_node.lchild is not None:queue.append(cur_node.lchild)if cur_node.rchild is not None:queue.append(cur_node.rchild)def preorder(self, root):"""先序遍歷"""if root is None:returnprint(root.data, end=" ")self.preorder(root.lchild)self.preorder(root.rchild)def inorder(self, root):"""中序遍歷"""if root is None:returnself.inorder(root.lchild)print(root.data, end=" ")self.inorder(root.rchild)def postorder(self, root):"""后序遍歷"""if root is None:returnself.postorder(root.lchild)self.postorder(root.rchild)print(root.data, end=" ")def no_preorder(self,root):"""非遞歸的先序遍歷"""if root==None:returnalist=[root]while alist:cur=alist.pop()print(cur.data)if cur.rchild != None:alist.append(cur.rchild)if cur.lchild != None:alist.append(cur.lchild)def no_inorder(self,root):cur=rootalist=[]while cur or alist:if cur!=None:alist.append(cur)cur=cur.lchildelse:cur=alist.pop()print(cur.data)cur=cur.rchild