asp网站建设代码,汕头建设工程总公司,西安网站排名优化,装饰工程经营范围有哪些理论基础
二叉树的定义形式有#xff1a;节点指针和数组
在数组中#xff0c;父节点的下标为i#xff0c;那么其左孩子的下标即i*21#xff0c;右孩子的下标即为i*22
二叉树的常见遍历形式有#xff1a;前序遍历、后序遍历、中序遍历和层序遍历
前序遍历#xff1a;二…理论基础
二叉树的定义形式有节点指针和数组
在数组中父节点的下标为i那么其左孩子的下标即i*21右孩子的下标即为i*22
二叉树的常见遍历形式有前序遍历、后序遍历、中序遍历和层序遍历
前序遍历二叉树的节点遍历顺序为根节点、左节点、右节点常记为“根左右”同理后序遍历则为“左右根”中序遍历则为“左根右”其主要的区别在于“根节点”的遍历顺序但是注意访问顺序和遍历顺序不是相同的概念例如中序遍历应该理解为已访问过中节点只是未处理它需要优先处理它的左节点层序遍历顾名思义就是按照从根节点到叶节点、从左到右的顺序一层一层地遍历节点
根据二叉树的定义不同又可分为不同类型的二叉树常见的有
满二叉树只有度为0的结点和度为2的节点并且度为0的结点都在同一层上。完全二叉树整颗树包括其每一棵子树除了叶节点其他每一个节点都有左右节点节点不为空同时要保证父子节点的顺序关系。二叉搜索树整颗树包括其每一棵子树都满足左节点 父节点右节点 父节点的条件其中序遍历的结果为递增序列。二叉平衡树整颗树包括其每一棵子树每一个节点都满足|其左右节点的树的高度的差值| 1
更多有关二叉树的理论基础可查阅《代码随想录》二叉树理论基础
对于二叉树的遍历在《代码随想录》中都有非常详细的解释我也是阅读学习之后再来解题的所以在下面的解题过程中就不加以赘述了仅贴出实现不同遍历形式的程序代码。 递归遍历二叉树
Java解法递归前序遍历
class Solution {public ListInteger preorderTraversal(TreeNode root) {ListInteger ans new ArrayList();this.preorder(root, ans);return ans;}public void preorder(TreeNode root, ListInteger list){if(null root){return;}list.add(root.val);this.preorder(root.left, list);this.preorder(root.right, list);}
}Java解法递归中序遍历
class Solution {public ListInteger inorderTraversal(TreeNode root) {ListInteger ans new ArrayList();this.inorder(root, ans);return ans;}public void inorder(TreeNode root, ListInteger list){if(null root){return;}this.inorder(root.left, list);list.add(root.val);this.inorder(root.right, list);}
}Java解法递归后序遍历
class Solution {public ListInteger postorderTraversal(TreeNode root) {ListInteger ans new ArrayList();this.postorder(root, ans);return ans;}public void postorder(TreeNode root, ListInteger list){if(null root){return;}this.postorder(root.left, list);this.postorder(root.right, list);list.add(root.val);}
}迭代遍历二叉树
Java解法迭代前序遍历
class Solution {public ListInteger preorderTraversal(TreeNode root) {ListInteger ans new ArrayList();this.preorder(root, ans);return ans;}public void preorder(TreeNode root, ListInteger list){StackTreeNode stack new Stack();if(null ! root) stack.push(root);while(!stack.isEmpty()){root stack.pop();list.add(root.val);if(null ! root.right) stack.push(root.right);if(null ! root.left) stack.push(root.left);}}
}Java解法迭代中序遍历
class Solution {public ListInteger inorderTraversal(TreeNode root) {ListInteger ans new ArrayList();this.inorder(root, ans);return ans;}public void inorder(TreeNode root, ListInteger list){StackTreeNode stack new Stack();while(null ! root || !stack.isEmpty()){if(null ! root){stack.push(root);root root.left;}else{root stack.pop();list.add(root.val);root root.right;}}}
}Java解法迭代后序遍历
class Solution {public ListInteger postorderTraversal(TreeNode root) {ListInteger ans new ArrayList();this.postorder(root, ans);return ans;}public void postorder(TreeNode root, ListInteger list){StackTreeNode stack new Stack();if(null ! root) stack.push(root);while(!stack.isEmpty()){root stack.pop();list.add(root.val);if(null ! root.left) stack.push(root.left);if(null ! root.right) stack.push(root.right);}Collections.reverse(list);}
}我们发现迭代法实现的先中后序其实风格也不是那么统一除了先序和后序有关联中序完全就是另一个风格了一会用栈遍历一会又用指针来遍历。那么如何针对三种不同的遍历方式使用迭代法是可以写出统一风格的代码 统一迭代遍历二叉树【重点】
可以利用标记法来做到统一迭代
将访问的节点放入栈中把要处理的节点也放入栈中但是要做标记。在这里我们利用空指针来做标记在要处理的节点放入栈之后紧接着放入一个空指针作为标记。详细的解释和实现可以查阅《代码随想录》二叉树的统一迭代法
Java解法统一迭代前序遍历
class Solution {public ListInteger preorderTraversal(TreeNode root) {ListInteger ans new ArrayList();this.preorder(root, ans);return ans;}public void preorder(TreeNode root, ListInteger list){StackTreeNode stack new Stack();if(null ! root) stack.push(root);while(!stack.isEmpty()){root stack.peek();if(null ! root){stack.pop(); // 需要先弹出节点避免后续重复访问// 节点按照右左根的顺序进栈后续出栈顺序为根左右前序遍历if(null ! root.right) stack.push(root.right);if(null ! root.left) stack.push(root.left);stack.push(root);stack.push(null); // 对需要处理的节点在其后面跟上空指针作为标记}else{stack.pop(); // 遇到标记时先弹出标记// 再弹出下一个节点进行处理root stack.pop();list.add(root.val);}}}
}Java解法统一迭代中序遍历
class Solution {public ListInteger inorderTraversal(TreeNode root) {ListInteger ans new ArrayList();this.inorder(root, ans);return ans;}public void inorder(TreeNode root, ListInteger list){StackTreeNode stack new Stack();if(null ! root) stack.push(root);while(!stack.isEmpty()){root stack.peek();if(null ! root){stack.pop(); // 需要先弹出节点避免后续重复访问// 节点按照右根左的顺序进栈后续出栈顺序为左根右中序遍历if(null ! root.right) stack.push(root.right);stack.push(root);stack.push(null); // 对需要处理的节点在其后面跟上空指针作为标记if(null ! root.left) stack.push(root.left);}else{stack.pop(); // 遇到标记时先弹出标记// 再弹出下一个节点进行处理root stack.pop();list.add(root.val);}}}
}Java解法统一迭代后序遍历
class Solution {public ListInteger postorderTraversal(TreeNode root) {ListInteger ans new ArrayList();this.postorder(root, ans);return ans;}public void postorder(TreeNode root, ListInteger list){StackTreeNode stack new Stack();if(null ! root) stack.push(root);while(!stack.isEmpty()){root stack.peek();if(null ! root){stack.pop();// 需要先弹出节点避免后续重复访问// 节点按照根右左的顺序进栈后续出栈顺序为左右根后序遍历stack.push(root);stack.push(null);// 对需要处理的节点在其后面跟上空指针作为标记if(null ! root.right) stack.push(root.right);if(null ! root.left) stack.push(root.left);}else{stack.pop();// 遇到标记时先弹出标记// 再弹出下一个节点进行处理root stack.pop();list.add(root.val);}}}
}二叉树结构也是在编程中常见的数据结构之一例如堆其实就是一个树结构以及哈希表中也运用到了红黑树来优化哈希表的存储结构等等。
通过今天的练习我第一次了解并学习到了二叉树的统一迭代遍历算法利用标记法来遍历二叉树的方法真的是非常巧妙同时通过迭代算法的练习也加深了对递归是如何模拟一个栈以及递归算法如何转变为迭代算法有了一个初步的思路
门径初窥书海奥, 欣喜若狂凯歌还。
