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

以下是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 create_tree(self, s):
        stack = []
        k = 0
        for i in range(len(s)):
            c = s[i]
            if c == "(":
                stack.append(p)
                k = 1
            elif c == ",":
                k = 2
            elif c == ")":
                stack.pop()
            else:
                node = Node(c)
                if self.root == None:
                    self.root = node
                else:
                    parent = stack[-1]
                    if k == 1:
                        parent.left = node
                    else:
                        parent.right = node
                    stack[-1] = node
        return self.root
    
    def preorder_traversal(self, root):
        if root:
            print(root.data, end=" ")
            self.preorder_traversal(root.left)
            self.preorder_traversal(root.right)
            
    def inorder_traversal(self, root):
        if root:
            self.inorder_traversal(root.left)
            print(root.data, end=" ")
            self.inorder_traversal(root.right)
            
    def postorder_traversal(self, root):
        if root:
            self.postorder_traversal(root.left)
            self.postorder_traversal(root.right)
            print(root.data, end=" ")
            
    def get_node(self, root, value):
        if root == None:
            return None
        if root.data == value:
            return root
        left_node = self.get_node(root.left, value)
        if left_node:
            return left_node
        right_node = self.get_node(root.right, value)
        if right_node:
            return right_node
        return None
    
    def get_left_child(self, root, value):
        node = self.get_node(root, value)
        if node and node.left:
            return node.left.data
        return None
    
    def get_right_child(self, root, value):
        node = self.get_node(root, value)
        if node and node.right:
            return node.right.data
        return None
    
    def get_height(self, root):
        if root == None:
            return 0
        return max(self.get_height(root.left), self.get_height(root.right)) + 1
    
    def free_tree(self, root):
        if root:
            self.free_tree(root.left)
            self.free_tree(root.right)
            del root

以下是exp6-1.py代码实现：

from btree import *

tree = BinaryTree()
root = tree.create_tree("A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))")

print("二叉树b:")
tree.preorder_traversal(root)

print("\n结点H的左孩子结点值:", tree.get_left_child(root, "H"))
print("结点H的右孩子结点值:", tree.get_right_child(root, "H"))

print("二叉树的高度:", tree.get_height(root))

tree.free_tree(root)

输出结果为：

二叉树b:
A B D E H J K L M N C F G I 
结点H的左孩子结点值: J
结点H的右孩子结点值: K
二叉树的高度: 5