js实现后序遍历二叉树
时间: 2023-03-28 09:01:00 浏览: 85
可以使用递归或迭代的方式实现后序遍历二叉树。递归方式是先遍历左子树,再遍历右子树,最后访问根节点。迭代方式可以使用栈来实现,先将根节点入栈,然后循环取出栈顶节点,如果该节点有左右子节点,则先将左右子节点入栈,直到栈为空为止,最后访问节点。
相关问题
js完全二叉树非叶子部分后序遍历
对于一个完全二叉树,我们可以用数组来表示。假设数组的索引从0开始,对于一个节点i,它的左子节点的索引为2i+1,右子节点的索引为2i+2。
非叶子部分即为除去最后一层的所有节点。若树的深度为d,则最后一层的节点数量为2^(d-1)。所以非叶子部分的节点数量为2^(d-1)-1。
后序遍历的顺序为先遍历左子树,再遍历右子树,最后访问根节点。对于非叶子部分的后序遍历,我们只需要从根节点开始遍历到最后一个非叶子节点即可。
具体步骤为:
1. 根据非叶子节点数量,计算树的深度d。
2. 从根节点开始,遍历到索引为2^(d-1)-1的节点。
3. 对于每个节点,先递归遍历它的左子节点,再递归遍历它的右子节点。
4. 最后访问根节点。
以下是一个JavaScript的示例代码实现:
```
function postOrderTraversal(arr, nodeIndex) {
const length = arr.length;
if (nodeIndex >= length) {
return;
}
// 左子节点的索引
const leftChild = 2 * nodeIndex + 1;
// 右子节点的索引
const rightChild = 2 * nodeIndex + 2;
// 先遍历左子节点
postOrderTraversal(arr, leftChild);
// 再遍历右子节点
postOrderTraversal(arr, rightChild);
// 访问根节点
console.log(arr[nodeIndex]);
}
const completeBinaryTree = [1, 2, 3, 4, 5, 6, 7, 8, 9];
const lastNonLeafIndex = Math.floor((completeBinaryTree.length - 1) / 2) - 1;
postOrderTraversal(completeBinaryTree, 0);
```
以上代码中,我们定义了一个`postOrderTraversal`函数,传入的参数为数组表示的完全二叉树,以及当前节点的索引。函数先判断节点索引是否超出了数组的长度,如果是,则无需再进行遍历。接下来,我们计算左子节点和右子节点的索引,并先递归遍历它们,最后再输出当前节点的值。最后,我们传入根节点的索引0,即可得到非叶子部分的后序遍历结果。
使用JavaScript完成。给你一棵二叉树的根节点 root ,返回其节点值的 后序遍历 。示例:输入:root = [1,null,2,3] 输出:[3,2,1]
好的,以下是使用JavaScript完成二叉树后序遍历的代码:
```javascript
function postorderTraversal(root) {
let result = [];
if (root === null) {
return result;
}
let stack = [root];
while (stack.length) {
let node = stack.pop();
result.unshift(node.val);
if (node.left !== null) {
stack.push(node.left);
}
if (node.right !== null) {
stack.push(node.right);
}
}
return result;
}
```
这里使用了一个栈来存储待处理的节点。首先将根节点入栈,然后在每一次循环中弹出栈顶节点,并将其值插入结果数组的开头。接着,将左右子节点(如果存在)分别推入栈中。由于后序遍历是先访问左右子节点,最后才访问根节点,因此需要先将根节点的值插入结果数组的开头。最后返回结果数组即可。
希望这个代码对您有帮助!
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)