二叉树的链式表示

一、二叉树的表示前面我们讲过了二叉树的顺序表示堆现在来看一下如何用链式结构表示二叉树。要储存二叉树就要存储各个节点每个节点包含该节点的值和指向左右子树的指针typedef int BTDataType; typedef struct BinaryTreeNode { BTDataType data; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }BTNode;二、二叉树的遍历二叉树的遍历方式主要分为两大类深度优先遍历DFS和广度优先遍历BFS1.深度优先遍历DFS遍历方式访问顺序应用举例前序遍历Preorder根 → 左子树 → 右子树复制树、前缀表达式求值中序遍历Inorder左子树 → 根 → 右子树二叉搜索树BST可得到有序序列后序遍历Postorder左子树 → 右子树 → 根释放树节点、后缀表达式求值1前序遍历这里详细展示前序遍历过程void PrevOrder(BTNode* root) { if (root NULL) { printf(N ); return; } printf(%d , root-data); PrevOrder(root-left); PrevOrder(root-right); }按照红色箭头执行前序遍历二叉树的逻辑过程逻辑上每个函数调用都有自己“独立”的栈帧互不干扰。物理上系统会高效重用已释放的栈内存从而避免频繁分配/释放物理页提升性能。这种重用对程序员透明不需要也不能主动控制。2中序遍历void InOrder(BTNode* root) { if (root NULL) { printf(N ); return; } InOrder(root-left); printf(%d , root-data); InOrder(root-right); }3后序遍历void PostOrder(BTNode* root) { if (root NULL) { printf(N ); return; } PostOrder(root-left); PostOrder(root-right); printf(%d , root-data); }2.广度优先遍历BFS三、二叉树的节点计算1.树的节点总数树的节点总数的计算类似统计全校在校师生个数让校长一个一个计数计算起来是很麻烦的也不可能用这种方式实现应该从最底层开始计数让每一层上报。若为空则返回0否则就返回左子树与右子树节点个数之和1。int TreeSize(BTNode* root) { if (root NULL) { return 0; } return TreeSize(root-left) TreeSize(root-right) 1; }2.树的叶子节点数若rootNULL,则返回0若该节点指向左右子树的指针都为空则返回1否则返回左子树节点数右子树节点数int TreeSizeLeaf(BTNode* root) { if (root NULL) { return 0; } if (root-left NULL root-right NULL) { return 1; } return TreeSizeLeaf(root-left) TreeSizeLeaf(root-right); }3.树的层数如果rootNULL返回0否则返回左右子树中较大的层数1int TreeHeihgt(BTNode* root) { if (root NULL) { return 0; } return TreeHeihgt(root-left) TreeHeihgt(root-right) ? TreeHeihgt(root-left) 1 : TreeHeihgt(root-right) 1; }但其实这样没有记录每次算出来的层数会重复执行多次当数据量较大的时候效率会低应该用变量将其记录下来int TreeHeihgt(BTNode* root) { if (root NULL) { return 0; } int leftHeight TreeHeihgt(root-left); int rightHeight TreeHeihgt(root-right); return leftHeight rightHeight ? leftHeight 1 : rightHeight 1; }四、递归调用的本质代码只有一份函数的机器指令存储在内存的代码段中每次调用包括递归调用都是执行同一段指令。数据不同每次调用会创建新的栈帧stack frame其中存放参数如当前节点指针局部变量返回地址决定了递归返回后继续执行的指令位置结果不同正是由于栈帧中的数据不同例如当前遍历到的节点不同同一份指令才会产生不同的执行效果和最终结果。一个形象的类比就像一本烹饪书一份指令不同的人不同的栈帧数据按照同样的步骤做菜但因为各自拿到的食材不同参数不同做出来的菜自然不同。做菜时每人都有自己的操作台栈帧互不干扰。补充一点返回地址也是“数据”“压进栈的数据”不仅包括参数和局部变量还包括返回地址。返回地址决定了函数执行完毕后该回到哪里继续执行。即便都是调用同一个递归函数每次调用返回后会回到调用点下一行代码这个控制流差异也是依靠栈帧中保存的返回地址实现的。