二叉树知识整理：结构、性质与遍历实现

文章目录1. 树型结构1.1 了解树2.二叉树2.1 二叉树的概念2.1.1 特殊的两种二叉树2.2 二叉树的性质2.2.1 性质推导2.3 二叉树的存储2.3.1 二叉树的链式存储2.3.2 二叉树的顺序存储2.4 二叉树的基本操作2.4.1 二叉树的三种遍历1.前序遍历2.中序遍历3.后序遍历2.4.2 二叉树的其他操作1. 获取树中节点个数2. 获取叶子节点个数3. 获取二叉树的高度4. 层序遍历二叉树 Oj 练习1. 树型结构1.1 了解树形如图中的结构称之为树型结构。实际上数据结构的树 图论中的树 根节点 父子关系对于数据结构中树的定义树是由 nn 0个节点但组成的有限集合。其中树的一些基本概念有以下节点的度一个节点含有子树的个数称为该节点的度树的度一棵树中所有节点度的最大值称为树的度上图树的度为 3叶子节点或终端节点度为 0 的节点称为叶子节点双亲节点或父节点若一个节点含有子节点则这个节点称为其子节点的父节点根节点一棵树中没有双亲节点的节点树的高度或深度树中节点的最大层次上图树的高度为 4非终端节点或分支节点度不为 0 的节点2.二叉树2.1 二叉树的概念二叉树是一个有限节点集合满足可以是空集空二叉树如果不为空则由三部分组成根节点Root、左子树Left Subtree、右子树Right Subtree)并且左子树和右子树本身也是二叉树2.1.1 特殊的两种二叉树满二叉树一棵二叉树若每层的节点树都达到最大值则这棵二叉树就是满二叉树。从数学关系上看一颗二叉树的层数为 K则节点总数为 2k- 1则它就是满二叉树。完全二叉树除了最后一层外其余各层都被完全填满并且最后一层的节点从左至右连续排列中间不能空缺图像概念如下2.2 二叉树的性质若规定根结点的层数为1则一棵非空二叉树的第i层上最多有2i-1(i0)个结点若规定只有根结点的二叉树的深度为1则深度为K的二叉树的最大结点数是 2k- 1(k0)对任何一棵二叉树, 如果其叶结点个数为n0,度为2的非叶结点个数为n2,则有n0n21具有n个结点的完全二叉树的深度k为 log2(n1)上取整对于具有n个结点的完全二叉树如果按照从上至下从左至右的顺序对所有节点从0开始编号则对于序号为 i 的节点有若 i 0,双亲序号(i - 1)/2; i 0,i 为根节点编号无双亲节点若2i1n左孩子序号2i1否则无左孩子若2i2n右孩子序号2i2否则无右孩子2.2.1 性质推导对于性质 3我们给出以下推导已知一棵 N 个节点的树有 N-1 条边下标 1、2 分别代表度为 12 的节点能产生的边数n1:产生 n1-1 条边n2:产生 2*n2条边n1 2*n2 N - 1 方程式 1n0 n1 n2 N 方程式 2联立解得n2 1 n02.3 二叉树的存储二叉树的存储结构分为顺序存储和链式存储2.3.1 二叉树的链式存储二叉树的链式存储是通过一个个的节点引用起来的常见的表示方式有二叉链表、三叉链表、线索二叉树表示方法链式存储使用情况形状不规则的普通二叉树动态变化的二叉树需要实现复杂逻辑的树//二叉链表classNode{intval;// 数据域Nodeleft;// 左孩子的引用常常代表左孩子为根的整棵左子树Noderight;// 右孩子的引用常常代表右孩子为根的整棵右子树}// 三叉链表classNode{intval;// 数据域Nodeleft;// 左孩子的引用常常代表左孩子为根的整棵左子树Noderight;// 右孩子的引用常常代表右孩子为根的整棵右子树Nodeparent;// 当前节点的根节点}// 线索二叉树classNode{intval;ThreadedNodeleft;ThreadedNoderight;// 标志位0代表孩子1代表线索指向前驱/后继intlTag;intrTag;}线索二叉树在普通的二叉链表中一个拥有 n 个结点的二叉树会有 n1 个空指针域。线索二叉树的核心思想就是利用这些空指针来存放结点在某种遍历序列中的“前驱”和“后继”信息从而加快遍历速度.实质就是线索二叉树 用空指针存遍历顺序线索树中的 right 可以类似理解为链表中的 next可以向上走也可以像普通二叉树一样往下找右子树走ltag0→ 左孩子 ltag1→ 前驱线索 rtag0→ 右孩子 rtag1→ 后继线索如中序遍历不用递归线索树publicvoidinorderTraverse(ThreadNoderoot){ThreadNodecurroot;// 找到最左节点while(cur.ltag0){curcur.left;}while(cur!null){System.out.print(cur.val );// 如果是线索 → 直接走后继if(cur.rtag1){curcur.right;}else{// 否则去右子树找最左curcur.right;while(cur!nullcur.ltag0){curcur.left;}}}}而将二叉树转为线索树需要用线索化方法将其转换如下publicclassThreadedBinaryTreeDemo{// 节点定义staticclassThreadNode{charval;ThreadNodeleft;ThreadNoderight;intltag;// 0 左孩子1 前驱intrtag;// 0 右孩子1 后继publicThreadNode(charval){this.valval;}}// 全局前驱指针staticThreadNodeprenull;// 递归过程中需要共享“上一个访问的节点”// 中序线索化publicstaticvoidinorderThread(ThreadNodenode){if(nodenull)return;// 1. 处理左子树保证顺序左→根→右inorderThread(node.left);// 2. 处理当前节点// (1) 建立前驱线索if(node.leftnull){node.leftpre;node.ltag1;}// (2) 建立后继线索if(pre!nullpre.rightnull){pre.rightnode;pre.rtag1;}// (3) 更新 pre当前节点成为下一个节点的前驱prenode;// 3. 处理右子树inorderThread(node.right);}2.3.2 二叉树的顺序存储顺序存储适合情况完全二叉树满二叉树顺序存储的核心是使用数组来模拟二叉树的结构就如前面性质所提到的左孩子2*i 1右孩子2*i 2顺序存储数组下标 二叉树的层序遍历顺序注当且仅当是完全二叉树时当不是完全二叉树时其存储情况如此图2.4 二叉树的基本操作2.4.1 二叉树的三种遍历1.前序遍历// 前序遍历publicvoidpreorderTree(TreeNoderoot){if(rootnull)return;System.out.print(root.val );preorderTree(root.left);preorderTree(root.right);}非递归方法如下思路通过栈来存储当前节点的上一位解题过程将 root 赋给 cur进入循环循环中 cur 拿到节点就进行压栈并打印随后向左移动向左时一路压栈一路打印直至 cur null 时再弹出前一个节点将其右索引赋值给 cur 并将其进行循环将 cur 视为另一子树的根节点即可理解// 前序遍历非递归publicvoidpreorderNor(TreeNoderoot){if(rootnull)return;StackTreeNodestacknewStack();TreeNodecurroot;// 循环判断cur的右侧是否有元素while(cur!null||!stack.isEmpty()){// 循环往下遍历左侧元素while(cur!null){stack.push(cur);System.out.print(cur.val );curcur.left;}// cur为空需要提出栈中一个元素TreeNodetopstack.pop();curtop.right;}}注意中序遍历非递归与此一样只是打印位置不同复杂度时间复杂度O(N)空间复杂度O(N)最坏/O(log N)平均/O(1)右单支树2.中序遍历// 中序遍历publicvoidinorderTree(TreeNoderoot){if(rootnull)return;inorderTree(root.left);System.out.print(root.val );inorderTree(root.right);}中序遍历非递归方法与前序遍历非递归类似仅仅调换打印位置// 中序遍历非递归publicvoidinorderNor(TreeNoderoot){if(rootnull)return;StackTreeNodestacknewStack();TreeNodecurroot;// 循环判断cur的右侧是否有元素while(cur!null||!stack.isEmpty()){// 循环往下遍历左侧元素while(cur!null){stack.push(cur);curcur.left;}// cur为空需要提出栈中一个元素TreeNodetopstack.pop();System.out.print(top.val );curtop.right;}}3.后序遍历// 后序遍历publicvoidpostorderTree(TreeNoderoot){if(rootnull)return;postorderTree(root.left);postorderTree(root.right);System.out.print(root.val );}下面为非递归方法注意如上图当 cur 走到 7 时假设还存在右值“10”直至走完 “10”随后弹出 7又会再次走到判断 7 是否存在右值因此进入死循环。为此我们在循环外定义一个节点prev以此来标记我们打印过的节点以避免死循环。加上if(top.right ! null top.right ! prev)这条判断语句即可思路通过栈来存储当前节点的上一位解题过程思路延续前面的前序以及中序遍历的思想仅在处理打印顺序时候需调整// 后序遍历非递归publicvoidpostorderNor(TreeNoderoot){if(rootnull)return;StackTreeNodestacknewStack();TreeNodecurroot;TreeNodeprevnull;while(cur!null||!stack.isEmpty()){while(cur!null){stack.push(cur);curcur.left;}TreeNodetopstack.peek();// 注意此处prev用来标记前一个元素是否有被打印if(top.right!nulltop.right!prev){curtop.right;}else{System.out.print(top.val );stack.pop();prevtop;}}}复杂度时间复杂度O(N)空间复杂度 O(N)最坏 /O(log N)最好2.4.2 二叉树的其他操作1. 获取树中节点个数// 左子树叶子个数 右子树叶子个数子问题法publicintgetLeafNodeCount(TreeNoderoot){if(rootnull)return0;if(root.leftnullroot.rightnull)return1;returngetLeafNodeCount(root.left)getLeafNodeCount(root.right);}2. 获取叶子节点个数// 获取叶子个数遍历法publicstaticintcount0;publicvoidgetLeafNodeCount(TreeNoderoot){if(rootnull)return;if(root.leftnullroot.rightnull){count;}getLeafNodeCount(root.left);getLeafNodeCount(root.right);}3. 获取二叉树的高度publicintgetHeight(TreeNoderoot){if(rootnull)return0;returnMath.max(getHeight(root.right),getHeight(root.left))1;}4. 层序遍历publicvoidlevelOrder(TreeNoderoot){if(rootnull)return;QueueTreeNodequeuenewLinkedList();queue.offer(root);while(!queue.isEmpty()){TreeNodecurqueue.poll();System.out.print(cur.val );if(cur.left!null)queue.offer(cur.left);if(cur.right!null)queue.offer(cur.right);}}二叉树 Oj 练习此题是转换为循环链表LCR 155. 将二叉搜索树转化为排序的双向链表 - 力扣LeetCode144. 二叉树的前序遍历 - 力扣LeetCode二叉搜索树与双向链表_牛客题霸_牛客网102. 二叉树的层序遍历 - 力扣LeetCode236. 二叉树的最近公共祖先 - 力扣LeetCode上面题解可参考另一篇文章~以上是我关于Java的笔记分享也可以关注关注我的Sirens-Blog感谢你读到这里这也是我学习路上的一个小小记录。希望以后回头看时能看到自己的成长~