C语言数据结构—二叉树的链式结构实现

目录

1、建立二叉树

1.1 二叉树的结构

1.2 手动建立二叉树

2、二叉树的遍历

2.1 二叉树的三种遍历方式

2.1.1 前序遍历 

2.1.2 中序遍历

2.1.2 后序遍历

3、求二叉树的结点数和二叉树的高度

3.1 求二叉树结点数

3.2 求二叉树叶子结点

3.3 求二叉树第k层结点的个数

3.4 求二叉树的高度

4、二叉树的查找

1、建立二叉树

在学习二叉树的功能之前，先要建立二叉树，这里我们先手动建立一棵二叉树。

1.1 二叉树的结构

我们要建立的这棵二叉树，将每一个结点表示为一个结构体，每一个结点同时存储了数据和自己子结点的地址（结构体指针），如果没有子结点该指针就指向空。

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

1.2 手动建立二叉树

使用malloc函数为结点分配空间。
为每个结点存储数据。
将新建结点插入数据这个过程封装为函数BuyNode()。

//新建结点
BTNode* BuyNode(int x)
{BTNode* node = (BTNode*)malloc(sizeof(BTNode));if (node == NULL){perror("malloc fail");exit(-1);}node->data = x;node->left = NULL;node->right = NULL;return node;
}

// 手动构建一棵二叉树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;

该二叉树示意图：

2、二叉树的遍历

2.1 二叉树的三种遍历方式

1、前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。
2、中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之间。
3、后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。

二叉树中的核心思想是分治。所谓分治就是分分而治之，大致意思就是将一个复杂的问题转化成一个个简单的小问题，最后解决问题的思想。

2.1.1 前序遍历 

1、对这棵树进行前序遍历，最原始的方法是
先访问1，然后遍历1左子树。
访问2，遍历2左子树。
访问3，遍历3左子树。
为空，再遍历3右子树。
为空，2的左子树遍历结束，再遍历2的右子树。
为空，1的左子树遍历结束，再遍历1的右子树。
…………
…………
…………
2、根据上述方法，我们可以将这个方法归纳为
先访问1后再前序遍历1的左子树和右子树，
前序遍历A的左子树 可以转化为 先访问2后再前序遍历2的左子树和右子树
前序遍历2的左子树 可以转化为 先访问3后再前序遍历3的左子树和右子树
这样就可以把一个复杂的问题转化为一个个较简单的问题。

void PrevOrder(BTNode* root) 
{if (root == NULL) {printf("NULL");return;}printf("%d ", root->data);PrevOrder(root->left);PrevOrder(root->right);
}

2.1.2 中序遍历

1、对这棵二叉树进行中序遍历，最原始的方法是
先遍历1的左子树。
遍历2的左子树。
遍历3的左子树。
为空，访问3，遍历3的右子树。
为空，访问2，遍历2的右子树。
为空，访问1，遍历1的右子树。
…………
…………
…………
2、根据上述方法，我们可以将这个方法归纳为
中序遍历1的左子树后再访问1，然后中序遍历1的右子树。
中序遍历1的左子树可以转化为中序遍历2的左子树后访问2，然后中序遍历2的右子树。
中序遍历2的右子树又可以转化为中序遍历3的左子树后访问3，然后中序遍历3的右子树。

void InOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}InOrder(root->left);printf("%d ", root->data);InOrder(root->right);
}

2.1.2 后序遍历

1、对这颗二叉树进行中序遍历，最原始的方法是
先遍历1的左子树。
遍历2的左子树。
遍历3的左子树。
为空，遍历3的右子树。
为空访，访问3，遍历2的右子树。
为空，访问2，遍历1的右子树。
…………
…………
…………
2、根据上述方法，我们可以将这个方法归纳为
后序遍历1的左子树和右子树后再访问1。
后序遍历1的左子树可以转化为后序遍历2的左子树和右子树后再访问2。
后序遍历2的左子树又可以转化为后序遍历3的左子树和右子树后再访问3。

void PostOrder(BTNode* root)
{if (root == NULL){printf("NULL");return;}PostOrder(root->left);PostOrder(root->right);printf("%d ", root->data);
}

3、求二叉树的结点数和二叉树的高度

3.1 求二叉树结点数

解题思路：
1、只要该结点地址不为空就是一个结点。
2、整棵树的结点可以转化成
求1的左子树结点数加1的右子树结点树加1（自己本身也是一个结点）。
1的左子树结点树可以转化成2的左子树结点数加右子树的结点树加1。
2的左子树结点数可以转化成3的左子树结点数加D的右子树结点数加1。
3的左右子树都为空，所以2的左子树结点数为1。
…………
…………
…………
直观的写法：

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

或者简洁的写法：

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

3.2 求二叉树叶子结点

解题思路：
1、左右孩子结点都为空的结点算作一个叶子节点。
2、求整棵树的叶子结点，可以转化为求1的左子树叶子结点和1的右子树叶子结点。
求1的左子树叶子结点可以转化为求2的左子树叶子结点加2的右子树叶子结点。
3的左右孩子结点都为空，2的左子树叶子节点为1。
…………
…………
…………

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

3.3 求二叉树第k层结点的个数

解题思路：
若k为3
1、一棵树的第一层结点为1
2、求这棵树第三层的结点数可以转化为求1的左子树以及1的右子树的第二层结点数之和。
求1的左子树的第二层结点数，可以转化成求2的左子树和2的右子树的第一层结点数之和。
2的左子树不为空，层数为1，结点数为1。
2的右子树为空，结点数为0。
…………
…………
…………

// 第k层的节点个数
int TreeKLevel(BTNode* root, int k)
{assert(k > 0);if (root == NULL)return 0;if (k == 1){return 1;}return TreeKLevel(root->left, k - 1) + TreeKLevel(root->right, k - 1);}

3.4 求二叉树的高度

解题思路：
1、空树高度为0。
2、一棵树该树的根结点左右子结点都为空时，该树高度为1。
3、一棵树的高度为左右子树中高度较大的一个加1。
4、求图示中树的高度可以转化为1的左右子树中高度较大的一方加1。
求1的左子树高度可以转化为2的左右子树中高度较大的一方加1。
求2的左子树的高度可以转化为3的左右子树中高度较大的一方加1。
3的左右子结点均为空，则2的左子树高度为1。
2的右子树为空树，2的右子树高度为0，
取较大的一方加1，则2的高度为2，即1的左子树高度为2。

int TreeDepth(BTNode* root)
{if (root == NULL){return 0;}if (root->left == NULL && root->right == NULL){return 1;}return max(TreeDepth(root->left), TreeDepth(root->right));
}

4、二叉树的查找

解题思路：
假设要查找6
如果找到就返回节点地址，没找到返回空。
递归调用的时候要根据返回值来判断是否找到，如果不为空代表找到了，不需要继续查找了，这时返回节点地址。

在整颗树查找6，先看根部是否为6，不是再在1的左右子树中查找。

先看1的左子树根部是否为6，不是再在2的左右子树中查找。

先看2的左子树根部是否为6，不是再在3的左右子树中查找。

3的左右子树为空，返回空。

2的右子树为空，返回空。

1的左子树查找完毕，没找到，查找1的右子树。

先看1的右子树根部是否为6，不是再在4的左右子树查找。
先看4的左子树根部是否为6，不是再在5的左右子树中查找。
5的左右子树为空，返回空。
4的右子树为6，找到了，返回该结点地址。

BTNode* TreeFind(BTNode* root, int x)
{if (root == NULL)return NULL;if (root->data == x)return root;BTNode* ret = NULL;ret = TreeFind(root->left, x);if (ret)return ret;ret = TreeFind(root->right, x);if (ret)return ret;return NULL;
}