二叉树(Binary Tree) 是由n个结点构成的有限集(n≥0),n=0时为空树,n>0时为非空树。
对于非空树:
存的目的是为了取,而取的关键在于如何通过父结点拿到它的左右子结点,不同存储方式围绕的核心也就是这。
使用一组地址连续的存储单元存储,例如数组。为了在存储结构中能得到父子结点之间的映射关系,二叉树中的结点必须按层次遍历的顺序存放。具体是:
假设将一棵二叉树按此方式存储到数组后,左子结点下标=2倍的父结点下标+1,右子节点下标=2倍的父结点下标+2(这里父子结点间的关系是基于根结点从0开始计算的)。若数组某个位置处值为#,代表此处对应的结点为空。
可以看出顺序存储非常适合存储接近完全二叉树类型的二叉树,对于一般二叉树有很大的空间浪费,所以对于一般二叉树,一般用下面这种链式存储。
对每个结点,除数据域外再多增加左右两个指针域,分别指向该结点的左孩子和右孩子结点,再用一个头指针指向根结点。对应的存储结构:
首先我们要得到相应的自定义函数,然后再去一一实现他们
typedef int BTDataType;
typedef struct BinaryTreeNode
{
BTDataType data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;
//创建一颗树
BTNode* creatBT();
//创建一个新节点
BTNode* BuyNode(int x);
//前序遍历
void PrevOrder(BTNode* root);
//计算节点个数
int TreeSize(BTNode* root);
由于我们接下来的前序、中序、后序遍历都需要一个二叉树,所以我们这里要先创建一颗二叉树才可以。
//创建一个新节点
BTNode* BuyNode(int x)
{
BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
if (newnode == NULL)
{
perror("malloc failed");
exit(0);
}
newnode->data = x;
newnode->left = newnode->right =NULL;
return newnode;
}
BTNode* creatBT()
{
BTNode* node1 = BuyNode(1);
BTNode* node2 = BuyNode(2);
BTNode* node3 = BuyNode(3);
BTNode* node4 = BuyNode(4);
BTNode* node5 = BuyNode(5);
BTNode* node6 = BuyNode(6);
node1->left = node2;
node1->right = node4;
node2->left = node3;
node4->left = node5;
node4->right = node6;
return node1;
}
//前序遍历
void PrevOrder(BTNode* root)
{
if (root == NULL)
{
printf("N ");
return;
}
printf("%d ", root->data);//输出当前数值
PrevOrder(root->left);//然后递归进行
PrevOrder(root->right);
}
//中序遍历
void InOrder(BTNode* root)
{
if (root == NULL)
{
printf("N ");
return;
}
InOrder(root->left);//先递归,等到最后一个之后再进行输出
printf("%d ", root->data);
InOrder(root->right);
}
//后序遍历
void BackOrder(BTNode* root)
{
if (root == NULL)
{
printf("N ");
return;
}
BackOrder(root->left);
BackOrder(root->right);
printf("%d ", root->data);
}
//节点个数
int treesize(BTNode* root)
{
if (root == NULL)return 0;
else return treesize(root->left) + treesize(root->right) + 1 ;
}
另一种方式:
int TreeSize(BTNode* root)
{
static int size = 0;//用局部静态变量,只初始化一次。
if (root == NULL)
{
return 0;
}
else
{
++size;
}
TreeSize(root->left);
TreeSize(root->right);
return size;
}
//求叶子节点个数
int TreeLeafSize(BTNode* root)
{
if (root == NULL)
{
return 0;
}
if (root->left == NULL && root->right == NULL)
{
return 1;
}
return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}
int TreeHeigh(BTNode* root)
{
if (root == NULL)
{
return 0;
}
int leftheight = TreeHeigh(root->left);
int rightheight = TreeHeigh(root->right);
return leftheight > rightheight ?
leftheight + 1 : rightheight + 1;
}
#pragma once
#include<iostream>
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int BTDataType;
typedef struct BinaryTreeNode
{
BTDataType data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;
//创建一颗树
BTNode* creatBT();
//创建一个新节点
BTNode* BuyNode(int x);
//前序遍历
void PrevOrder(BTNode* root);
//计算节点个数
int TreeSize(BTNode* root);
#include"Tree.h"
//创建一个新节点
BTNode* BuyNode(int x)
{
BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
if (newnode == NULL)
{
perror("malloc failed");
exit(0);
}
newnode->data = x;
newnode->left = newnode->right =NULL;
return newnode;
}
BTNode* creatBT()
{
BTNode* node1 = BuyNode(1);
BTNode* node2 = BuyNode(2);
BTNode* node3 = BuyNode(3);
BTNode* node4 = BuyNode(4);
BTNode* node5 = BuyNode(5);
BTNode* node6 = BuyNode(6);
node1->left = node2;
node1->right = node4;
node2->left = node3;
node4->left = node5;
node4->right = node6;
return node1;
}
//前序遍历
void PrevOrder(BTNode* root)
{
if (root == NULL)
{
printf("N ");
return;
}
printf("%d ", root->data);//输出当前数值
PrevOrder(root->left);//然后递归进行
PrevOrder(root->right);
}
//中序遍历
void InOrder(BTNode* root)
{
if (root == NULL)
{
printf("N ");
return;
}
InOrder(root->left);//先递归,等到最后一个之后再进行输出
printf("%d ", root->data);
InOrder(root->right);
}
//后序遍历
void BackOrder(BTNode* root)
{
if (root == NULL)
{
printf("N ");
return;
}
BackOrder(root->left);
BackOrder(root->right);
printf("%d ", root->data);
}
//节点个数
int treesize(BTNode* root)
{
if (root == NULL)return 0;
else return treesize(root->left) + treesize(root->right) + 1 ;
}
int TreeSize(BTNode* root)
{
static int size = 0;//用局部静态变量,只初始化一次。
if (root == NULL)
{
return 0;
}
else
{
++size;
}
TreeSize(root->left);
TreeSize(root->right);
return size;
}
//求叶子节点个数
int TreeLeafSize(BTNode* root)
{
if (root == NULL)
{
return 0;
}
if (root->left == NULL && root->right == NULL)
{
return 1;
}
return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}
int TreeHeigh(BTNode* root)
{
if (root == NULL)
{
return 0;
}
int leftheight = TreeHeigh(root->left);
int rightheight = TreeHeigh(root->right);
return leftheight > rightheight ?
leftheight + 1 : rightheight + 1;
}
int main()
{
BTNode* root = creatBT();
InOrder(root);
printf("\n");
int ret = TreeSize(root);
std::cout << "TreeSize:" << ret << std::endl;
ret = treesize(root);
std::cout << "TreeSize:" << ret << std::endl;
ret = TreeLeafSize(root);
std::cout << "TreeLeafSize:" << ret << std::endl;
int heigh = TreeHeigh(root);
std::cout << "TreeHeigh:" << heigh << std::endl;
return 0;
}