本文内容将主会多次用到函数递归知识!!!
本节内容需要借助画图才能更好理解!!!
和往常一样,还是创建三个文件
这是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):访问根结点的操作发生在遍历其左右子树之后
访问顺序为:左子树、右子树、根结点
图解遍历:
以前序遍历为例: