1. 什么是二叉树 #1
Comments
为什么学习二叉树二叉树的知识更倾向于理论，我们在实际应用开发过程中直接使用得并不多，但是二叉树作为数据结构的一个重要的组成部分，底层很多东西都是基于二叉树实现的，比如TreeMap，TreeSet，Linux的虚拟内存管理，数据库系统等，所以掌握二叉树的基本操作是相当必要的。 二叉树的概念和特点我们学习的数据结构中的树，不是现实生活中的树。它和现实生活中的树有着很多的相似之处，或者可以说数据结构的树是对现实生活中的树的抽象。
数据结构中的树：
树的定义： 树是由n(n>=1)个有限节点组成的一个具有层次关系的集合。 树的特点：
二叉树的定义和创建二叉树是一种特殊的树，在树的基础上添加约束条件：
二叉树就是一个集合，集合就是用来存储对象的容器，二叉树上存储的每一个元素，都是一个一个的对象。节点对象。 二叉树的实现分析一个二叉树节点有三个部分，一个是指向左子树的部分，一个是指向右子树的部分，另外一个是数据部分。可以把整个节点抽象成一个节点对象。节点对象有两个节点对象属性和一个数据数据。 一个二叉树有且只有一个根节点，其余的都是根节点的直接或间接子节点。所以可以把二叉树抽象成一个对象。该对象有一个节点类型的数据，用来保存根节点。
二叉排序树的本质就是一颗二叉树，它具有如下特点：
树的分类
144. 二叉树的前序遍历给你二叉树的根节点root，返回它节点值的前序遍历。
root = [1, null, 2, 3]
[1,2,3]
root = []
[]
root = [1]
[1]var preorderTraversal = function(root) {
if (!root) return [];
var result = [];
var stack = [root];
while(stack.length) {
var node = stack.pop();
result.push(node.val);
if (node.right) stack.push(node.right);
if (node.left) stack.push(node.left);
}
return result;
};94. 二叉树的中序遍历
var inorderTraversal = function(root) {
const stack = [];
const res = [];
while(root || stack.length) {
if(root) {
stack.push(root);
root = root.left;
} else {
root = stack.pop();
res.push(root.val);
root = root.right;
}
}
return res;
};145. 二叉树的后序遍历 var postorderTraversal = function(root) {
if(!root) return [];
const stack = [root];
const result = [];
while(stack.length > 0) {
const node = stack.pop();
result.push(node.val);
if(node.left) stack.push(node.left);
if(node.right) stack.push(node.right);
}
return result.reverse();
};完全二叉树function Node(data, left, right) {
this.data = data;
this.left = left;
this.right = right;
}树的查找function getNode(data, node) {
if(node) {
if(data === node.data) {
return node;
} else if (data < node.data) {
return getNode(data, node.left);
} else {
return getNode(data, node.right);
}
} else {
return null;
}
}二分查找二分查找的条件是必须是有序的线性表。 binarySearch(data, arr, start, end) {
if(start>end) {
return -1;
}
var mid = Math.floor((end + start) / 2);
if(data == arr[mid]) {
return mid;
} else if ( data < arr[mid]) {
return binarySearch(data, arr, start, mid - 1);
} else {
return binarySearch(data, arr, mid + 1, end);
}
}什么是中序遍历中序遍历是二叉树遍历的一种，也叫做中根遍历、中序周游。 在二叉树中，中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。 左 中 右 输入: [1,null,2,3]
1
\
2
/
3
输出: [1,3,2]var inorderTraversal = function(root, array = []) }
if(root) {
inorderTraversal (root.left, array);
array.push(root.val);
inorderTraversal (root.right, array);
}
return array;
}
var inorderTraversal = function (root) {
const result = [];
const stack = [];
let current = root;
while (current || stack.length > 0) {
while (current) {
stack.push(current);
current = current.left;
}
current = stack.pop();
result.push(current.val);
current = current.right;
}
return result;
};什么是前序遍历前序遍历（VLR），是二叉树遍历的一种，也叫做先根遍历、先序遍历、前序周游，可记做根左右。前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。 中 左 右 输入: [1,null,2,3]
1
\
2
/
3
输出: [1,2,3]var preorderTraversal = function (root, array = []) {
if (root) {
array.push(root.val);
preorderTraversal(root.left, array);
preorderTraversal(root.right, array);
}
return array;
};
var preorderTraversal = function (root) {
const result = [];
const stack = [];
let current = root;
while (current || stack.length > 0) {
while (current) {
result.push(current.val);
stack.push(current);
current = current.left;
}
current = stack.pop();
current = current.right;
}
return result;
};什么是后序遍历后序遍历（LRD）是二叉树遍历的一种，也叫做后根遍历、后序周游，可记做左右根。后序遍历有递归算法和非递归算法两种。在二叉树中，先左后右再根，即首先遍历左子树，然后遍历右子树，最后访问根结点。 左 右 中 输入: [1,null,2,3]
1
\
2
/
3
输出: [3,2,1]var postorderTraversal = function (root, array = []) {
if (root) {
postorderTraversal(root.left, array);
postorderTraversal(root.right, array);
array.push(root.val);
}
return array;
};var postorderTraversal = function (root) {
const result = [];
const stack = [];
let last = null; // 标记上一个访问的节点
let current = root;
while (current || stack.length > 0) {
while (current) {
stack.push(current);
current = current.left;
}
current = stack[stack.length - 1];
if (!current.right || current.right == last) {
current = stack.pop();
result.push(current.val);
last = current;
current = null; // 继续弹栈
} else {
current = current.right;
}
}
return result;
}// dfs
var postorderTraversal = function (root) {
let res = [];
function dfs(node) {
if(!node) return
dfs(node.left);
dfs(node.right);
res.push(node.val);
}
dfs(root);
return res;
}重建二叉树function reConstructBinaryTree(pre, vin) {
if(pre.length === 0){
return null;
}
if(pre.length === 1){
return new TreeNode(pre[0]);
}
const value = pre[0];
const index = vin.indexOf(value);
const vinLeft = vin.slice(0,index);
const vinRight = vin.slice(index+1);
const preLeft = pre.slice(1,index+1);
const preRight = pre.slice(index+1);
const node = new TreeNode(value);
node.left = reConstructBinaryTree(preLeft, vinLeft);
node.right = reConstructBinaryTree(preRight, vinRight);
return node;
}求二叉树的遍历let pre;
let vin;
while((pre = readline())!=null){
vin = readline();
print(getHRD(pre,vin));
}
function getHRD(pre, vin) {
if (!pre) {
return '';
}
if (pre.length === 1) {
return pre;
}
const head = pre[0];
const splitIndex = vin.indexOf(head);
const vinLeft = vin.substring(0, splitIndex);
const vinRight = vin.substring(splitIndex + 1);
const preLeft = pre.substring(1, splitIndex + 1);
const preRight = pre.substring(splitIndex + 1);
return getHRD(preLeft, vinLeft) + getHRD(preRight, vinRight) + head;
} |
二叉树的基本操作(注：以下图文说明皆来自 wiki 百科 树的遍历） 从二叉树的根节点出发，节点的遍历分为三个主要步骤：
这三个步骤的先后顺序也是不同遍历方式的根本区别。 遍历方式的命名，源于其存取节点的顺序。
二叉树的前序遍历(Pre-Order Traversal)
前序遍历：F, B, A, D, C, E, G, I, H// 二叉树前序遍历模板
function preOrderTraversal(root) {
if (!root) return // 判断root是否有到达这一层
// Do Something with root 处理当前节点
preOrderTraversal(root.left) // 若其中一侧的子树非空则会读取其子树
preOrderTraversal(root.right) // 另一侧的子树也做相同的事
}144. 二叉树的前序遍历/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
// DFS 直接套用模板即可
var preorderTraversal = function (root) {
return getTree(root)
}
const getTree = (node, arr = []) => {
if (!node) return arr
arr.push(node.val) // 处理当前节点
getTree(node.left, arr)
getTree(node.right, arr)
return arr
}二叉树的中序遍历(In-Order Traversal)
中序遍历：A, B, C, D, E, F, G, H, I// 二叉树中序遍历模板
function preOrderTraversal(root) {
if (!root) return // 判断root是否有到达这一层
preOrderTraversal(root.left) // 若其中一侧的子树非空则会读取其子树
// Do Something with root 处理当前节点
preOrderTraversal(root.right) // 另一侧的子树也做相同的事
}94. 二叉树的中序遍历/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
// DFS 方法一（直接套模板）
var inorderTraversal = function (root) {
return getTree(root)
}
const getTree = (node, arr = []) => {
if (!node) return arr
getTree(node.left, arr)
arr.push(node.val) // 处理当前节点
getTree(node.right, arr)
return arr
}
// DFS 方法二
var inorderTraversal = function (root) {
const ans = []
if (!root) return ans
ans.push(
...inorderTraversal(root.left),
root.val,
...inorderTraversal(root.right)
)
return ans
}
// 对方法一进行简化，可以按照中序遍历的顺序直接全部push进ans二叉树的后序遍历(Post-Order Traversal)
后序遍历：A, C, E, D, B, H, I, G, F// 二叉树后序遍历模板
function preOrderTraversal(root) {
if (!root) return // 判断root是否有到达这一层
preOrderTraversal(root.left) // 若其中一侧的子树非空则会读取其子树
preOrderTraversal(root.right) // 另一侧的子树也做相同的事
// Do Something with root 处理当前节点
}145. 二叉树的后序遍历/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
// DFS 直接套模板
var postorderTraversal = function (root) {
return getTree(root)
}
const getTree = (node, arr = []) => {
if (!node) return arr
getTree(node.left, arr)
getTree(node.right, arr)
arr.push(node.val) // 处理当前节点
return arr
}广度优先遍历
层次遍历：F, B, G, A, D, I, C, E, H// 二叉树层次遍历模板
function level(node) {
if (!node) return null
const queue = [node]
while (queue.length) {
const curr = queue.shift()
// Do Something with curr
if (curr.left) queue.push(curr.left)
if (curr.right) queue.push(curr.right)
}
}144. 二叉树的前序遍历
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
// BFS 解法一
var preorderTraversal = function (root) {
if (!root) return []
const ans = []
const stack = [root]
while (stack.length) {
const { val, left, right } = stack.pop()
ans.push(val) // 处理当前节点
if (right) stack.push(right) // 先右
if (left) stack.push(left) // 后左
}
return ans
}
/* ------------------------------------------------ 分割线----------------------------------------------------- */
// BFS 解法二
var preorderTraversal = function (root) {
if (!root) return []
const ans = []
const stack = [root]
while (stack.length) {
let curr = stack.pop()
while (curr) {
ans.push(curr.val)
if (curr.right) stack.push(curr.right) // push右子节点
curr = curr.left // 将指针指向左子节点
}
}
return ans
}
// 了解到层序遍历的顺序之后，我们就可以通过循环利用指针的特性逐步推送到下一层
// 此方法在in-order和post-order的实现中较常用到94. 二叉树的中序遍历
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var inorderTraversal = function (root) {
const stack = []
const ans = []
while (root || stack.length) {
while (root) {
stack.push(root)
root = root.left
}
root = stack.pop()
ans.push(root.val)
root = root.right
}
return ans
}145. 二叉树的后序遍历
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
// BFS
var postorderTraversal = function (root) {
if (!root) return []
const stack = []
const ans = []
let curr = root
while (stack.length || curr) {
if (curr) {
ans.push(curr.val)
stack.push(curr) // 储存节点
curr = curr.right // 每次先遍历右节点，再遍历左节点
} else {
const node = stack.pop() // 右子树走到底之后，再从获取已经遍历过右子树的中间结果，将它出栈，并遍历它的左子树
curr = node.left
}
}
return ans.reverse()
} |
|
可恶，偷吃。 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
什么是二叉树
树是用来模拟具有树状结构性质的数据集合。根据它的特性可以分为非常多的种类，对于我们来讲，掌握二叉树这种结构就足够了，它也是树最简单、应用最广泛的种类。
二叉树的基本操作（解答）
二叉树的前序遍历（解答）
二叉树的中序遍历（解答）
二叉树的后序遍历（解答）
请写出递归和非递归版本的，前中后序遍历。
题目
重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如输入前序遍历序列
{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。求二叉树的遍历
给定一棵二叉树的前序遍历和中序遍历，求其后序遍历
输入描述:
两个字符串，其长度n均小于等于26。 第一行为前序遍历，第二行为中序遍历。 二叉树中的结点名称以大写字母表示：A，B，C....最多26个结点。
输出描述:
输入样例可能有多组，对于每组测试样例， 输出一行，为后序遍历的字符串。
样例：
The text was updated successfully, but these errors were encountered: