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

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

二叉树

二叉树是一种树，在其中每个节点最多可以包含2个子节点。也就是说，每个节点可以有0个、1个或2个子节点，但不会超过2个。二叉树中的每个节点都包含三个字段：

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

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

完全二叉树 – 如果所有层都完全填充，除了最后一层之外，并且所有节点尽可能保持在左侧，则称为完全二叉树。

严格/正式的二叉树 – 如果每个节点只具有零或两个孩子，则称为严格或正式的二叉树。

完美二叉树 – 如果所有节点都有两个孩子，所有叶节点处于同一层，则该二叉树称为完美二叉树。

平衡二叉树 – 如果左子树的高度与右子树的高度之间的差最多为1，则称该二叉树为平衡二叉树（0或1）。

从给定的数组构建二叉树

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

例子

如果根节点在第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)