当前位置：首页 > news >正文

python二叉树链树_树的链式存储结构

news 来源：原创 2024/5/10 7:03:51

二叉链树是一种树状数据结构，其中每个节点最多有两个子节点，分别称为左子节点和右子节点。每个节点包含一个数据元素和指向其左右子节点的指针。二叉链树可以是空树，也可以是具有以下特点的非空树：
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