Python自定义二叉树类

不念不忘少年蓝@ 2022-02-19 08:57 278阅读 0赞

**树的基本术语：**  
**节点（Node）**：是树的基本构成部分。它可以有其他专属名称，称之为“**键（key）**”。 一个节点可能有更多的信息，称之为“**负载（payload）**”。尽管负载信息和树的许多算法并不直接相关，但是它对于树的应用至关重要。

**边（Edge）**：也是树的基本构成部分。边连接两个节点，并表示它们之间存在联系。每个节点（除了根节点）都有且只有一条与其他节点相连的入边（指向该节点的边），每个节点可能有许多条出边（从该节点指向其他节点的边）。

**根节点（Root）**：是树中唯一一个没有入边的节点。

**路径（Path）**：是由边连接起来的节点的有序排列。例如：动物界 → 脊索动物门 → 哺乳动物纲 → 食肉动物目 → 猫科 → 猫属 → 家猫 就是一条路径。

**子节点集（Children）**：当一个节点的入边来自另一个节点时，称前者是后者的子节点。同一个节点的所有子节点构成子节点集。

**父节点（Parent）**：一个节点是其所有出边所连接节点的父节点。

**兄弟节点（Sibling）**：同一个节点的所有子节点互为兄弟节点。

**子树（Subtree）**：是一个父节点的某个子节点的所有边和后代节点所构成的集合。

**叶节点（Leaf Node）**：没有子节点的节点成为称为叶节点。

**层数（Level）**：一个节点的层数是指从根节点到该节点的路径中的边的数目。

**高度（Height）**：树的高度等于所有节点的层数的最大值。

**方法一：通过嵌套的方式实现树结构**

# 生成只有根节点的二叉树列表
    def BinaryTree(r):
    	return [r, [], []]
    
    # 插入左子树
    def insertLeft(root, newBranch):
    	t = root.pop(1)							#获取左子树，左子树索引为1
    	if len(t) > 1:							#若左子树长度大于1，说明左子树有子树
    		root.insert(1, [newBranch, t, []])	#在索引为1的位置(左子树的位置)插入新子树，并将原左子树作为新子树的左子树
    	else:									#说明左子树没有子树，且可能没有左子树的根节点
    		root.insert(1, [newBranch, [], []])	#在索引为1的位置(左子树的位置)插入子树
    	return root
    
    # 插入右子树
    def insertRight(root, newBranch):
    	t = root.pop(2)							#获取右子树，右子树索引为2
    	if len(t) > 1:							#若右子树长度大于1，说明右子树有子树
    		root.insert(2, [newBranch, [], t])	#在索引为2的位置(右子树的位置)插入新子树，并将原右子树作为新子树的右子树
    	else:									#说明右子树没有子树，且可能没有右子树的根节点
    		root.insert(2, [newBranch, [], []])	#在索引为2的位置(右子树的位置)插入子树
    	return root
    
    # 获取根节点值
    def getRootVal(root):
    	return root[0]
    
    # 设置根节点值
    def setRootVal(root, newVal):
    	root[0] = newVal
    
    # 获取左子树
    def getLeftChild(root):
    	return root[1]
    
    # 获取右子树
    def getRightChild(root):
    	return root[2]
    
    r = BinaryTree(3)						#生成只有根节点为3的二叉树列表
    insertLeft(r, 4)						#插入左子树，其根节点为4
    print(r)
    insertLeft(r, 5)						#插入左子树，其根节点为5，并将原左子树作为它的左子树
    print(r)
    insertRight(r, 6)						#插入右子树，其根节点为6
    print(r)
    insertRight(r, 7)						#插入右子树，其根节点为7，并将原右子树作为它的右子树
    print(r)
    l = getLeftChild(r)						#获取根节点的左子树
    print(l)
    setRootVal(l, 9)						#设置根节点的左子树的根节点为9
    print(r)
    insertLeft(l, 11)						#在根节点的左子树中插入左子树，其根节点为11，并将原根节点的左子树的左子树作为它的左子树
    print(r)
    print(getRightChild(getRightChild(r)))	#获取根节点的右子树的右子树

**结果为：**

[3, [4, [], []], []]
    [3, [5, [4, [], []], []], []]
    [3, [5, [4, [], []], []], [6, [], []]]
    [3, [5, [4, [], []], []], [7, [], [6, [], []]]]
    [5, [4, [], []], []]
    [3, [9, [4, [], []], []], [7, [], [6, [], []]]]
    [3, [9, [11, [4, [], []], []], []], [7, [], [6, [], []]]]
    [6, [], []]

**方法二：通过节点和引用实现树结构**

class BinaryTree2(object):
    	def __init__(self, rootObj):
    		self.root = rootObj
    		self.leftChild = None
    		self.rightChild = None
    
    	def insertLeft2(self, newNode):
    		if self.leftChild == None:
    			self.leftChild = BinaryTree2(newNode)
    		else:
    			t = BinaryTree2(newNode)
    			t.leftChild = self.leftChild
    			self.leftChild = t
    
    	def insertRight2(self, newNode):
    		if self.rightChild == None:
    			self.rightChild = BinaryTree2(newNode)
    		else:
    			t = BinaryTree2(newNode)
    			t.rightChild = self.rightChild
    			self.rightChild = t
    
    	def getRightChild2(self):
    		return self.rightChild
    
    	def getLeftChild2(self):
    		return self.leftChild
    
    	def setRootVal2(self, obj):
    		self.root = obj
    
    	def getRootVal2(self):
    		return self.root
    
    r2 = BinaryTree2('a')
    print(r2.getRootVal2())
    print(r2.getLeftChild2())
    r2.insertLeft2('b')
    print(r2.getLeftChild2())
    print(r2.getLeftChild2().getRootVal2())
    r2.insertRight2('c')
    print(r2.getRightChild2())
    print(r2.getRightChild2().getRootVal2())
    r2.getRightChild2().setRootVal2('hello')
    print(r2.getRightChild2().getRootVal2())

**结果为：**

a
    None
    <__main__.BinaryTree2 object at 0x00000000026F06A0>
    b
    <__main__.BinaryTree2 object at 0x00000000026F06D8>
    c
    hello