一、二叉树链式结构的实现 1.1 前置说明 在学习二叉树的基本操作前，需先要创建一棵二叉树，然后才能学习其相关的基本操作。由于现在大家对二叉树结构掌握还不够深入，为了降低大家学习成本，此处手动快速创建一棵简单的二叉树，快速进入二叉树操作学习，等二叉树结构了解的差不多时，我们反过头再来研究二叉树真正的创建方式。 快速创建一棵简单的二叉树 typedef int BTDataType; typedef struct BinaryTreeNode { BTDataType data; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }BTNode; BTNode*BuyNode(BTDataType x) { BTNode* node = (BTNode*)malloc(sizeof(BTNode)); if (node == NULL) { perror("malloc fail"); return NULL; } node->data = x; node->left = NULL; node->right = NULL; return node; } BTNode* CreatBinaryTree() { BTNode* node1 = BuyNode(1); BTNode* node2 = BuyNode(2); BTNode* node3 = BuyNode(3); BTNode* node4 = BuyNode(4); BTNode* node5 = BuyNode(5); BTNode* node6 = BuyNode(6); node1->left = node2; node1->right = node4; node2->left = node3; node4->left = node5; node4->right = node6; return node1; } 注意：上述代码并不是创建二叉树的方式，真正创建二叉树方式后序详解重点讲解。 再看二叉树基本操作前，再回顾下二叉树的概念: 二叉树是： 1.空树 2.非空：根节点，根节点的左子树、根节点的右子树组成的。 从概念中可以看出，二叉树定义是递归式的，因此后序基本操作中基本都是按照该概念实现的。 1.2 二叉树的遍历的时间、空间复杂度 时间复杂度：O(N) 空间复杂度：O(h)—h是高度范围是【logN,N】 1.3 二叉树的遍历 1.3.1 前序、中序以及后序遍历： 学习二叉树结构，最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。 由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。 按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历： 1.3.2 前序遍历: (Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前(根 -> 左子树 -> 右子树)。 代码： void PrevOrder(BTNode* root)//前序 { if (root == NULL) { printf("NULL "); return; } printf("%d ", root->data); PrevOrder(root->left); PrevOrder(root->right ); } 流程图： 结果：1 2 3 NULL NULL NULL 4 5 NULL NULL 6 NULL NULL 1.3.3 后序遍历 (Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后(左子树 -> 右子树 -> 根)。 代码： void PostOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } PostOrder(root->left); PostOrder(root->right); printf("%d ", root->data); } 流程图： 只画了部分，具体和第一个前序一样的流程只不过注意到底是先走哪里 结果：NULL NULL 3 NULL 2 NULL NULL 5 NULL NULL 6 4 1 1.3.4 中序遍历：就不画流程图了具体即上有兴趣可以自己画一下 (Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中间(左子树 -> 根 -> 右子树)。 结果：NULL 3 NULL 2 NULL 1 NULL 5 NULL 4 NULL 6 NULL 代码： void InOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } InOrder(root->left); printf("%d ", root->data); InOrder(root->right); } 1.4 二叉树节点个数 1.4.1 错误示范一(代码)： 代码： void BTreeSzie(BTNode* root) { if (root == NULL) { return; } int size = 0; size++; BTreeSzie(root->left ); BTreeSzie(root->right ); } 流程图： 1.4.2 错误示范二(代码)： 代码： 经过错误示范一想要改进就可能想到static—C语言关键字 虽然解决了size每次调用重定义的错误但是我们并不能拿到size,因为size是局部变量，为了解决这个问题，就可能想到返回值的做法，但是返回值会导致调用多次这个函数时，static一直向后面增加而外面也不能局部变量置零 int BTreeSzie(BTNode* root) { static int size = 0; printf("%p,%d\n", &size,size); if (root == NULL) { return size; } size++; BTreeSzie(root->left ); BTreeSzie(root->right ); return size; } 流程图: 通过打印size的地址和值可以得知static解决了错误示范一中的问题 但是出现多次调用还是会出现累加现象同时不能在下一次调用这个函数时将size置零，因为它是一个局部变量。 1.4.3 正确代码第一种(方式)：定义全局变量 代码： int size = 0; void BTreeSzie(BTNode* root) { if (root == NULL) { return size; } size++; BTreeSzie(root->left); BTreeSzie(root->right); return size; } 流程图: 1.4.4 正确代码第二种(方式)： 代码： int BTreeSzie(BTNode* root) { return root == NULL ? 0 : BTreeSzie(root->left) + BTreeSzie(root->right) + 1; } 流程图: 二、全部代码： #define _CRT_SECURE_NO_WARNINGS 1 #include #include #include typedef int BTDataType; typedef struct BinaryTreeNode { BTDataType data; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }BTNode; BTNode*BuyNode(BTDataType x) { BTNode* node = (BTNode*)malloc(sizeof(BTNode)); if (node == NULL) { perror("malloc fail"); return NULL; } node->data = x; node->left = NULL; node->right = NULL; return node; } BTNode* CreatBinaryTree() { BTNode* node1 = BuyNode(1); BTNode* node2 = BuyNode(2); BTNode* node3 = BuyNode(3); BTNode* node4 = BuyNode(4); BTNode* node5 = BuyNode(5); BTNode* node6 = BuyNode(6); node1->left = node2; node1->right = node4; node2->left = node3; node4->left = node5; node4->right = node6; return node1; } void PrevOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } printf("%d ", root->data); PrevOrder(root->left); PrevOrder(root->right); } void InOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } InOrder(root->left); printf("%d ", root->data); InOrder(root->right); } void PostOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } PostOrder(root->left); PostOrder(root->right); printf("%d ", root->data); } //二叉树节点个数 --- 遍历计数 //int size = 0; //void BTreeSzie(BTNode* root) //{ // if (root == NULL) // { // return size; // } // size++; // BTreeSzie(root->left); // BTreeSzie(root->right); // return size; //} //int BTreeSzie(BTNode* root) //{ // static int size = 0; // //printf("%p,%d\n", &size,size); // if (root == NULL) // { // return size; // } // size++; // BTreeSzie(root->left ); // BTreeSzie(root->right ); // return size; //} int BTreeSzie(BTNode* root) { return root == NULL ? 0 : BTreeSzie(root->left) + BTreeSzie(root->right) + 1; } int main() { BTNode* root = CreatBinaryTree(); PrevOrder(root); printf("\n"); InOrder(root); printf("\n"); PostOrder(root); printf("\n"); //printf("BTreeSize:%d\n", BTreeSzie(root)); //printf("BTreeSize:%d\n", BTreeSzie(root)); //printf("BTreeSize:%d\n", BTreeSzie(root)); /*BTreeSzie(root); printf("BTreeSize:%d\n", size); size = 0; BTreeSzie(root); printf("BTreeSize:%d\n", size); size = 0; BTreeSzie(root); printf("BTreeSize:%d\n", size);*/ printf("BTreeSize:%d\n", BTreeSzie(root)); return 0; } 总结 Ending,今天的链式二叉树的内容就到此结束啦~，如果后续想了解更多，就请关注我吧。