Python实现二叉树数据结构程序

树是一种数据结构，由节点组成。节点由边连接。最顶端的节点称为根节点，最底端的节点称为叶节点。叶节点是没有子节点的节点。

二叉树

二叉树是一种树，其中每个节点最多可以包含2个子节点。这意味着每个节点可以有0个、1个或2个子节点，但不能超过2个。二叉树中的每个节点包含三个字段：

  • 数据

  • 指向左子节点的指针

  • 指向右子节点的指针

完全二叉树 - 如果除最后一层外，所有层都已完全填充，并且所有节点都应尽可能靠左，则称二叉树为完全二叉树。

严格/真二叉树 - 如果每个节点都有零个或两个子节点，则称二叉树为严格或真二叉树。

满二叉树 - 如果所有节点都有两个子节点并且所有叶节点都在同一层，则称二叉树为满二叉树。

平衡二叉树 - 如果左子树的高度和右子树的高度之差最多为一(0或1)，则称二叉树为平衡二叉树。

从给定数组构造二叉树

示例

如果根节点位于第i个索引处，则左子节点将位于第(2*i+1)个索引处，右子节点将位于第(2*i-1)个索引处。我们将使用此概念从数组元素构造二叉树。

class TreeNode:
   def __init__(self,data,left=None,right=None):
      self.data=data
      self.left=left
      self.right=right
def insert_into_tree(root,arr,i,l):
   if i<l:
      print(arr[i])
      temp=TreeNode(arr[i])
      root=temp
      root.left=insert_into_tree(root,arr,i*2+1,l)
      root.right=insert_into_tree(root,arr,i*2+2,l)
   return root
arr=[1,2,3,4,5]
i=0
l=len(arr)
root=TreeNode(arr[0])
insert_into_tree(root,arr,i,l)

输出

1
2
4
5
3

更新于：2023年4月24日

浏览量：290

开启您的职业生涯

完成课程获得认证

开始学习
广告