Python 实现二叉树数据结构

树是一种由节点组成的数据结构。节点之间通过边连接。最顶部的节点称为根节点，最底部的节点称为叶节点。叶节点是没有任何子节点的节点。

二叉树

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

数据
指向左子节点的指针
指向右子节点的指针

Python 实现二叉树数据结构

完全二叉树 − 如果所有层级除了最后一层都填满了，并且所有的节点都尽可能地靠左，那么二叉树被称为完全二叉树。

严格/正规二叉树 − 如果每个节点要么没有子节点，要么有两个子节点，那么二叉树被称为严格或正规二叉树。

完美二叉树 − 如果所有节点都有两个子节点，并且所有叶子节点在同一层级上，那么二叉树被称为完美二叉树。

平衡二叉树 − 如果左子树的高度和右子树的高度之间的差值最多为一（0或1），那么二叉树被称为平衡二叉树。

从给定数组构建二叉树

Python 实现二叉树数据结构

示例

如果根节点位于第i个索引处，则左子节点将位于(2i+1)个索引处，右子节点将位于(2i-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)