二叉树
概念
一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根节点加上两棵别称为左子树和右子树的二又树组成。 二叉树的特点: 1.每个结点最多有两棵子树，即二叉树不存在度大于2的结点。2.二又树的子树有左右之分，其子树的次序不能颠倒
特殊的二叉树
1.满二叉树:一个二叉树，如果每一个层的结点数都达到最大值，则这个二又树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是(2^k)-1，则它就是满二叉树。 2.完全二叉树:完全二又树是效率很高的数据结构，完全- -又树是由满二又树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二又树中编号从1至n的结点一对应时称之为完全二又树。要注意的是满二叉树是-种特殊的完全二叉树。
具体实现代码如下：
BinaryTree.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <assert.h>
#include "Queue.h"
#include "Stack.h"
typedef char BTDataType ;
typedef struct BTNode
{
struct BTNode* _left;
struct BTNode* _right;
BTDataType _data;
}BTNode;
// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int* pi);
void BinaryTreeDestory(BTNode** root);
int BinaryTreeSize(BTNode* root);
int BinaryTreeLeafSize(BTNode* root);
int BinaryTreeLevelKSize(BTNode* root, int k);
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// 遍历 递归
void BinaryTreePrevOrder(BTNode* root);//前序遍历
void BinaryTreeInOrder(BTNode* root);//中序遍历
void BinaryTreePostOrder(BTNode* root);//后序遍历
void BinaryTreeLevelOrder(BTNode* root);//层序遍历
// 遍历 非递归
void BinaryTreePrevOrderNonR(BTNode* root);//前序遍历的非递归
void BinaryTreeInOrderNonR(BTNode* root);//中序遍历的非递归
void BinaryTreePostOrderNonR(BTNode* root);//后序遍历的非递归
void TestBinaryTree();
BinaryTree.c
#include "BinaryTree.h"
#include "Queue.h"
#include "Stack.h"
BTNode* BuyBTNode(BTDataType x)
{
BTNode* node = (BTNode*)malloc(sizeof(BTNode));
node->_data= x;
node->_left =NULL;
node->_right = NULL;
return node;
}
BTNode* BinaryTreeCreate(BTDataType* a,int* pi)
{
if (a[*pi] != '#')
{
BTNode* root = BuyBTNode(a[*pi]);
(*pi)++;
root->_left = BinaryTreeCreate(a, pi);
(*pi)++;
root->_right = BinaryTreeCreate(a, pi);
return root;
}
else
{
return NULL;
}
}
int BinaryTreeSize(BTNode* root)
{
if (root == NULL)
{
return 0;
}
else
{
return BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right) + 1;
}
}
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 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);
}
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
if (root == NULL)
{
return NULL;
}
if (root->_data == x)
{
return root;
}
BTNode* ret = BinaryTreeFind(root->_left, x);
if (ret)
{
return ret;
}
return ret = BinaryTreeFind(root->_right, x);
}
void _BinaryTreePrevOrder(BTNode* root, int* a, int* pi)
{
if (root == NULL)
{
return ;
}
printf("%c ", root->_data);
(*pi)++;
_BinaryTreePrevOrder(root->_left, a, pi);
_BinaryTreePrevOrder(root->_right, a, pi);
}
void BinaryTreePrevOrder(BTNode* root)//前序遍历
{
if (root == NULL)
return ;
int treeSize = BinaryTreeSize(root);
int* arr = (int*)malloc(sizeof(int)*treeSize);
int i = 0;
_BinaryTreePrevOrder(root, arr, &i);
}
void _BinaryTreeInOrder(BTNode* root, int* arr, int* pi)
{
if (root == NULL)
{
return ;
}
_BinaryTreeInOrder(root->_left, arr, pi);
printf("%c ", root->_data);
_BinaryTreeInOrder(root->_right, arr, pi);
}
void BinaryTreeInOrder(BTNode* root)//中序遍历
{
if (root == NULL)
return;
int treeSize = BinaryTreeSize(root);
int* arr = (int*)malloc(sizeof(int)*treeSize);
int i = 0;
_BinaryTreeInOrder(root, arr, &i);
}
void _BinaryTreePostOrder(BTNode* root, int* arr, int* pi)
{
if (root == NULL)
return;
_BinaryTreePostOrder(root->_left, arr, pi);
_BinaryTreePostOrder(root->_right, arr, pi);
printf("%c ", root->_data);
}
void BinaryTreePostOrder(BTNode* root)//后序遍历
{
if (root == NULL)
{
return;
}
int treeSize = BinaryTreeSize(root);
int* arr = (int*)malloc(sizeof(int)*treeSize);
int i = 0;
_BinaryTreePostOrder(root, arr, &i);
}
void BinaryTreeLevelOrder(BTNode* root)//层序遍历
{
Queue q;
QueueInit(&q);
if (root != NULL)
{
QueuePush(&q, root);
while (QueueEmpty(&q) != 0)
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
printf("%c ", front->_data);
if (front->_left)
{
QueuePush(&q, front->_left);
}
if (front->_right)
{
QueuePush(&q, front->_right);
}
}
}
printf("\n");
}
void BinaryTreePrevOrderNonR(BTNode* root)//前序遍历的非递归
{
Stack st;
StackInit(&st,10);
BTNode* cur = root;
while (cur || StackEmpty(&st) != 0)
{
//开始访问一棵树
//1.先访问树的左路节点
while (cur)
{
printf("%c ", cur->_data);
StackPush(&st, cur);
cur = cur->_left;
}
BTNode* top = StackTop(&st);
StackPop(&st);
//2.访问左路节点的右子树
cur = top->_right;
}
printf("\n");
}
void BinaryTreeInOrderNonR(BTNode* root)//中序遍历的非递归
{
Stack st;
StackInit(&st, 10);
BTNode* cur = root;
//1.压左路节点
while (cur || StackEmpty(&st) != 0)
{
while (cur)
{
StackPush(&st, cur);
cur = cur->_left;
}
//2.取出左路节点，并访问左路节点的右子树
BTNode* top = StackTop(&st);
printf("%c ", top->_data);
StackPop(&st);
cur = top->_right;
}
printf("\n");
}
void BinaryTreePostOrderNonR(BTNode* root)//后序遍历的非递归
{
Stack st;
StackInit(&st,10);
BTNode* cur = root;
BTNode* prev = NULL;
while (cur || StackEmpty(&st) != 0)
{
//1.把压左路节点入栈
while (cur)
{
StackPush(&st, cur);
cur = cur->_left;
}
BTNode* top = StackTop(&st);
//右树访问过了，才能访问根节点
if (top->_right == NULL || top->_right == prev)//判断右树是否已经访问过，如果不判断就会出现死循环
{
printf("%c ", top->_data);
StackPop(&st);
prev = top;
}
else
{
cur = top->_right;
}
}
printf("\n");
}
test.c
# include "BinaryTree.h"
#include "Queue.h"
#include "Stack.h"
void BinaryTreeTest()
{
char* array = "ABD##E#H##CF##G##";
int i = 0;
BTNode* tree = BinaryTreeCreate(array, &i);
printf("%d\n", BinaryTreeSize(tree));
printf("%d\n", BinaryTreeLeafSize(tree));
BinaryTreePrevOrder(tree); //递归的前序遍历
printf("\n");
printf("\n");
BinaryTreeInOrder(tree);//递归的中序序遍历
printf("\n");
printf("\n");
BinaryTreePostOrder(tree);//递归的后序遍历
printf("\n");
printf("\n");
BinaryTreeLevelOrder(tree);//层序遍历
printf("\n");
printf("\n");
BinaryTreePrevOrderNonR(tree);//非递归的前序遍历
printf("\n");
BinaryTreeInOrderNonR(tree);//中序遍历的非递归
printf("\n");
BinaryTreePostOrderNonR(tree);//后序遍历的非递归
}
int main()
{
BinaryTreeTest();
system("pause");
return 0;
}
注：这份代码还需要一份栈接口的代码以及实现队列的代码，因为我是直接把这两份代码放在头文件下面的，有点多，就没有在这里放，所以那两份代码有问题的话，可以看我前面的博客，里面有详细的代码哦。
栈接口的实现：https://blog.csdn.net/qq_42270373/article/details/83033961
队列接口的实现：https://blog.csdn.net/qq_42270373/article/details/83034037
