目录
谢谢帅气美丽且优秀的你看完我的文章还要点赞、收藏加关注
没错，说的就是你，不用再怀疑！！！
希望我的文章内容能对你有帮助，一起努力吧！！！
1、树与二叉树
1.1树的概念
树（tree）是n（n>=0）个结点的有限集,在任意一棵非空树中
- 有且仅有一个特点的结点称为（root）根结点
- 当n>1的时候，其余结点可以分为m（m>0）个互不相交有限集:T1、T2、T3...Tm。其中每一个有 限集，又可以看成是一棵树，并且称之为根的子树
树结点包含一个数据元素以及若干个指向其子树的分支（指针）
结点层次
结点层次：从根开始定义的，根结点为第一层、根的子结点（孩子）为第二层、....、树中结点的最大的 层次称为：树的高度（height）或者说是树的深度（depth）
结点的度
结点的度：结点拥有的子树的数量：度。度为0的结点称为：叶子结点(leaf)或者是终端结点、度不为0 的结点：分支结点
代码示例：
#include <iostream>
// 用来记录树子结点信息的结点
typedef struct node_infor
{
int index;
struct node_infor *next;
}Infor;
// 树的结点
typedef struct tree_node
{
int value;
Infor *tree_node_ptr;
}TreeNode;
void addNode(TreeNode *tree,Infor *node)
{
Infor *node_ptr = tree->tree_node_ptr;
if(node_ptr == nullptr)
{
tree->tree_node_ptr = node;
return ;
}
// 找到下一个为空的位置
while(node_ptr->next)node_ptr = node_ptr->next;
// 尾插法
node_ptr->next = node;
}
void frontPrint(TreeNode *tree,int index)
{
std::cout << tree[index].value << " ";
Infor *node_ptr = tree[index].tree_node_ptr;
while(node_ptr)
{
frontPrint(tree,node_ptr->index);
node_ptr = node_ptr->next;
}
}
int main()
{
// 创建一棵树
TreeNode tree[10];
// 初始化树的结点
for(int i = 0;i < 10;i++)
{
tree[i].value = i+1;
tree[i].tree_node_ptr=nullptr;
}
// 设置关系
Infor *node = new Infor;
node->index = 1;
node->next = nullptr;
addNode(&tree[0],node);
node = new Infor;
node->index = 2;
node->next = nullptr;
addNode(&tree[0],node);
node = new Infor;
node->index = 3;
node->next = nullptr;
addNode(&tree[0],node);
node = new Infor;
node->index = 4;
node->next = nullptr;
addNode(&tree[1],node);
node = new Infor;
node->index = 5;
node->next = nullptr;
addNode(&tree[2],node);
node = new Infor;
node->index = 6;
node->next = nullptr;
addNode(&tree[2],node);
node = new Infor;
node->index = 7;
node->next = nullptr;
addNode(&tree[2],node);
node = new Infor;
node->index = 8;
node->next = nullptr;
addNode(&tree[3],node);
node = new Infor;
node->index = 9;
node->next = nullptr;
addNode(&tree[3],node);
frontPrint(tree,0);
std::cout << std::endl;
}2、二叉树
二叉树是一种树的形状结构
它的特点：
- 它的每一个结点最多最多只能有两个子树，也就是说二叉树它不能存在度大于2的结点
- 二叉树的子树称为：左子树、右子树。注意：子树的次序不能颠倒
2.1二叉树的五大形态
- 空二叉树
- 只有一个根结点的二叉树
- 只有一个左子树的二叉树
- 只有一个右子树的二叉树
- 左右子树都存在的二叉树（完全二叉树）
2.2二叉树的性质
在二叉树的第i层上至多有2^(i-1)个结点(i>=1)
- 在任何一棵二叉树下，如果其终端结点（叶子结点）个数为n0，度为2的结点树为n2,则有n2=n0-1
- 满二叉树：
- 一棵深度为k具有2^k-1个结点的二叉树（在不改变二叉树的深度情况下，不能增加新的 结点的二叉树）
- 完全二叉树：
- 除去最后一层之后，就是一棵满二叉树
- 最后一层结点必须要是从左至右排列
- 满二叉树：
- 具有n个结点的完全二叉树，如果自上而下，自左到右，从1到n进行编号，那么变好的为i的结点， 它的左结点（如果存在）那么比编号为：2i、右结点（如果存在）那么编号：2i+1，它的父结点编 号：i/2
具有n个结点完全二叉树的深度为(log2N)+1向下取整
2.3二叉树的存储结构
- 顺序存储结构
- 数组
- 链式存储结构
2.4二叉树的遍历
如何按照某条搜索路径去访问树里面的每一个结点，使得每一个结点均被访问一次，而且只能访问一 次，”访问“的含义很广，可以是对数据进行打印，修改，对比...
- 先序访问
- 先访问根结点，再访问左子树，最后访问右子树（根左右）
- 中序访问
- 先访问左子树，再访问根结点，最后访问右子树（左根右）
- 后序访问
- 先访问左子树，再访问右子树，最后访问根结点（左右根）
- 注意：先中后序访问需要把左右子树都作为一棵正常的树来看待
- 先序，中序，后序是针对于根来说的，就是围绕根结点（把当前结点看做根结点使用），若左和右 不是终端结点，则会继续深入（递归）遍历，但是每次访问的结点都会当做根结点使用。
- 层次遍历：
- 一层一层的去遍历元素