二叉树结点的结构体
包含指向左右子树的指针,和一个数据
1. typedef struct MyTreeNode 2. { 3. struct MyTreeNode* left; //左孩子 4. struct MyTreeNode* right; //右孩子 5. int data; 6. }MyTreeNode;
创建一棵二叉树
创建一颗二叉树,其节点关系以及每个结点的数据如图所示
代码如下
1. { 2. MyTreeNode t[15]; 3. 4. for (i = 0; i < 15; i++) 5. { 6. memset(&t[i], 0, sizeof(MyTreeNode)); //没有孩子的应指向NULL 7. t[i].data = i + 1; 8. } 9. 10. //建立关系 11. t[0].left = &t[1]; 12. t[0].right = &t[7]; 13. t[1].left = &t[2]; 14. t[2].left = &t[3]; 15. t[2].right = &t[4]; 16. t[4].left = &t[5]; 17. t[5].right = &t[6]; 18. t[7].right = &t[8]; 19. t[8].right = &t[14]; 20. t[8].left = &t[9]; 21. t[9].left = &t[10]; 22. t[9].right = &t[11]; 23. t[11].left = &t[12]; 24. t[11].right = &t[13]; 25. }
二叉树的前序遍历
前序遍历是指,先访问根结点,然后访问左子树根节点,然后访问右子树根结点(根-左-右)。通过递归调用实现前序遍历算法的C语言代码如下:
1. void preorder_traversal(MyTreeNode* tree) 2. { 3. if (tree == NULL) 4. { 5. //叶子结点指向NULL则返回 6. return; 7. } 8. printf("%d ", tree->data); 9. preorder_traversal(tree->left); 10. preorder_traversal(tree->right); 11. }
前序遍历算法的测试结果:
中序遍历
先访问左子树根结点,然后访问根结点,最后访问右子树根结点(左-根-右)。通过递归调用实现中序遍历算法的C语言代码如下:
1. void inorder_traversal(MyTreeNode* tree) 2. { 3. if (tree == NULL) 4. { 5. return; 6. } 7. inorder_traversal(tree->left); 8. printf("%d ", tree->data); 9. inorder_traversal(tree->right); 10. }
中序遍历算法的测试结果:
后序遍历
先访问左子树根结点,然后访问右子树根结点,最后访问根结点(左-右-根)。通过递归调用实现后序遍历算法的C语言代码如下:
1. void postorder_traversal(MyTreeNode* tree) 2. { 3. if (tree == NULL) 4. { 5. return; 6. } 7. postorder_traversal(tree->left); 8. postorder_traversal(tree->right); 9. printf("%d ", tree->data); 10. }
后序遍历算法的测试结果:
三种遍历的关系
通过对比三种递归遍历算法的代码可以看到,三种遍历的区别就在于printf函数的位置不同,其他语句的顺序都是相同的,实际上,在遍历树的时候,不管是前序遍历、中序遍历、还是后序遍历,每个结点都会被访问三次,如下图所示,三种遍历的区别就在于获取节点数据的时机不同,前序遍历是在第一次访问就获取结点数据,中序遍历是在第二次访问的时候获取结点数据,后序遍历是在第三次访问的时候获取结点数据。
求二叉树的叶子结点数
代码如下
1. void get_leaf_num(MyTreeNode* tree, int* count) //指针做函数参数,间接修改实参的值 2. { 3. if ((tree->left == NULL) && (tree->right == NULL)) 4. { 5. (*count)++; 6. } 7. if (tree->left != NULL) 8. { 9. get_leaf_num(tree->left, count); 10. } 11. if (tree->right != NULL) 12. { 13. get_leaf_num(tree->right, count); 14. } 15. }
求二叉树叶子结点算法测试:
复制一棵树
通过递归实现复制树,代码如下
1. MyTreeNode* copy_tree(MyTreeNode* tree) 2. { 3. MyTreeNode* root = NULL;// *left = NULL, * right = NULL; 4. root = (MyTreeNode*)malloc(sizeof(MyTreeNode)); 5. memset(root, 0, sizeof(MyTreeNode)); 6. root->data = tree->data; 7. if (tree->left != NULL) 8. { 9. //如果有左子树则复制左子树 10. root->left = copy_tree(tree->left); 11. } 12. else 13. { 14. //没有左子树则置为NULL 15. root->left = NULL; 16. } 17. if (tree->right != NULL) 18. { 19. root->right = copy_tree(tree->right); 20. } 21. else 22. { 23. root->right = NULL; 24. } 25. return root; 26. }
复制树的时候,要通过malloc动态为复制好的树的结点分配内存,最后返回树的根结点地址。算法测试结果如下: