二叉树的创建和销毁
1.创建二叉树
创建一个二叉树，我们需要创建一个结构体，里面两个结构体指针分别存放左子树和右子树：
typedef char BTDataType; //typedef 便于后续修改数据类型 typedef struct BinaryTreeNode { BTDataType _data; struct BinaryTreeNode* _left; struct BinaryTreeNode* _right; }BTNode;
通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode *BinaryTreeCreate(BTDataType * src, int n, int* pi) { if (*pi >= n || src[*pi] == '#') { (*pi)++; return NULL; } BTNode * cur = (BTNode *)malloc(sizeof(BTNode)); cur->_data = src[*pi]; (*pi)++; cur->_left = BinaryTreeCreate(src, n, pi); cur->_right = BinaryTreeCreate(src, n, pi); return cur; }
2.销毁二叉树
二叉树的销毁
void BinaryTreeDestory(BTNode** root) { if (*root) { BinaryTreeDestory(&(*root)->_left); BinaryTreeDestory(&(*root)->_right); free(*root); *root = NULL; } }
二叉树的遍历
// 二叉树前序遍历 void BinaryTreePrevOrder(BTNode* root); // 二叉树中序遍历 void BinaryTreeInOrder(BTNode* root); // 二叉树后序遍历 void BinaryTreePostOrder(BTNode* root); // 层序遍历 void BinaryTreeLevelOrder(BTNode* root);
对于二叉树的四种遍历 ：
前序遍历：当前结点（根节点 ）, 左子树, 右子树 即访问根结点的操作发生在遍历其左右子树之前
中序遍历:左子树，根节点，右子树 访问根结点的操作发生在遍历其左右子树之中（间）。
后序遍历：左子树，右子树，根节点 访问根结点的操作发生在遍历其左右子树之后。
层序遍历：从所在二叉树的根节点出发，从上到下按层遍历，每层从左到右遍历
前中后序遍历实现：
void BinaryTreePrevOrder(BTNode* root) { if (root) { putchar(root->_data); BinaryTreePrevOrder(root->_left); BinaryTreePrevOrder(root->_right); } } void BinaryTreeInOrder(BTNode* root) { if (root) { BinaryTreeInOrder(root->_left); putchar(root->_data); BinaryTreeInOrder(root->_right); } } void BinaryTreePostOrder(BTNode* root) { if (root) { BinaryTreePostOrder(root->_left); BinaryTreePostOrder(root->_right); putchar(root->_data); } }
层序遍历实现
对于层序遍历，我们不能简单的调用递归来遍历，这里我们利用队列其先进先出的性质，实现层序遍历：
#include "queue.h" void BinaryTreeLevelOrder(BTNode* root) { Queue qu; BTNode * cur; QueueInit(&qu); QueuePush(&qu, root); while (!QueueIsEmpty(&qu)) { cur = QueueTop(&qu); putchar(cur->_data); if (cur->_left) { QueuePush(&qu, cur->_left); } if (cur->_right) { QueuePush(&qu, cur->_right); } QueuePop(&qu); } QueueDestory(&qu); }
二叉树的相关计算
1.二叉树节点个数
我们递归调用将左子树的结点加上右子树的结点再加上根结点
int BinaryTreeSize(BTNode* root) { //巧用三目运算符 return root == NULL ? 0 : BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right) + 1; }
2.二叉树叶子节点个数
叶子节点：度为0的节点
int BinaryTreeLeafSize(BTNode* root) { if (root == NULL) return 0; if (root->_left == NULL && root->_right == NULL) return 1; //只有根结点就返回1个叶子数 //递归调用遍历左子树和右子树的叶子数相加 return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right); }
3.二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k) { if (root == NULL) //若二叉树为空或者K小于0，返回0 return 0; if (k == 1) //若K等于1，第1层就是树根，根只有一个，返回1 return 1; //递归调用返回左子树中第K-1层结点个数 加上 右子树中第K-1层结点的个数 return BinaryTreeLevelKSize(root->_left, k - 1) + BinaryTreeLevelKSize(root->_right, k - 1); }
4.二叉树查找值为x的节点
思路：先对左子树递归查找，如果未找到x,则返回NULL,如果找到x，便返回x所在节点。根据返回值判断是否需要进行右递归查找操作。
BTNode* BinaryTreeFind(BTNode* root, BTDataType x) { if (root == NULL) return NULL; if (root->_data == x) return root; BTNode* ret1 = BinaryTreeFind(root->_left, x); if (ret1) return ret1; BTNode* ret2 = BinaryTreeFind(root->_right, x); if (ret2) return ret2; return NULL; }
本节完
