二叉树算法实现

一：二叉链表的建立和遍历

例，建立如图所示二叉链表：

# 定义结点类
class BNode:
	def __init__(self,data=None,lchild=None,rchild=None):
		self.data = data
		self.lchild = lchild
		self.rchild = rchild

# 先序遍历函数
def preorder(T):
	if T == None:
		return 
	print(T.data, end="")
	preorder(T.lchild)
	preorder(T.rchild)

# 中序遍历
def inorder(T):
	if T == None:
		return
	inorder(T.lchild)
	print(T.data, end="")
	inorder(T.rchild)

# 后序遍历
def finalorder(T):
	if T == None:
		return
	finalorder(T.lchild)
	finalorder(T.rchild)
	print(T.data, end="")

if __name__ == '__main__':
	# 实例化结点
	a = BNode("A")
	b = BNode("B")
	c = BNode("C")
	d = BNode("D")
	a.lchild = b
	a.rchild = c
	b.rchild = d
    # 先序遍历二叉树
	preorder(a)
	print()
    # 中序遍历二叉树
	inorder(a)
	print()
    # 后序遍历二叉树
	finalorder(a)

如果结点很多，我们可以通过循环或递归的方式来创建结点

# 定义结点类
class BNode:
	def __init__(self,data=None,lchild=None,rchild=None):
		self.data = data
		self.lchild = lchild
		self.rchild = rchild

# 先序遍历函数
def preorder(T):
	if T == None:
		return 
	print(T.data, end="")
	preorder(T.lchild)
	preorder(T.rchild)

# 中序遍历
def inorder(T):
	if T == None:
		return
	inorder(T.lchild)
	print(T.data, end="")
	inorder(T.rchild)

# 后序遍历
def finalorder(T):
	if T == None:
		return
	finalorder(T.lchild)
	finalorder(T.rchild)
	print(T.data, end="")

# 递归创建二叉树
def createBT():
	ch = input("输入一个结点数据，*表示空")
	if ch == "*":
		return None
	else:
		T = BNode(ch)
		T.lchild = createBT()
		T.rchild = createBT()
	return T

if __name__ == '__main__':
	# 创建二叉树，如上图二叉树，输入顺序为：A B * D * * C * *
	T = createBT()
	# 先序遍历二叉树
	preorder(T)
	print()
	# 中序遍历二叉树
	inorder(T)
	print()
	# 后序遍历二叉树
	finalorder(T)

统计叶子结点数

# 定义结点类
class BNode:
	def __init__(self,data=None,lchild=None,rchild=None):
		self.data = data
		self.lchild = lchild
		self.rchild = rchild
	
    
# 递归创建二叉树
def createBT():
	ch = input("输入一个结点数据，*表示空")
	if ch == "*":
		return None
	else:
		T = BNode(ch)
		T.lchild = createBT()
		T.rchild = createBT()
	return T
	
	
# 统计叶子结点数
def countleaf(T):
	if T == None:
		return None
	else:
		if T.lchild == None and T.rchild == None:
			global n
			n += 1
		countleaf(T.lchild)
		countleaf(T.rchild)
		
		
if __name__ == '__main__':
	# 创建二叉树，如上图二叉树，输入顺序为：A B * D * * C * *
	T = createBT()
	# 定义计数器
	n = 0
	countleaf(T)
	print(n)

查找元素

# 定义结点类
class BNode:
	def __init__(self,data=None,lchild=None,rchild=None):
		self.data = data
		self.lchild = lchild
		self.rchild = rchild
		
# 递归创建二叉树
def createBT():
	ch = input("输入一个结点数据，*表示空")
	if ch == "*":
		return None
	else:
		T = BNode(ch)
		T.lchild = createBT()
		T.rchild = createBT()
	return T

# 查找元素
def searchdata(T, ch):
	if T == None:
		return None
	if T.data == ch:
		return T
	else:
		p = searchdata(T.lchild, ch)
		if p != None:
			return p
		p = searchdata(T.rchild, ch)
		if p != None:
			return p


if __name__ == '__main__':
	# 创建二叉树
	T = createBT()
	# 查找元素
	ch = input("请输入查找元素：")
	ret = searchdata(T, ch)
	if ret != None:
		print("元素存在")
	else:
		print("元素不存在")

二：二叉树的类表存储

为什么可以使用列表来存放二叉树？

• 二叉树是递归定义的
• python列表也是递归定义的

步骤如下：

• 空树用None表示
• 非空树用包含三个元素的列表[data,lchild,rchild]表示

把一棵树映射到一种分层的list结构，每棵二叉树都有与之对应的列表

以如下二叉树为例：

它的list结构为：[“A”,[“B”,None,“D”,None,None]],[“C”,None,None]]

# 先序遍历
def preorder(T):
    if T == None:
        return
    print(T[0])
    preorder(T[1])
    preorder(T[2])

# 中序遍历
def inorder(T):
    if T == None:
        return
    inorder(T[1])
    print(T[0])
    inorder(T[2])
    
# 后序遍历
def finalorder(T):
    if T == None:
        return
    finalorder(T[1])
    finalorder(T[2])
    print(T[0])

if __name__ == '__main__':
    t = ["A",["B",None,["D",None,None]],["C",None,None]]
    preorder(t)
    inorder(t)
    finalorder(t)

创建二叉列表，以上图为例：

class BinTreeLink:
    def __init__(self, data, lchild=None, rchild=None):
        self.btree = [data, lchild, rchild]

    # 判断是否为空
    def is_empty(self):
        return self.btree[0] is None

    # 建立左子树
    def set_lchild(self, lchild):
        if self.is_empty():
            return
        self.btree[1] = lchild.btree

    # 建立右子树
    def set_rchild(self, rchild):
        if self.is_empty():
            return
        self.btree[2] = rchild.btree

if __name__ == '__main__':
    a = BinTreeLink("A")
    b = BinTreeLink("B")
    c = BinTreeLink("C")
    d = BinTreeLink("D")
    a.set_lchild(b)
    a.set_rchild(c)
    b.set_rchild(d)
    print(a.btree)

三：二叉树非递归中序遍历

​ 要实现非递归中序遍历算法，二叉树的列表存储方式必须为为链表存储。首先要建立二叉链表，然后利用栈来进行中序遍历。

以下图为例：

# 定义栈
class sstack:
    def __init__(self):
        self.slist = []

    # 判断栈是否为空
    def is_empty(self):
        if self.slist == []:
            return 1
        else:
            return 0

    # 压栈
    def pushstack(self, item):
        self.slist.append(item)

    # 出栈
    def popstack(self):
        return self.slist.pop()

class BNode:
    def __init__(self, data=None, lchild=None, rchild=None):
        self.data = data
        self.lchild = lchild
        self.rchild = rchild

# 中序遍历
def inOrder(T):
    p = T
    s = sstack()
    while p != None or s.is_empty() != 1:
        while p != None:
            s.pushstack(p)
            p = p.lchild
        if s.is_empty() != 1:
            p = s.popstack()
            print(p.data)
            p = p.rchild


if __name__ == '__main__':
    a = BNode("A")
    b = BNode("B")
    c = BNode("C")
    d = BNode("D")
    a.lchild = b
    a.rchild = c
    b.rchild = d
    inOrder(a)

四：哈夫曼树的建立

构建如下哈夫曼树：

# 节点创建
class HuffmanNode:
    def __init__(self, data):
        self.data = data
        self.lchild = None
        self.rchild = None
        self.parent = None

# 构建哈夫曼树
def creatHuffmanTree(hufnode):
    nodelist = hufnode[:]
    while len(nodelist) > 1:
        nodelist.sort(key=lambda item:item.data)
        left = nodelist.pop(0)
        right = nodelist.pop(0)
        father = HuffmanNode(left.data + right.data)
        father.lchild = left
        father.rchild = right
        left.parent = father
        right.parent = father
        nodelist.append(father)
    return nodelist[0]

# 先序遍历
def preorder(T):
    if T == None:
        return
    print(T.data)
    preorder(T.lchild)
    preorder(T.rchild)

if __name__ == '__main__':
    hufnode = []
    while True:
        a = int(input("请输入叶子节点的权值，输入-1结束"))
        if a == -1:
            break
        hufnode.append(HuffmanNode(a))
    bt = creatHuffmanTree(hufnode)
    preorder(bt)

五：哈夫曼编码的实现

例：已知一段码文出现4个字符{T,;,A,C}，出现的概率为{7,5,2,4}，使用哈夫曼编码的方式对这4个字符进行编码。

过程：

​ (1) 遍历nodelis，从第一个叶子结点开始回退

​ (2) 遇到左分支设置为0，遇到右分支设置为1

​ (3) 直到回退到根结点，再去找下一个叶子结点。

class HuffmanNode:
    def __init__(self, data):
        self.data = data
        self.lchild = None
        self.rchild = None
        self.parent = None

def creatHuffmanTree(hufnode):
    nodelist = hufnode[:]
    while len(nodelist) > 1:
        nodelist.sort(key=lambda item:item.data)
        left = nodelist.pop(0)
        right = nodelist.pop(0)
        father = HuffmanNode(left.data + right.data)
        father.lchild = left
        father.rchild = right
        left.parent = father
        right.parent = father
        nodelist.append(father)
    return nodelist[0]

# 哈夫曼编码
def hufEncode(hufnode, root):
    encode = [""] * len(hufnode)
    for i in range(len(hufnode)):
        node = hufnode[i]
        while node != root:
            if node.parent.lchild == node:
                encode[i] = "0" + encode[i]
            else:
                encode[i] = "1" + encode[i]
            node = node.parent
    return encode