【初阶数据结构】树和二叉树的基本概念和结构
【初阶数据结构】树和二叉树的基本概念和结构
1.树的概念
学二叉树之前得先学树，后面也有能用到树的知识，比如并查集就是树当中的森林
1-1树的概念
树是一种非线性的数据结构，它是由N（N>=0）个有限结点组成的层次关系的集合，说它是树主要是因为他很像一棵倒挂的树，也就是根在是上，枝叶在下。
- A为根结点，根节点没有前驱结点
- 树是递归定义的，树中最基本的关系就是父子关系，A是B和C的父节点，同时B也是D的父节点。（任何一棵树都可以分为根和子树）
上面两个图都不是树，因为树内部不能出现环，出现环就是我们后面要讲的图
1-2.树中的亲缘关系名词
- 结点的度：一个结点所含子树的个数，比如结点A的度为2
- 叶子结点或终端结点：度为0的结点，比如结点D，G和E
- 分支结点或非终端结点：度不为0的结点，比如结点A,B和C
- 父节点或双亲结点：若一个结点有子节点，那么这个结点就被称为父节点，比如A是B和C的父节点
- 子节点或孩子结点：同理，比如B和C是A的子节点
- 兄弟节点：具有相同父节点的结点，比如B和C是兄弟结点（亲兄弟）
- 堂兄弟结点：父节点都在同一层的结点，比如D和G,E
- 树的度：一棵树中，最大的结点的度被称为树的度，比如该树的结点是2
- 结点的层次：从根开始定义，如果规定根为第一层，以此类推（推荐） 备注：如果规定根为第0层，以此类推也行，但数组从0开始时因为偏移量，这里没必要 而且如果一个如果要表示空树，显然规定根为第一层，更能合乎情理表示空树
- 结点的祖先：从根到该节点的经过分支的所有结点，比如G的祖先是A和C
- 结点的子孙：以某一个结点为根的子树中的任意一个结点，比如C的子孙是G和E
- 森林：由m(m>0)棵互不相交的树的集合
2.树的存储方式
2-1兄弟孩子表示法
不那么合适的写法： 由于我们不知道树的结点的度为多少，所以在树的结点定义的时候直接定义有点麻烦
//一：结点的度不知道，我怎么设计呐？
struct TreeNode
{
int data;
struct TreeNode* childNode1;
struct TreeNode* childNode2;
struct TreeNode* childNode3;
//...
};
//二：如果明确树的度
//静态顺序表：
#define N 5
struct TreeNode
{
int data;
struct TreeNode* childArr[N];
int childSize;
};
//缺点：但是这是树的度，不是每一个结点的度，会造成数组空间浪费
//三：动态顺序表：
struct TreeNode
{
int data;
struct TreeNode** childArr;
int childSize;
};最合适的写法： 兄弟孩子表示法
typedef int DataType;
struct TreeNode
{
struct TreeNode* firstchild1;//第一个孩子结点
struct TreeNode* pNextBrother;//指向第一个兄弟结点
DataType _data;
};
Linux目录系统结构：（树）
2-2双亲表示法
任意一个结点找祖先
3.满二叉树和完全二叉树
二叉树：度为2的树；二叉树的结点的度只能为0或者2
任何二叉树都是由以下结构复合而成的
特殊的二叉树：
- 满二叉树：每一层都是满的， 如果有K层，第K层结点个数：2^(K-1) ; 总结点个数：2^k-1
- 完全二叉树：如果有K层，则前K-1层必须是 满的，最后一层满或不满都可以 K层，结点数量范围是【2^(K-1),2^K-1】
4.二叉树的性质
- 性质1：在二叉树的第i层上至多有2^(i-1)个结点（数学归纳法或者错位相减法证明）
- 性质2：深度为i的二叉树至多有2^i-1个结点 （数学归纳法或者错位相减法证明）
- 性质3：对于任意一棵二叉树，若叶子数为n0,度为2的结点有n2,则n0=n2+1（数学归纳法）
- 性质4：具有n个结点的完全二叉树必为LogN+1（数学推导证明如下）
5.二叉树的顺序存储和链式存储
5-1二叉树的顺序存储
结论：完全二叉树很适合顺序存储，但是普通二叉树不适合顺序存储
不难看出：完全二叉树只要按照结点层次放到数组中即可 但是普通二叉树由于有些位置的空缺，而二叉树的左右结点是有顺序的，所以会导致一部分空缺，造成空间的浪费，及不推荐。
5-2链式存储
利用二叉链表就可以解决上面普通链表不适合用顺序存储的缺点，如果左孩子不存在则为NULL
typedef int DataType;
typedef struct Btree
{
DataType data;
struct Btree* lchild, rchild;
}Btree;5-3变式：三叉链表
在实际问题中，我们有时候还需要访问双亲结点，二叉链表存储则需要从根节点出发查找到双亲结点，这样显得有点麻烦，所以有的时候，为了方便我们往往还可以使用到三叉链表，也就是在二叉链表，存储左孩子和右孩子的地址的同时，额外存储结点的双亲结点。
6.二叉树的前中后序遍历
二叉树的遍历就是按照某条路径访问二叉树的每一个结点有且仅有一次，二叉树的访问范围很广：输出，查找，插入，修改，删除等，如果我们规定左右子树的访问顺序只能是先左后右，那么就只有3种访问顺序：DLR,LDR,LRD,按照根访问的时机先后，分别叫做先序遍历，中序遍历和后序遍历。
这里其实使用的是一种递归的思想：以前序遍历为例，我们规定一种规则，就是先访问他的根，再访问他的左子树和右子树，而左子树又是一棵二叉树，同样是递归访问他的左子树，再去访问他的右子树....以此类推。
这就好比是：要把所有的犯人抓住，我们规定了一种方式就是先抓住头头，然后抓完了头头的所有左翼，才能抓头头的右翼，然后抓左翼的时候，又有头头，又是抓完了头头的所有左翼，才能抓头头的右翼...
下面以下图为例，给大家写一下代码：
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
typedef struct BTNode
{
int val;
struct BTNode* left;
struct BTNode* right;
}BTNode;
BTNode* CreateBTree()
{
BTNode* n1 = (BTNode*)malloc(sizeof(BTNode));
BTNode* n2 = (BTNode*)malloc(sizeof(BTNode));
BTNode* n3 = (BTNode*)malloc(sizeof(BTNode));
BTNode* n4 = (BTNode*)malloc(sizeof(BTNode));
BTNode* n5 = (BTNode*)malloc(sizeof(BTNode));
BTNode* n6 = (BTNode*)malloc(sizeof(BTNode));
n1->val = 1;
n2->val = 2;
n3->val = 3;
n4->val = 4;
n5->val = 5;
n6->val = 6;
n1->left = n2;
n1->right = n4;
n2->left = n3;
n2->right=NULL;
n3->left = NULL;
n3->right = NULL;
n4->left = n5;
n4->right = n6;
n5->left = NULL;
n5->right = NULL;
n6->left = NULL;
n6->right = NULL;
return n1;
}
void PrevOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
printf("%d ", root->val);
PrevOrder(root->left);
PrevOrder(root->right);
}
void InOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
InOrder(root->left);
printf("%d ", root->val);
InOrder(root->right);
}
void PostOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf("%d ", root->val);
}
int main()
{
BTNode* root = CreateBTree();
//前序遍历
PrevOrder(root);
printf("\n");
//中序遍历
InOrder(root);
printf("\n");
//后序遍历
PostOrder(root);
return 0;
}
7.求二叉树总结点个数
相信你理解了二叉树的三种常见的遍历方式，这道题不难破解，似乎就是在把打印的部分换成一个计数器计数就可以了，但是事情似乎没有你想象的那么简单，因为你或许会犯以下的小错误：（不加static是大错，加static就是有一点小毛病，static只初始化一次）
错误示范1:
int TreeSize(BTNode* root)
{
int size = 0;//每一次递归调用都会初始化size=0;使得最终的结果为1
if (root == NULL)
{
return 0;
}
++size;
TreeSize(root->left);
TreeSize(root->right);
return size;
}
于是聪明的你又想到了使用satic只能初始化一次，但是似乎....
static int size = 0;//这样使得以后这个程序里所有再次调用这个TreeSize函数都不会再初始化
//但是这也是问题所在，直接封杀了我如果想再次调用这个函数求一下TreeSize的int TreeSize(BTNode* root)
{
static int size = 0;//这样使得以后这个程序里所有再次调用这个TreeSize函数都不会再初始化
//但是这也是问题所在，直接封杀了我如果想再次调用这个函数求一下TreeSize的想法。
if (root == NULL)
{
return 0;
}
++size;
TreeSize(root->left);
TreeSize(root->right);
return size;
}
所以最好的方法还得是下面这种方法：
int TreeSize(BTNode* root)
{
if (root == NULL)
{
return 0;
}
return 1 + TreeSize(root->left) + TreeSize(root->right);
}
return 1 + TreeSize(root->left) + TreeSize(root->right);
//这里值得注意的是，因为要求二叉树的总结点，必然要遍历整个二叉树，那么遍历采用的是
//前序遍历还是中序遍历还是后序遍历都是无所谓的，所以1的位置相对于非空结点的左右子树递归都是任意的(这里其实左右子树的递归顺序也是未定义的)8.求二叉树的叶子结点
求二叉树的叶子结点，遍历整棵二叉树是一定的，但是这次我们要计数的不是所有的结点，而是叶子结点,
到了这里，我觉得我们应该把一棵二叉树分成空结点&非空节点 或者将非空节点再细分为非叶子结点和叶子结点吗，也就是空结点，非叶子结点，叶子结点 在这题的话就是说对于空结点统计为0，叶子结点统计为1，非叶子结点就递归他的左子树和右子树就完了,并且统计为0(这里代码中隐式为0,没有写出)
if (root == NULL)
{
return 0;
}
//这里过滤掉的是空节点，并且返回0后面统计 if (root->left == NULL && root->right == NULL)
{
return 1;
}
//这里过滤的是叶子结点,并且叶子结点要返回1给后面统计 return TreeLeftSize(root->left) + TreeLeftSize(root->right);
//这里就是对非空结点中的非叶子结点的左子树和右子树进行递归(并且既然root是非叶子结点的话就不用+1)这里我觉得递归的 return TreeLeftSize(root->left) + TreeLeftSize(root->right);这段从近root的来看就是意味着是root的左右节点,从远的递归的角度来看却是左右子树的性质,显然是第二种远的角度来看合理一点.
int TreeLeftSize(BTNode* root)
{
if (root == NULL)
{
return 0;
}
if (root->left == NULL && root->right == NULL)
{
return 1;
}
return TreeLeftSize(root->left) + TreeLeftSize(root->right);
}到了这里我希望你能看出这道题和上道题目的一点区别:(画框的区域代表的是遍历的区域)
9.求二叉树的高度
这里我们要求二叉树的高度,首先我们就得知道针对得对象是非叶子节点,就得先递归求出左子树和右子树的高度,然后进行比较再分析一下才能求出整个二叉树的高度,所以这里我们得采用类似后序遍历得方式进行求二叉树的高度, 思路:父亲的高度=左右子树高度的最大值+1
int TreeHeight(BTNode* root)
{
if (root == NULL)
{
return 0;
}
return TreeHeight(root->left) > TreeHeight(root->right) ? TreeHeight(root->left)+1 : TreeHeight(root->right)+1;
}
腾讯云开发者
