【数据结构与算法】第19篇：树与二叉树的基础概念

一、什么是树1.1 树的定义树是 nn ≥ 0个节点的有限集合。当 n 0 时称为空树。任意非空树满足有且仅有一个根节点其余节点可分为 m 个互不相交的子树现实中的例子文件系统、公司组织架构、网页DOM树。1.2 树的术语画一棵树来理解textA ← 根节点 / | \ B C D ← 子树 / \ | E F G ← 叶子节点术语说明示例根节点树的最顶层节点A父节点直接上层节点A是B、C、D的父节点子节点直接下层节点B、C、D是A的子节点兄弟节点同一父节点的节点B、C、D互为兄弟叶子节点没有子节点的节点E、F、G度节点拥有的子节点个数A的度是3B的度是2树的度所有节点度的最大值树的度是3深度从根到该节点的层数根深度为1B的深度是2高度从该节点到最远叶子的距离A的高度是3二、二叉树2.1 二叉树的定义二叉树是每个节点最多有两个子树的树结构子树分为左子树和右子树左右有序。ctypedef struct TreeNode { int data; struct TreeNode *left; struct TreeNode *right; } TreeNode;2.2 二叉树的特点每个节点最多有两棵子树左右子树有顺序不能颠倒二叉树可以是空树2.3 特殊的二叉树满二叉树所有分支节点都有左右子树且所有叶子节点都在同一层。text1 / \ 2 3 / \ / \ 4 5 6 7完全二叉树除了最后一层其他层都是满的且最后一层的叶子节点都靠左排列。text1 / \ 2 3 / \ / 4 5 62.4 二叉树的性质性质内容性质1第 i 层最多有 2^(i-1) 个节点性质2深度为 k 的二叉树最多有 2^k - 1 个节点性质3叶子节点数 度为2的节点数 1性质4n 个节点的完全二叉树深度为 ⌊log₂n⌋ 1性质3的推导设 n0 为叶子节点数n1 为度为1的节点数n2 为度为2的节点数总节点数n n0 n1 n2总边数n - 1 n1 2n2相减得n0 n2 1三、二叉树的顺序存储3.1 存储方式用数组存储二叉树按完全二叉树的编号规则将节点放入数组对应位置。编号规则根节点编号为1编号 i 的左孩子2i编号 i 的右孩子2i 1编号 i 的父节点⌊i/2⌋text1(0) / \ 2(1) 3(2) / \ / 4(3) 5(4) 6(5) 数组存储[0, 1, 2, 3, 4, 5, 6] 下标 0 1 2 3 4 5 63.2 顺序存储的优缺点优点随机访问通过下标快速定位节点适合满二叉树和完全二叉树缺点空间浪费非完全二叉树会留下大量空位插入删除不方便3.3 代码实现c#include stdio.h #include stdlib.h #define MAX_SIZE 100 typedef struct { int data[MAX_SIZE]; int size; // 实际节点个数 } SeqBinaryTree; // 初始化 void initTree(SeqBinaryTree *tree) { for (int i 0; i MAX_SIZE; i) { tree-data[i] 0; // 0表示空节点 } tree-size 0; } // 设置根节点 void setRoot(SeqBinaryTree *tree, int value) { tree-data[1] value; tree-size 1; } // 设置左孩子父节点索引为p从1开始 void setLeft(SeqBinaryTree *tree, int parent, int value) { int idx parent * 2; if (idx MAX_SIZE) { printf(索引越界\n); return; } tree-data[idx] value; if (idx tree-size) tree-size idx; } // 设置右孩子 void setRight(SeqBinaryTree *tree, int parent, int value) { int idx parent * 2 1; if (idx MAX_SIZE) { printf(索引越界\n); return; } tree-data[idx] value; if (idx tree-size) tree-size idx; } // 获取左孩子 int getLeft(SeqBinaryTree *tree, int parent) { int idx parent * 2; if (idx tree-size) return 0; return tree-data[idx]; } // 获取右孩子 int getRight(SeqBinaryTree *tree, int parent) { int idx parent * 2 1; if (idx tree-size) return 0; return tree-data[idx]; } // 获取父节点 int getParent(SeqBinaryTree *tree, int child) { if (child 1) return 0; int idx child / 2; return tree-data[idx]; } // 打印树按层 void printTree(SeqBinaryTree *tree) { printf(二叉树数组存储下标从1开始\n); for (int i 1; i tree-size; i) { if (tree-data[i] ! 0) { printf(data[%d]%d, i, tree-data[i]); // 打印父节点信息 if (i 1) { printf( (父节点: %d), getParent(tree, i)); } printf(\n); } } } int main() { SeqBinaryTree tree; initTree(tree); // 构建一个完全二叉树 setRoot(tree, 1); setLeft(tree, 1, 2); setRight(tree, 1, 3); setLeft(tree, 2, 4); setRight(tree, 2, 5); setLeft(tree, 3, 6); printTree(tree); printf(\n节点2的左孩子: %d\n, getLeft(tree, 2)); printf(节点3的右孩子: %d\n, getRight(tree, 3)); printf(节点6的父节点: %d\n, getParent(tree, 6)); return 0; }运行结果text二叉树数组存储下标从1开始 data[1]1 data[2]2 (父节点: 1) data[3]3 (父节点: 1) data[4]4 (父节点: 2) data[5]5 (父节点: 2) data[6]6 (父节点: 3) 节点2的左孩子: 4 节点3的右孩子: 0 节点6的父节点: 3四、满二叉树与完全二叉树的性质4.1 满二叉树性质说明节点数深度为k节点数 2^k - 1叶子节点都在最后一层叶子数 2^(k-1)度为1的节点0个4.2 完全二叉树性质说明节点数深度为k节点数在 [2^(k-1), 2^k-1] 之间叶子节点只能在最后两层顺序存储适合用数组存储没有空间浪费完全二叉树的顺序存储特点按层序遍历的顺序存入数组下标 i 的节点左孩子下标 2i右孩子下标 2i1如果 2i n则没有左孩子如果 2i1 n则没有右孩子五、二叉树与树的区别对比项树二叉树节点度数无限制最多2子树顺序无序有序左右区分空树通常不允许允许六、小结这一篇我们学习了树和二叉树的基础概念要点说明树术语根、叶子、度、深度、高度二叉树每个节点最多两个子节点左右有序满二叉树所有层满节点数 2^k-1完全二叉树最后一层靠左排列适合数组存储顺序存储用数组下标模拟父子关系2i, 2i1核心公式第i层最多节点数2^(i-1)深度k的二叉树最多节点数2^k - 1叶子节点数 度为2的节点数 1下一篇我们讲二叉树的链式存储和四种遍历方式。七、思考题一棵完全二叉树有100个节点它的叶子节点有多少个一棵二叉树的叶子节点数为20度为2的节点数是多少顺序存储中如何判断一个节点是否有左孩子如何判断是否有右孩子为什么完全二叉树适合用数组存储而普通二叉树不适合欢迎在评论区讨论你的答案。