树是数据结构中最重要的非线性结构之一二叉树的遍历、线索化和存储结构是 408 考研的绝对重点。一、树的基本概念1. 术语A (根节点) / \ B C / \ \ D E F (叶子节点) 根节点最顶层的节点A 叶子节点没有子节点的节点D、E、F 父节点B 是 D 和 E 的父节点 子节点D 和 E 是 B 的子节点 兄弟节点B 和 C 互为兄弟 树的深度从根到最远叶子经过的边数上图为 22. 二叉树的定义每个节点最多有两个子节点分别称为左孩子和右孩子。二叉树的五种基本形态 ① 空二叉树 ② 只有根节点 ③ 只有左子树 ④ 只有右子树 ⑤ 左右子树都有3. 两种特殊的二叉树满二叉树 1 / \ 2 3 / \ / \ 4 5 6 7 每层节点都满节点总数 2^(h1) - 1 完全二叉树 1 / \ 2 3 / \ / 4 5 6 除了最后一层其他层都是满的 最后一层的节点靠左排列二、二叉树的存储结构1. 顺序存储数组// 用数组存储完全二叉树// 下标从 1 开始// 节点 i 的左孩子 2i// 节点 i 的右孩子 2i 1// 节点 i 的父节点 i / 2int[]treenewint[n1];tree[1]1;// 根节点tree[2]2;// 左孩子tree[3]3;// 右孩子适用于满二叉树和完全二叉树普通二叉树会浪费大量空间。2. 链式存储最常用publicclassTreeNode{intval;TreeNodeleft;// 左孩子TreeNoderight;// 右孩子publicTreeNode(intval){this.valval;}}// 构建一棵二叉树TreeNoderootnewTreeNode(1);root.leftnewTreeNode(2);root.rightnewTreeNode(3);root.left.leftnewTreeNode(4);root.left.rightnewTreeNode(5);三、二叉树的遍历遍历是二叉树最基础的操作前、中、后三种遍历的递归和非递归写法都要能手写。1. 前序遍历根→左→右// 递归publicvoidpreorder(TreeNoderoot){if(rootnull)return;System.out.print(root.val );// 访问根preorder(root.left);// 遍历左子树preorder(root.right);// 遍历右子树}// 输出: 1 2 4 5 3 6// 非递归栈publicvoidpreorderIterative(TreeNoderoot){if(rootnull)return;StackTreeNodestacknewStack();stack.push(root);while(!stack.isEmpty()){TreeNodenodestack.pop();System.out.print(node.val );if(node.right!null)stack.push(node.right);// 右先入栈if(node.left!null)stack.push(node.left);// 左后入栈先出}}2. 中序遍历左→根→右// 递归publicvoidinorder(TreeNoderoot){if(rootnull)return;inorder(root.left);// 遍历左子树System.out.print(root.val );// 访问根inorder(root.right);// 遍历右子树}// 输出: 4 2 5 1 3 6// 非递归栈publicvoidinorderIterative(TreeNoderoot){StackTreeNodestacknewStack();TreeNodecurrroot;while(curr!null||!stack.isEmpty()){while(curr!null){stack.push(curr);currcurr.left;// 一路向左}currstack.pop();System.out.print(curr.val );currcurr.right;// 转向右子树}}3. 后序遍历左→右→根// 递归publicvoidpostorder(TreeNoderoot){if(rootnull)return;postorder(root.left);// 遍历左子树postorder(root.right);// 遍历右子树System.out.print(root.val );// 访问根}// 输出: 4 5 2 6 3 1// 非递归双栈法publicvoidpostorderIterative(TreeNoderoot){if(rootnull)return;StackTreeNodes1newStack();StackTreeNodes2newStack();s1.push(root);while(!s1.isEmpty()){TreeNodenodes1.pop();s2.push(node);if(node.left!null)s1.push(node.left);if(node.right!null)s1.push(node.right);}while(!s2.isEmpty()){System.out.print(s2.pop().val );}}4. 层序遍历BFSpublicvoidlevelOrder(TreeNoderoot){if(rootnull)return;QueueTreeNodequeuenewLinkedList();queue.offer(root);while(!queue.isEmpty()){TreeNodenodequeue.poll();System.out.print(node.val );if(node.left!null)queue.offer(node.left);if(node.right!null)queue.offer(node.right);}}// 输出: 1 2 3 4 5 65. 遍历总结1 / \ 2 3 / \ \ 4 5 6 前序1 2 4 5 3 6 根左右 中序4 2 5 1 3 6 左根右 后序4 5 2 6 3 1 左右根 层序1 2 3 4 5 6 逐层从左到右四、线索二叉树1. 为什么要线索化普通二叉树中n 个节点有 2n 个指针域但只有 n-1 个被使用根节点没有父指针大量指针域被浪费。线索二叉树利用这些空指针指向遍历顺序中的前驱和后继。中序线索化后 1 / \ 2 3 / \ \ 4 5 6 中序序列: 4 2 5 1 3 6 4 的前驱 null, 4 的后继 2 2 的前驱 4, 2 的后继 5 (2 本身有左右孩子不用线索) 5 的前驱 2, 5 的后继 1 1 的前驱 5, 1 的后继 3 (1 本身有左右孩子不用线索) 3 的前驱 1, 3 的后继 6 6 的前驱 3, 6 的后继 null2. 线索二叉树的节点结构publicclassThreadedTreeNode{intval;ThreadedTreeNodeleft;ThreadedTreeNoderight;intltag;// 0: left 指向左孩子, 1: left 指向前驱intrtag;// 0: right 指向右孩子, 1: right 指向后继}3. 中序线索化classThreadedBinaryTree{privateThreadedTreeNoderoot;privateThreadedTreeNodeprev;// 记录前驱节点publicvoidthreaded(){prevnull;inorderThreaded(root);// 处理最后一个节点if(prev!null)prev.rtag1;}privatevoidinorderThreaded(ThreadedTreeNodenode){if(nodenull)return;// 1. 线索化左子树inorderThreaded(node.left);// 2. 处理当前节点if(node.leftnull){node.leftprev;// 左指针指向前驱node.ltag1;}if(prev!nullprev.rightnull){prev.rightnode;// 前驱的右指针指向当前节点prev.rtag1;}prevnode;// 3. 线索化右子树inorderThreaded(node.right);}}五、408 考研经典考题题1已知前序和中序重构二叉树前序: 1 2 4 5 3 6 中序: 4 2 5 1 3 6 解题思路 1. 前序第一个 根 1 2. 中序中找 1左边是左子树(4,2,5)右边是右子树(3,6) 3. 前序剩余中2 4 5 是左子树的前序3 6 是右子树的前序 4. 递归... 1 / \ 2 3 / \ \ 4 5 6题2求二叉树深度publicintmaxDepth(TreeNoderoot){if(rootnull)return0;returnMath.max(maxDepth(root.left),maxDepth(root.right))1;}题3判断二叉树是否对称publicbooleanisSymmetric(TreeNoderoot){if(rootnull)returntrue;returnisMirror(root.left,root.right);}privatebooleanisMirror(TreeNodeleft,TreeNoderight){if(leftnullrightnull)returntrue;if(leftnull||rightnull)returnfalse;return(left.valright.val)isMirror(left.left,right.right)isMirror(left.right,right.left);}题4根据遍历序列确定二叉树已知前序和中序可以唯一确定一棵二叉树 已知后序和中序可以唯一确定一棵二叉树 已知前序和后序不能唯一确定缺少中序信息六、二叉树的性质公式1. 第 i 层最多有 2^(i-1) 个节点i ≥ 1 2. 深度为 h 的二叉树最多有 2^h - 1 个节点 3. n0 n2 1叶子节点数 度为2的节点数 1 4. 完全二叉树中编号为 i 的节点 - 左孩子 2i如果 ≤ n - 右孩子 2i 1如果 ≤ n - 父节点 i/2性质 3 证明设 n0 叶子节点数n1 度为1的节点数n2 度为2的节点数 总节点数 n n0 n1 n2 总边数 n - 1 n1 2n2 n0 n1 n2 - 1 n1 2n2 n0 n2 1 ✅七、树的存储结构1. 双亲表示法// 每个节点存 parent 下标classPNode{intdata;intparent;// 父节点的数组下标}2. 孩子表示法// 每个节点存孩子链表classCNode{intdata;ListIntegerchildren;// 孩子节点下标列表}3. 孩子兄弟表示法最常用// 每个节点存第一个孩子和右兄弟classCSNode{intdata;CSNodefirstChild;// 第一个孩子CSNodenextSibling;// 右兄弟}// 将树转化为二叉树左孩子右兄弟// 任意一棵树都可以用二叉树来表示 觉得有用的话点赞 关注【张老师技术栈】吧每周更新 Java/Python/爬虫 实战干货不让你白来。