树的基本概念
结点：结点包括一个数据元素及若干指向其他子树的分支
结点的度：结点所拥有子树的个数称为该结点的度
叶子结点：度为0的结点称为叶子结点，叶子结点也称为终端结点
分支结点：度不为0的结点称为分支结点，分支结点也称为非终端结点，一棵树中除叶结点以外的所有结点都是分支结点
祖先结点：从根结点到该结点所经分支上的所有结点
子孙结点：以某结点为根结点的子树中所有结点
双亲结点：树中某结点有孩子结点，则这个结点称为它孩子结点的双亲结点，双亲结点也称为前驱结点
孩子结点：树中一个结点的子树的根结点称为该结点的孩子结点，孩子结点也称为后继结点
数的度：树中所有结点的度的最大值称为该树的度
树的深度：树中所有结点的层次的最大值称为该书的深度
二叉树基本概念
一棵二叉树是结点的一个有限集合。该集合是由一个根结点和两颗子树（左子树 右子树）构成 or
该集合为空（空树）。
二叉树的特点：
a.每个结点最多有两颗子树，即二叉树不存在大于2的结点
b.二叉树的子树有左右之分，其子树的次序不能颠倒
满二叉树&完全二叉树.png
构造二叉树
typedef int TreeDataType;
typedef struct BTreeNode{
TreeDataType data;
struct BTreeNode* left;
struct BTreeNode* right;
}BTreeNode;
BTreeNode* CreateNode(int data)
{
BTreeNode* node = (BTreeNode *)malloc(sizeof(BTreeNode));
node->data = data;
node->left = node->right = NULL;
return node;
}
//构造二叉树
//返回值：1 二叉树的根节点 2 创建树过程中，使用的字符个数
BTreeNode* CreateTree(int preOrder[],int size,int* pUsedSize)
{
//空树
if (size <= 0)
{
*pUsedSize = 0;
return NULL;
}
int leftUse, rightUse;
int rootValue = preOrder[0];
//一颗空树
if (rootValue == -1)
{
*pUsedSize = 1;
return NULL;
}
BTreeNode* root = CreateNode(rootValue);
root->left = CreateTree(preOrder + 1, size - 1, &leftUse);
root->right = CreateTree(preOrder + 1+leftUse, size-1-leftUse,&rightUse);
//使用字符个数 = 根节点 + 左子树 + 右子树 = 1 + leftused + rightused；
*pUsedSize = 1+ leftUse + rightUse;
return root;
}
二叉树的基本操作
BinaryTree.h
#define _CRT_SECURE_N0_WARNINGS 1
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int TreeDataType;
typedef struct BTreeNode{
TreeDataType data;
struct BTreeNode* left;
struct BTreeNode* right;
}BTreeNode;
BTreeNode* CreateNode(int data)
{
BTreeNode* node = (BTreeNode *)malloc(sizeof(BTreeNode));
node->data = data;
node->left = node->right = NULL;
return node;
}
//构造二叉树
//返回值：1 二叉树的根节点 2 创建树过程中，使用的字符个数
BTreeNode* CreateTree(int preOrder[],int size,int* pUsedSize)
{
//空树
if (size <= 0)
{
*pUsedSize = 0;
return NULL;
}
int leftUse, rightUse;
int rootValue = preOrder[0];
//一颗空树
if (rootValue == -1)
{
*pUsedSize = 1;
return NULL;
}
BTreeNode* root = CreateNode(rootValue);
root->left = CreateTree(preOrder + 1, size - 1, &leftUse);
root->right = CreateTree(preOrder + 1+leftUse, size-1-leftUse,&rightUse);
//使用字符个数 = 根节点 + 左子树 + 右子树 = 1 + leftused + rightused；
*pUsedSize = 1+ leftUse + rightUse;
return root;
}
//基本操作
// 用 前序 中序 后序 遍历
void PreOrder(BTreeNode* root)
{
//空树
if (root == NULL)
return;
printf("%d ", root->data);
PreOrder(root->left);
PreOrder(root->right);
}
void InOrder(BTreeNode* root)
{
//空树
if (root == NULL)
return;
InOrder(root->left);
printf("%d ", root->data);
InOrder(root->right);
}
void PostOrder(BTreeNode* root)
{
//空树
if (root == NULL)
return;
PostOrder(root->left);
PostOrder(root->right);
printf("%d ", root->data);
}
//求树的节点个数
//方法一
//1）化为子问题
//2）遍历
int GetSize1(BTreeNode* root)
{
//空树
if (root == NULL)
return 0;
int left = GetSize1(root->left);
int right = GetSize1(root->right);
return left + right + 1;
}
//方法二
//利用后序遍历的方式计数节点个数
int count = 0;//全局变量
void GetSize2(BTreeNode* root)
{
//空树
if (root == NULL)
return;
GetSize2(root->left);
GetSize2(root->right);
count++;
}
//求二叉树叶子节点的个数
int GetLeafSize(BTreeNode* root)
{
//空树
if (root == NULL)
return 0;
if (root->left ==NULL && root->right == NULL)
return 1;
return GetLeafSize(root->left) + GetLeafSize(root->right);
}
//求第k层叶子结点的个数
int GetLevelKSize(BTreeNode* root, int k)
{
assert(k >= 1);
if (root == NULL)
return 0;
if (k == 1)
return 1;
// 我的第 k 层，是我子树的第 k - 1 层
int left = GetLevelKSize(root->left, k - 1);
int right = GetLevelKSize(root->right, k - 1);
return left + right;
}
// 高度/深度
#define MAX(a, b) ((a) > (b) ? (a) : (b))
int GetHeight(BTreeNode *root)
{
if (root == NULL) {
return 0;
}
// 当子树只有一个结点的时候，可以写，也可以不写
// 写的话，节省两次函数调用
if (root->left == NULL&&root->right == NULL)
return 1;
return MAX(GetHeight(root->left), GetHeight(root->right)) + 1;
}
BTreeNode* Find(BTreeNode* root, TreeDataType data)
{
if (root == NULL) {
return NULL; // (1)
}
if (root->data == data) {
return root; // (2)
}
BTreeNode *result = Find(root->left, data);
if (result != NULL) {
// 左子树找到了
return result; // (3)
}
result = Find(root->right, data);
if (result != NULL) {
return result; // (4)
}
else {
return NULL; // (5)
}
}
//--------------------------------------------------
//----------------------测试------------------------
//--------------------------------------------------
void Test()
{
int preOrder[] = { 1, 2, 3, -1, 4, 5, -1, -1, -1, 6, -1, -1, 7, 8, -1, -1, 9, -1, 10 };
//int preOrder[] = { 1, 2, 4, -1, -1, -1, 3 };
int size = sizeof(preOrder) / sizeof(int);
int usedSize;
BTreeNode *root = CreateTree(preOrder, size, &usedSize);
PreOrder(root); printf("\n");
InOrder(root); printf("\n");
PostOrder(root); printf("\n");
printf("递归法-->结点个数: %d\n", GetSize1(root));
GetSize2(root); printf("全局变量法-->结点个数: %d\n", count);
printf("叶子结点个数: %d\n", GetLeafSize(root));
printf("第3层叶子结点的个数:%d\n",GetLevelKSize(root, 3));
printf("高度: %d\n", GetHeight(root));
}
Main.c
#define _CRT_SECURE_N0_WARNINGS 1
#include "BinaryTree.h"
int main()
{
Test();
}
二叉树——二叉树.png
前序：1 2 3 4 5 6 7 8 9 10
中序：3 5 4 2 6 1 8 7 9 10
后序：5 4 3 6 2 8 10 9 7 1
层序：1 2 7 3 6 8 9 4 10 5
二叉树基本操作.png
