2022年 11月 7日

使用Python语言来实现二叉树

最近Leetcode的每日一题总是会出现跟树有关的题，因此最近学习一下用Python实现二叉树。

首先，我们可以使用嵌套列表来表示二叉树，形式如下。

[Root，Left，Right]

 

下面我们介绍一些函数来介绍：

第一个函数，创建二叉树：

  1. def BinaryTree(r):  # 创建二叉树
  2.     return [r, [], []]

第二个函数，插入左节点：

  1. def insertLeft(root, newBranch):  # 插入左节点
  2.     t = root.pop(1)
  3.     if len(t) > 1:
  4.         root.insert(1, [newBranch, t, []])
  5.     else:
  6.         root.insert(1, [newBranch, [], []])
  7.     return root

第三个函数，插入右节点：

还有一些次要的函数：

  1. def getRootVal(root):  # 得到根结点的值
  2.     return root[0]
  3.  
  4.  
  5. def setRootVal(root, newVal):  # 重置根结点的值
  6.     root[0] = newVal
  7.  
  8.  
  9. def getLeftChild(root):  # 得到左子树
  10.     return root[1]
  11.  
  12.  
  13. def getRightChild(root):  # 得到右子树
  14.     return root[2]

其次，我们可以使用链表来表示二叉树。

下面，我们看一下代码(功能在注释中) 。

  1. class BinaryTree:
  2.     def __init__(self, rootObj):  # 创建树的根节点
  3.         self.key = rootObj
  4.         self.leftChild = None
  5.         self.rightChild = None
  6.  
  7.     def insertLeft(self, newNode):  # 插入左子节点
  8.         if self.leftChild == None:
  9.             self.leftChild = BinaryTree(newNode)
  10.         else:
  11.             t = BinaryTree(newNode)
  12.             t.leftChild = self.leftChild
  13.             self.leftChild = t
  14.  
  15.     def insertRight(self, newNode):  # 插入右子节点
  16.         if self.rightChild == None:
  17.             self.rightChild = BinaryTree(newNode)
  18.         else:
  19.             t = BinaryTree(newNode)
  20.             t.rightChild = self.rightChild
  21.             self.rightChild = t
  22.  
  23.     def getRightChild(self):  # 得到右子节点
  24.         return self.rightChild
  25.  
  26.     def getLeftchild(self):  # 得到左子节点
  27.         return self.leftChild
  28.  
  29.     def setRootVal(self, obj):  # 更换根节点
  30.         self.key = obj
  31.  
  32.     def getRootVal(self):  # 得到根节点
  33.         return self.key