文章目录

• 链式二叉树
• • 1. 概念
  • 2. 链式二叉树的基本操作
  • • 前序遍历
    • 中序遍历
    • 后续遍历
    • 根据前序遍历构建二叉树
    • 层序遍历
    • 在二叉树中查找指定值
    • 获取二叉树节点个数
    • 获取叶子节点个数
    • 求二叉树的高度

链式二叉树

1. 概念

设计不同的节点结构可构成不同形式的链式存储结构。由二叉树的定义可知，二叉树的节点由一个数据元素分别指向其左右子树的两个分支构成，则表示二叉树的链表中的结点至少包含3个域：数据域和左右指针域，左右指针分别指向左右孩子所在的链节点的存储地址。

typedef char BTDataType;typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;

2. 链式二叉树的基本操作

前序遍历

前序遍历又叫先根遍历，先遍历根节点再遍历左子树和右子树，而左子树和右子树又有根节点，这就是一个递归操作。就是按根左右的遍历方法。

比如下面这棵数的前序遍历就是ABDEHCFG

// 二叉树前序遍历
void BinaryTreePrevOrder(BTNode* root)
{if (root == NULL){return;}printf("%c ", root->data);BinaryTreePrevOrder(root->left);BinaryTreePrevOrder(root->right);}

中序遍历

中序遍历中根遍历，它的遍历顺序就是先遍历左子树再遍历根节点再遍历右子树，也就是左根右。

这棵树的中序遍历就是DBEHAFCG

// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{if (root == NULL){return;}BinaryTreeInOrder(root->left);printf("%c ", root->data);BinaryTreeInOrder(root->right);
}

后续遍历

后续遍历也叫后根遍历，遍历的顺序是先左子树再右子树最后根节点，按照左右根来遍历二叉树。

下面这棵树的后续遍历就是DHEBFGCA

// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{if (root == NULL){return;}BinaryTreePostOrder(root->left);BinaryTreePostOrder(root->right);printf("%c ", root->data);
}

根据前序遍历构建二叉树

给定一个字符串。是二叉树树的前序遍历ABD##E#H##CF##G##，其中#代表NULL，通过这个字符串构造一颗二叉树。

实现思路：

1. 函数三个参数，数组、字符串长度、数组下标，通过递归来构建
2. 递归的结束条件，数组遍历完了、或者是遇到#了
3. 每调用一次函数就让index加一
4. 最后返回节点

// 根据前序遍历构建二叉树
BTNode* BinaryTreeCreate(BTDataType* arr, int n, int* index)
{if (*index >= n || arr[*index] == '#'){return NULL;}BTNode* root = (BTNode*)(malloc(sizeof(BTNode)));root->data = arr[*index];(*index)++;root->left = BinaryTreeCreate(arr, n, index);(*index)++;root->right = BinaryTreeCreate(arr, n, index);return root;
}

层序遍历

层序遍历就是将二叉树按层一层一层遍历。

下面这个二叉树的层序遍历为ABCDEFGH

思路：

同过队列来进行广度优先搜索。

• 首先将根节点如队列，然后出队出队的同时将左右孩子入队列(注意左右孩子不为空)
• 出队前记录当前队列元素个数，出当前队列中的元素(避免刚入队的左右子树出队列)
• 当队列为空时说明层序遍历完成

// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{Queue q = {NULL,NULL};QueueInit(&q);QueuePush(&q,root);while (!QueueEmpty(&q)){int size = QueueSize(&q);while (size--){BTNode* root = QueueFront(&q);printf("%c ", root->data);if (root->left != NULL){QueuePush(&q, root->left);}if (root->right != NULL){QueuePush(&q, root->right);}QueuePop(&q);}}}

在二叉树中查找指定值

直接递归遍历二叉树，先找根节点再找左子树和右子树。

// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL){return NULL;}if (root->data == x){return root;}BTNode* left = BinaryTreeFind(root->left, x);if (left != NULL){return left;}BTNode* right = BinaryTreeFind(root->right, x);if (right != NULL){return right;}return NULL;}

获取二叉树节点个数

这其实就时一个普通的遍历，通过递归将大事化小。整棵树的节点个数会等于：它的左子树节点个数加上右子树的节点个数再加上自己，也就是加一。

// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{return root == NULL ? 0 : BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}

获取叶子节点个数

叶子节点右一个特点，就是它的左子树和右子树都为空，通过递归如果左右子树都为NULL就返回1，否则返回0,就能得到叶子节点个数。

// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{if (root == NULL){return 0;}if (root->left == NULL && root->right == NULL){return 1;}return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

求二叉树的高度

二叉树的高度就是它的最大深度，相求一颗树的最大深度，就得先求出它的左右子树的最大深度，通过后续遍历到达叶子节点，从叶子节点开始不断求出左右子树的较大的那一棵子树再加一，开始不断向上返回就能得到一颗二叉树的最大深度。

int maxDepth(BTNode* root){if (root == NULL){return 0;}int left = maxDepth(root->left);int right = maxDepth(root->right);return left > right ? left+1 : right+1;}

从叶子节点开始不断求出左右子树的较大的那一棵子树再加一，开始不断向上返回就能得到一颗二叉树的最大深度。

int maxDepth(BTNode* root){if (root == NULL){return 0;}int left = maxDepth(root->left);int right = maxDepth(root->right);return left > right ? left+1 : right+1;}