1. 模型构建
二叉树如下图,是由节点、节点与节点之前的连接组成的,而且连接是有顺序的,一般我们认为左边的次序要优先于右边。
对于每个节点来说,都有一个数据区域存放该节点的信息,另外还需要描述其左右子节点。每个节点的这三个信息确认之后,其实整个树的信息就确认了。
2. 节点结构体定义
typedef struct {
int data;//数据区域
struct BinaryTreeNode* left;//左子节点
struct BinaryTreeNode* right;//右子节点
}BinaryTreeNode;
1
2
3
4
5
非常完美吭,不再解释了。
3. 二叉树的构造与遍历
非常简单啊,从根节点开始逐次构造即可,看代码
#include<stdio.h> /* * 使用链表构造与遍历二叉树 * 作者:熊猫大大 * 时间:2019-12-01 */ #include <stdio.h> typedef struct { int data;//数据区域 struct BinaryTreeNode* left;//左子节点 struct BinaryTreeNode* right;//右子节点 }BinaryTreeNode; //为树的当前节点添加左子节点 int addLeftChild(BinaryTreeNode* curNode, int leftData) { //分配新节点 BinaryTreeNode* leftNode = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode)); //为新节点挂载数据 leftNode->data = leftData; //新节点暂时无子节点 leftNode->left = NULL; leftNode->right = NULL; //将新节点挂到当前节点下 curNode->left = leftNode; return 1; } //为树的当前节点添加右子节点 int addRightChild(BinaryTreeNode* curNode,int rightData) { //分配新节点 BinaryTreeNode* rightNode = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode)); //为新节点挂载数据 rightNode->data = rightData; //新节点暂时无子节点 rightNode->left = NULL; rightNode->right = NULL; //将新节点挂到当前节点下 curNode->right = rightNode; return 1; } //遍历当前节点与子节点 void printTree(BinaryTreeNode *node) { if (node == NULL) { return; } printf("父节点:%d", node->data); printf("----"); BinaryTreeNode* temp = NULL; if (node->left != NULL) { temp = node->left; printf("左:%d", temp->data); } if (node->right != NULL) { temp = node->right; printf("右:%d", temp->data); } printf("\n"); printTree(node->left); printTree(node->right); } //----------------------------------------------------------------------------------------------------测试入口区域 int main() { //设定根节点 BinaryTreeNode root; //根节点 root.data = 1; root.left = NULL; root.right = NULL; addLeftChild(&root, 2); addRightChild(&root, 3); //为2号节点增加子节点 addLeftChild(root.left, 4); addRightChild(root.left, 5); printTree(&root); return 1; }