树和二叉树的基本操作与实现

60 阅读 0 评论 40 点赞

我是靠谱客的博主腼腆航空，最近开发中收集的这篇文章主要介绍树和二叉树的基本操作与实现，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

树的概念以及相关概念

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为像一棵反着的树。

**树的特点：**每个结点有零个或多个子节点；没有父节点的结点成为根节点；每个芬根结点有且只有一个父节点；除了根节点外，每个子结点可以分为多个不想交的子树

树的存储方式
树可以使用顺序存储和链式存储两种方式来实现

二叉树

二叉树的基本概念以及性质
二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根节点加上两个别称为左子树和右子树的二叉树组成。
二叉树的特点：
1.每个结点最多有两个子树
2.二叉树的子树有左右之分，其子树的次序不能颠倒

**满二叉树：**一个二叉树，如果每个结点都是两个，则这个二叉树是满二叉树。总节点个数没（2^k）-1个

完全二叉树：完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中编号从1至n的节点——对应时称之为完全二叉树

二叉树的静态存储于链式存储
二叉树一般可以使用顺序结构和链式结构来存储

顺序存储：
顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费

链式存储：
链式存储结构是用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。

实现链式数据结构有以下基本操作：

#pragma once
#include <stdlib.h>
#include <stdio.h>
typedef struct Node { //二叉树的前序遍历(根，左，右的顺序）
char value;
struct Node *left; //代表左子树
struct Node *right; //代表右子树
}Node;

void PreorderTraversal(Node *root) {
if (root == NULL) { //树为空时
return;
}
printf("%d", root->value); //打印根的值
if (root->left != NULL) {
PreorderTraversal(root->left);//左
}
if (root->right != NULL) {
PreorderTraversal(root->right);//右
}
}
//二叉树的中序遍历（左，根，右）
void InorderTraversal(Node *root) {
if (root == NULL) {
return;
}
InorderTraversal(root->left);
printf("%d", root->value);
InorderTraversal(root->right);
}
//二叉树的后序遍历（左，右，根）
void PostorderTraversal(Node *root) {
if (root == NULL) {
return;
}
PostorderTraversal(root->left);
PostorderTraversal(root->right);
printf("%d", root->value);
}
//求节点个数遍历
int size;
void Size(Node *root) {
if (root == NULL) {
return;
}
size++;
Size(root->left);
Size(root->right);
}
//递推求节点个数
int Size2(Node *root) {
if (root = NULL) {
return 0;
}
int left = Size2(root->left);
int right = Size2(root->right);
return left + right + 1;
}
//递推方式，求叶子节点个数
int LeafSize(Node *root){
if (root == NULL) {
return 0;
}
if (root->left == NULL && root->right == NULL) {
return 1;
}
int left = LeafSize(root->left);
int right = LeafSize(root->right);
return left + right;
}
//求二叉树的高度
int GetHeight(Node *root) {
if (root == NULL) {
return 0;
}
int left = GetHeight(root->left);
int right = GetHeight(root->right);

return (left > right ? left : right) + 1;

}
//求第n层的节点个数
int GetKLevel(Node *root, int n)
{
if (root == NULL)
{
return 0;
}
if (n == 1) {
return 1;
}
int z = GetHeight(root->left);
int y = GetHeight(root->right);
return z + y;
}
//在二叉树中找一个结点，找到返回结点地址，没找到返回NULL
Node *Find(Node *root, int v) {
if (root == NULL) {
return NULL;
}
if (root->value = v) { //在根找
return root;
}
Node *result = Find(root->left, v);
if(result != NULL)
{ //在左子树找
return result;
}
result = Find(root->right, v);
if(result != NULL){ //在右子树找
return result;
}
else {
return NULL;
}
}
//判断两个二叉树是否相同

bool isSameTree(struct Node* p, struct Node* q) {
if (p == NULL && q == NULL) {
return true;
}
if (p == NULL || q == NULL) {
return false;
}
return p->value == q->value && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
//判断是不是镜像二叉树
bool isMirror(struct Node *p, struct Node *q) {
if (p == NULL && q == NULL) {
return true;
}
if (p == NULL || q == NULL) {
return false;
}
return p->value == q->value && isMirror(p->left, q->right)
&& isMirror(p->right, q->left);
}
//判断一个树是否是另一个树的子树
bool preorder(struct Node *r, struct Node *t) {
if (r == NULL) {
return false;
}
if (isSameTree(r, t)) {
return true;
}
bool result = preorder(r->left, t);
if (result == true) {
return true;
}
return preorder(r->left, t);
}
bool isSubtree(struct Node *s, struct Node *t) {
return preorder(s, t);
}