PTA\6-2 二叉树 - 2. 创建

### 创建二叉树 为了创建一个适用于 PTA 平台练习题 6-2 的二叉树，可以基于给定的数据结构定义来构建。这里采用的是 C/C++ 编程语言中的指针和结构体概念。 #### 数据结构定义 首先定义二叉树节点 `TNode` 结构以及指向该类型的指针： ```c typedef struct TNode *Position; typedef Position BinTree; struct TNode { ElementType Data; /* 存储元素 */ BinTree Left; /* 左子树 */ BinTree Right; /* 右子树 */ }; ``` 此部分描述了基本的二叉树节点构成方式[^3]。 #### 构建函数 接着编写用于创建新节点并初始化其成员变量的辅助函数 `MakeTreeNode()` 和将两个现有节点连接到父节点下的 `AttachToBT()`. ```c /* 动态分配内存空间以建立新的二叉树节点 */ BinTree MakeTreeNode(ElementType X) { BinTree Node = (BinTree)malloc(sizeof(struct TNode)); if (!Node) exit(-1); // 如果申请失败则退出程序 Node->Data = X; Node->Left = NULL; Node->Right = NULL; return Node; } /* 将左右两棵子树附加至根节点下形成完整的二叉树 */ void AttachToBT(BinTree Parent, BinTree LChild, BinTree RChild){ Parent->Left=LChild; Parent->Right=RChild; } ``` 上述代码片段展示了如何通过动态内存分配的方式实例化一个新的二叉树节点，并提供了方法将其左孩子和右孩子分别设置为指定的子树[^4]. #### 示例应用 假设现在要按照特定顺序输入一系列整数值作为二叉树各层次上的节点值，可以通过递归调用来完成整个过程: ```c #include <stdio.h> #include <stdlib.h> // ... 上述定义 ... int main(){ int N,i,x; scanf("%d",&N); BinTree Root=NULL; while(N--){ scanf("%d", &x); // 这里简化处理逻辑，实际应根据具体题目要求调整 BinTree NewNode=MakeTreeNode(x); if(!Root){ Root=NewNode; }else{ // 此处省略具体的插入位置判断逻辑... // 需要考虑按层序或先序等方式添加节点 } } // 输出测试：中序遍历打印所有节点 printf("In-order Traversal:\n"); InorderTraversal(Root); free(Root); // 记得释放资源 return 0; } ``` 这段伪代码框架说明了一个简单的流程——读取用户输入的一系列数字，依次加入到正在形成的二叉树当中；最后执行一次中序遍历来验证结果是否正确. 实际操作时需依据具体需求设计更精确的插入策略。