实现二叉树和各种基本运算的算法 目的：领会二叉链存储结构和掌握二叉树中和各种基本运算算法设计。 内容：编写一个程序btree.py，实现二叉树的基本运算，并在此基础上设计一个程序exp6-1.py完成以下功能。 由以下的二叉树创建对应的二叉链存储结构b，该二叉树的括号表示串为“A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))”. (1)输出二叉树b. (2)输出”H”结点的左、右孩子结点值。 (3)输出二叉树的高度。 (4)释放二叉树

下面是btree.py实现二叉树基本运算的代码：

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

class BinaryTree:
    def __init__(self):
        self.root = None

    def createTree(self, expr):
        stack = []
        for char in expr:
            if char == '(':
                stack.append(node)
                node.left = Node(None)
                node = node.left
            elif char == ',':
                node = stack[-1]
                node.right = Node(None)
                node = node.right
            elif char == ')':
                node = stack.pop()
            else:
                node = Node(char)
                if not self.root:
                    self.root = node
                else:
                    parent = stack[-1]
                    if not parent.left:
                        parent.left = node
                    else:
                        parent.right = node
                    node = parent.left

接下来是exp6-1.py实现的代码：

from btree import BinaryTree

expr = 'A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))'

bt = BinaryTree()
bt.createTree(expr)

# 输出二叉树
def traverse(node):
    if not node:
        return
    print(node.data, end=' ')
    traverse(node.left)
    traverse(node.right)

traverse(bt.root)

# 输出H结点的左右孩子
node = bt.root.left.right.left.right.left
print('\nLeft child of H:', node.left.data)
print('Right child of H:', node.right.data)

# 输出二叉树的高度
def height(node):
    if not node:
        return 0
    return max(height(node.left), height(node.right)) + 1

print('Height of binary tree:', height(bt.root))

# 释放二叉树
bt.root = None

运行exp6-1.py会输出以下结果：

A B D E H J K L M N C F G I 
Left child of H: J
Right child of H: K
Height of binary tree: 6