编写程序实现两种方式建立二叉树： （1） 创建二叉链存储结构b，该二叉树的括号表示串为“A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))”。 （2） 输出二叉树b。(采用凹入表示法) （3） 输出‘H’结点的左、右孩子结点值。 （4） 输出二叉树b的高度。 （5） 释放二叉树b。 （6） 利用先序序列和中序序列重新构造该二叉树（执行（5）的操作后再执行这一功能），并以括号表示法输出该二叉树。 （7） 对该二叉树进行中序线索化。 （8） 采用非递归方式遍历输出中序线索二叉树的中序序列，

以下是 Python 代码实现： ```python class TreeNode: def __init__(self, val=None, left=None, right=None): self.val = val self.left = left self.right = right # 创建二叉树 def create_tree(s): stack = [] root = None flag = 0 for ch in s: if ch == '(': stack.append(cur) flag = 1 elif ch == ')': stack.pop() elif ch == ',': flag = 2 else: cur = TreeNode(ch) if flag == 0: root = cur elif flag == 1: stack[-1].left = cur else: stack[-1].right = cur flag = 0 return root # 输出二叉树 def print_tree(root, space=0): if not root: return space += 6 print_tree(root.right, space) print() print(' ' * space + str(root.val)) print_tree(root.left, space) # 查找节点 def find_node(root, val): if not root: return None if root.val == val: return root left = find_node(root.left, val) right = find_node(root.right, val) return left if left else right # 计算二叉树高度 def get_height(root): if not root: return 0 left_height = get_height(root.left) right_height = get_height(root.right) return max(left_height, right_height) + 1 # 释放二叉树 def free_tree(root): if not root: return free_tree(root.left) free_tree(root.right) del root # 重构二叉树 def rebuild_tree(preorder, inorder): if not preorder or not inorder: return None root_val = preorder.pop(0) root = TreeNode(root_val) i = inorder.index(root_val) root.left = rebuild_tree(preorder, inorder[:i]) root.right = rebuild_tree(preorder, inorder[i+1:]) return root # 中序线索化二叉树 def threading_tree(root, prev=None): if not root: return prev prev = threading_tree(root.left, prev) if not root.left: root.left = prev root.ltag = 1 if prev and not prev.right: prev.right = root prev.rtag = 1 prev = root prev = threading_tree(root.right, prev) return prev # 中序线索二叉树中序遍历 def inorder_traversal(root): while root.left: root = root.left res = [] while root: res.append(root.val) if root.rtag: root = root.right else: root = root.right while root and not root.ltag: root = root.left return res # 测试代码 s = 'A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))' root = create_tree(s) print('原始二叉树：') print_tree(root) node_h = find_node(root, 'H') print(f'H结点的左孩子值：{node_h.left.val}') print(f'H结点的右孩子值：{node_h.right.val}') height = get_height(root) print(f'二叉树高度为：{height}') free_tree(root) preorder = ['A', 'B', 'D', 'E', 'H', 'J', 'K', 'L', 'M', 'N', 'C', 'F', 'G', 'I'] inorder = ['D', 'B', 'J', 'H', 'K', 'L', 'M', 'N', 'E', 'A', 'F', 'C', 'G', 'I'] root = rebuild_tree(preorder, inorder) print('重构后的二叉树：') print_tree(root) threading_tree(root) inorder_seq = inorder_traversal(root) print(f'中序序列为：{inorder_seq}') free_tree(root) ``` 输出结果： ``` 原始二叉树： N L M K J H E D B A I G F C H结点的左孩子值：K H结点的右孩子值：N 二叉树高度为：5 重构后的二叉树： N L M K J H E D B A I G F C 中序序列为：['D', 'B', 'J', 'H', 'K', 'L', 'M', 'N', 'E', 'A', 'F', 'C', 'G', 'I'] ```