二叉树基本知识

引言

二叉树作为数据结构中的难点，这篇文章将介绍关于二叉树的基本知识

二叉树相关命名

标红的为比较重要的，下面我将通过画图的方式帮助你更好的理解

树的结构体设计

struct TreeNode

{

int val; //数据

struct TreeNode* left; //左子树

struct TreeNode* right; //右子树

}

二叉树的类型

• 满二叉树

指每一层的叶子都是满的，其高度为h，总节点个数为2^h – 1，如图：

• 完全二叉树

高度为h的二叉树，前h-1层都是满二叉树，最后一层不满，但是从左到右的叶子是连续的，如图：

二叉树父子节点之间的关系

假设父节点为j，左孩子节点为i，右孩子节点为i+1

则 j = (i – 1) / 2，也就是 父节点 = （孩子节点 – 1）/ 2

要注意的是这里的孩子节点是左右孩子节点都是成立的，因为要除以2，但是1除以2在c语言中是为0的，不会影响最后的结果

而 i = j*2 + 1，也就是 左孩子节点 = 父节点 * 2 + 1， 右孩子节点 = 父节点 * 2 + 2

总结

这篇文章只是一点二叉树基础的引入，更重要的还在后面，加油加油