数据结构之链式结构二叉树的实现（初级版）

本文内容将主会多次用到函数递归知识！！！

本节内容需要借助画图才能更好理解！！！

和往常一样，还是创建三个文件

这是tree.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef char btdatatype;
//定义二叉树结点结果
typedef struct binarytreenode
{btdatatype data;struct binarytreenode* left;struct binarytreenode* right;
}btnode;//前序遍历
void preorder(btnode* root);
//中序遍历
void InOrder(btnode* root);
//后序遍历
void PostOrder(btnode* root);// ⼆叉树结点个数
int BinaryTreeSize(btnode* root);
// ⼆叉树叶⼦结点个数
int BinaryTreeLeafSize(btnode* root);
// ⼆叉树第k层结点个数
int BinaryTreeLevelKSize(btnode* root, int k);
//⼆叉树的深度/⾼度
int BinaryTreeDepth(btnode* root);
// ⼆叉树查找值为x的结点
btnode* BinaryTreeFind(btnode* root, btdatatype x);
// ⼆叉树销毁
void BinaryTreeDestory(btnode** root);

这是tree.c

​
#include"tree.h"
//先序遍历--根左右
void preorder(btnode* root)
{if (root == NULL){printf("NULL ");return;}printf("%c ", root->data);preorder(root->left);preorder(root->right);
}
//中序遍历--左根右
void InOrder(btnode* root)
{if (root == NULL){printf("NULL ");return;}InOrder(root->left);printf("%c ", root->data);InOrder(root->right);
}
//后序遍历--左右根
void PostOrder(btnode* root)
{if (root == NULL){printf("NULL ");return;}PostOrder(root->left);PostOrder(root->right);printf("%c ", root->data);
}
int BinaryTreeSize(btnode* root)
{if (root == NULL){return 0;}return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}
// ⼆叉树叶⼦结点个数
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);
}
// ⼆叉树第k层结点个数
int BinaryTreeLevelKSize(btnode* root, int k)
{if (root == NULL){return 0;}if (k == 1){return 1;}return BinaryTreeLevelKSize(root->left,k-1) + BinaryTreeLevelKSize(root->right, k - 1);//从上往下索引，索引一层就k-1
}
//⼆叉树的深度/⾼度  ？？？
int BinaryTreeDepth(btnode* root)
{if (root == NULL){return 0;}int leftdep = BinaryTreeDepth(root->left);int rightdep = BinaryTreeDepth(root->right);return 1 + (leftdep > rightdep ? leftdep : rightdep);
}
// ⼆叉树查找值为x的结点
btnode* BinaryTreeFind(btnode* root, btdatatype x)
{if (root == NULL){return NULL;}if (root->data == x){return root;}btnode* leftfind = BinaryTreeFind(root->left, x);if (leftfind){return leftfind;}btnode* rightfind = BinaryTreeFind(root->right, x);if (rightfind){return rightfind;}return NULL;
}
//传二级指针可以这样简单理解，销毁即把指向这一空间的指针（地址）置为NULL，而我们的root是一个一级指针，要将其销毁，则需要将其地址置为NULL，故传二级指针
void BinaryTreeDestory(btnode** root)
{if (*root == NULL){return;}BinaryTreeDestory(&((*root)->right));BinaryTreeDestory(&((*root)->left));free(*root);*root = NULL;
}
​

这是test.c

​
#include"tree.h"
btnode* buynode(btdatatype x)
{btnode* node = (btnode*)malloc(sizeof(btnode));assert(node);node->data = x;node->left = node->right = NULL;return node;
}
//手动构造一棵二叉树
btnode* createtree()
{btnode* nodeA = buynode('A');      //字符不要用双引号！！！btnode* nodeB = buynode('B');btnode* nodeC = buynode('C');btnode* nodeD = buynode('D');btnode* nodeE = buynode('E');btnode* nodeF = buynode('F');nodeA->left = nodeB;nodeA->right = nodeC;nodeB->left = nodeD;nodeC->left = nodeE;nodeC->right = nodeF;return nodeA;
}
void test()
{btnode* root = createtree();preorder(root);printf("\n");InOrder(root);printf("\n");PostOrder(root);printf("\n");printf("size:%d\n", BinaryTreeSize(root));printf("size:%d\n", BinaryTreeSize(root));printf("leaf size:%d\n", BinaryTreeLeafSize(root));printf("k size:%d\n", BinaryTreeLevelKSize(root, 2));printf("k size:%d\n", BinaryTreeLevelKSize(root, 3));printf("k size:%d\n", BinaryTreeLevelKSize(root, 1));printf("depth:%d\n", BinaryTreeDepth(root));btnode* find = BinaryTreeFind(root, 'A');if (find == NULL){printf("not found!");}else{printf("we've found it!");}BinaryTreeDestory(&root);
}
int main()
{test();return 0;
}​

说明：

1. 遍历规则

按照规则，⼆叉树的遍历有：前序/中序/后序的递归结构遍历：

1）前序遍历(Preorder Traversal 亦称先序遍历)：访问根结点的操作发生在遍历其左右子树之前

访问顺序为：根结点、左子树、右子树

2）中序遍历(Inorder Traversal)：访问根结点的操作发生在遍历其左右子树之中（间）

访问顺序为：左子树、根结点、右子树

3）后序遍历(Postorder Traversal)：访问根结点的操作发生在遍历其左右子树之后

访问顺序为：左子树、右子树、根结点 

图解遍历：

以前序遍历为例：