树是一种非线性的数据结构,它是由 n(n >= 0)个有限个节点组成的一个具有层次关系的集合。把它叫做树是因为他看起来像一颗倒挂的树,也就是说,它是根朝上,而叶朝下的。
树的定义有两点: 1)有且仅有一个特定的称为根(root)的结点; 2)当结点数量>1时,其余结点可分为 若干个互不相交的有限集 ,其中每个集合也可以看作一颗树,称之为根的子树。
判断是否是一个树
几个重要的知识点:
树的结构相对线性表就相对复杂很多,要存储起来更加复杂。实际中树有很多种表示方法,如:双亲表示法、孩子表示法、孩子兄弟表示法等等
typedef int DataType;
struct Node
{
struct Node* firstChild1;//第一个孩子节点
struct Node* pNextBrother;//指向下一个兄弟节点
DataType data;//数据域
}
一棵二叉树是节点的一个有限集合,该集合或者为空,或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。
相关习题:
解析2:
解析3:
所谓遍历就是指沿着某条搜索路线,依次对树中的每个节点均做一次且仅做一次的访问。遍历二叉树是很重要的运算之一,是二叉树上进行其他运算的基础。
二叉树的前序、中序、后序遍历也称为深度优先遍历,因为他们都是先往下遍历的,而不管左右。
遍历方式:
代码实现:
#include
#include
typedef char BTDataType;
typedef struct BinaryTreeNode
{
struct BinaryTreeNode* left;//左孩子
struct BinaryTreeNode* right;//右孩子
BTDataType data;//数据域
}BTNode;
void PrevOrder(BTNode* root)//前序
{
if (root == NULL)
{
printf("NULL ");
return;
}
printf("%c ", root->data);
PrevOrder(root->left);
PrevOrder(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 main()
{
BTNode* A = (BTNode*)malloc(sizeof(BTNode));
A->data = 'A';
A->left = NULL;
A->right = NULL;
BTNode* B = (BTNode*)malloc(sizeof(BTNode));
B->data = 'B';
B->left = NULL;
B->right = NULL;
BTNode* C = (BTNode*)malloc(sizeof(BTNode));
C->data = 'C';
C->left = NULL;
C->right = NULL;
BTNode* D = (BTNode*)malloc(sizeof(BTNode));
D->data = 'D';
D->left = NULL;
D->right = NULL;
BTNode* E = (BTNode*)malloc(sizeof(BTNode));
E->data = 'E';
E->left = NULL;
E->right = NULL;
A->left = B;
A->right = C;
B->left = D;
B->right = E;
PrevOrder(A);
printf("\n");
InOrder(A);
printf("\n");
PostOrder(A);
printf("\n");
system("pause");
return 0;
}
我们主要要了解具体递归的顺序,我们可以自己在纸上画一画
层序遍历:除了先序遍历、中序遍历、后序遍历外,还可以对二叉树进行层序遍历。设二叉树的根节点所在的层数为1,层序遍历就是从所在二叉树的根节点出发,首先访问第一层的根节点,然后从左到右访问第二层上的节点,以此类推,自上而下,自左至右逐层访问树的节点的过程就是层序遍历,也称为广度优先遍历。
二叉树的广度优先遍历思想:我们利用队列(先进先出),上一层出的时候带着下一层进
//层序遍历 广度优先遍历
void LevelOrder(BTNode* root)
{
//核心思想——上一层出的时候带下一层节点进
queue<BTNode*> q;//创建队列容器
if (root)
{
q.push(root);//入队
}
while (!q.empty())
{
BTNode* front = q.front();
q.pop();
printf("%c ", front->data);
if (front->left)
{
q.push(front->left);
}
if (front->right)
{
q.push(front->right);
}
}
printf("\n");
}
二叉树遍历的例题:
答案为:A A D
很多人看到计算二叉树的节点个数,心想那么简单,直接遍历一下二叉树不就好了吗。
//节点个数
int size = 0;
void TreeSize(BTNode* root)
{
if (root == NULL)
{
return;
}
else
{
size++;
}
TreeSize(root->left);
TreeSize(root->right);
}
其实,vs2022已经报错了,为什么呢?因为我们定义了一个全局的size,在我们计算了节点为A的节点个数时,得到的大小是5,但是在计算节点为B的节点个数为8,。就是因为我们这个变量A是个全局变量,会累加的。
void TreeSize(BTNode* root, int* psize)
{
if (root == NULL)
{
return;
}
else
{
++(*psize);
}
TreeSize(root->left, psize);
TreeSize(root->right, psize);
}
int Asize = 0;
TreeSize(A, &Asize);
printf("TreeSize(A): %d", Asize);
int Bsize = 0;
TreeSize(B, &Bsize);
printf("TreeSize(A): %d", Bsize);
我们要记得把地址传过去。
但是,如果我们知道多线程的时候,程序在运行时,可能有多个进程在同时进行,我们就无法保证在求一个节点的数时的节点前,先把size赋值为0了。怎么办呢?看下面的代码就很好的解决了这个问题。
//返回节点个数
int TreeSize(BTNode* root)
{
return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}
这个程序很巧,我们求一棵二叉树节点个数,就计算它左子树节点个数 + 右子树节点个数 + 1(根节点)
计算叶子节点个数和求节点个数的思想是一样的
//求叶子节点个数
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);
}