JavaScript二叉树及遍历算法实例分析
导读:本文共4835字符,通常情况下阅读需要16分钟。同时您也可以点击右侧朗读,来听本文内容。按键盘←(左) →(右) 方向键可以翻页。
摘要: 什么是二叉树二叉树是每个节点最多只能有两个子节点的树,如下图所示:一个二叉树具有以下几个特质:第i层的节点最有只有2^(i-1)个;如果这颗二叉树的深度为k,那二叉树最多有2^k-1个节点;在一个非空的二叉树中,若使用n0表示叶子节点的个数,n2是度为2的非叶子节点的个数,那么两者满足关系n0 = n2 + 1。满二叉树如果在一个二叉树中,除了叶子节点,其余的节... ...
目录
(为您整理了一些要点),点击可以直达。什么是二叉树
二叉树是每个节点最多只能有两个子节点的树,如下图所示:
一个二叉树具有以下几个特质:
第
i
层的节点最有只有2^(i-1)
个;如果这颗二叉树的深度为
k
,那二叉树最多有2^k-1
个节点;在一个非空的二叉树中,若使用
n0
表示叶子节点的个数,n2
是度为2的非叶子节点的个数,那么两者满足关系n0 = n2 + 1
。
满二叉树
如果在一个二叉树中,除了叶子节点,其余的节点的每个度都是2,则说明该二叉树是一个满二叉树,
如下图所示:
满二叉树除了满足普通二叉树特质,还具有如下几个特质:
满二叉树的的第
n
层具有2^(n-1)
个节点;深度为
k
的满二叉树一定存在2^k-1
个节点,叶子节点的个数为2^(k-1)
;具有
n
个节点的满二叉树的深度为log_2^(n+1)
。
完全二叉树
如果一个二叉树去掉最后一次层是满二叉树,且最后一次的节点是依次从左到右分布的,则这个二叉树是一个完全二叉树,
如下图所示:
二叉树的存储
存储二叉树的常见方式分为两种,一种是使用数组存储,另一种使用链表存储。
数组存储
使用数组存储二叉树,如果遇到完全二叉树,存储顺序从上到下,从左到右,如下图所示:
如果是一个非完全二叉树,如下图所示:
需要先将其转换为完全二叉树,然后在进行存储,如下图所示:
可以很明显的看到存储空间的浪费。
链表存储
使用链表存储通常将二叉树中的分为3个部分,如下图:
这三个部分依次是左子树的引用,该节点包含的数据,右子树的引用,存储方式如下图所示:
与二叉树相关的算法
以下算法中遍历用到的树如下:
//tree.jsconstbt={val:'A',left:{val:'B',left:{val:'D',left:null,right:null},right:{val:'E',left:null,right:null},},right:{val:'C',left:{val:'F',left:{val:'H',left:null,right:null},right:{val:'I',left:null,right:null},},right:{val:'G',left:null,right:null},},}module.exports=bt
深度优先遍历
二叉树的深度优先遍历与树的深度优先遍历思路一致,思路如下:
访问根节点;
访问根节点的
left
访问根节点的
right
重复执行第二三步
实现代码如下:
constbt={val:'A',left:{val:'B',left:{val:'D',left:null,right:null},right:{val:'E',left:null,right:null},},right:{val:'C',left:{val:'F',left:{val:'H',left:null,right:null},right:{val:'I',left:null,right:null},},right:{val:'G',left:null,right:null},},}functiondfs(root){if(!root)returnconsole.log(root.val)root.left&&dfs(root.left)root.right&&dfs(root.right)}dfs(bt)/**结果ABDECFHIG*/
广度优先遍历
实现思路如下:
创建队列,把根节点入队
把对头出队并访问
把队头的
left
和right
依次入队重复执行2、3步,直到队列为空
实现代码如下:
functionbfs(root){if(!root)returnconstqueue=[root]while(queue.length){constnode=queue.shift()console.log(node.val)node.left&&queue.push(node.left)node.right&&queue.push(node.right)}}bfs(bt)/**结果ABCDEFGHI*/
先序遍历
二叉树的先序遍历实现思想如下:
访问根节点;
对当前节点的左子树进行先序遍历;
对当前节点的右子树进行先序遍历;
如下图所示:
递归方式实现如下:
constbt=require('./tree')functionpreorder(root){if(!root)returnconsole.log(root.val)preorder(root.left)preorder(root.right)}preorder(bt)/**结果ABDECFHIG*/
迭代方式实现如下:
//非递归版functionpreorder(root){if(!root)return//定义一个栈,用于存储数据conststack=[root]while(stack.length){constnode=stack.pop()console.log(node.val)/*由于栈存在先入后出的特性,所以需要先入右子树才能保证先出左子树*/node.right&&stack.push(node.right)node.left&&stack.push(node.left)}}preorder(bt)/**结果ABDECFHIG*/
中序遍历
二叉树的中序遍历实现思想如下:
对当前节点的左子树进行中序遍历;
访问根节点;
对当前节点的右子树进行中序遍历;
如下图所示:
递归方式实现如下:
constbt=require('./tree')//递归版functioninorder(root){if(!root)returninorder(root.left)console.log(root.val)inorder(root.right)}inorder(bt)/**结果DBEAHFICG*/
迭代方式实现如下:
//非递归版functioninorder(root){if(!root)returnconststack=[]//定义一个指针letp=root//如果栈中有数据或者p不是null,则继续遍历while(stack.length||p){//如果p存在则一致将p入栈并移动指针while(p){//将p入栈,并以移动指针stack.push(p)p=p.left}constnode=stack.pop()console.log(node.val)p=node.right}}inorder(bt)/**结果DBEAHFICG*/
后序遍历
二叉树的后序遍历实现思想如下:
对当前节点的左子树进行后序遍历;
对当前节点的右子树进行后序遍历;
访问根节点;
如下图所示:
递归方式实现如下:
constbt=require('./tree')//递归版functionpostorder(root){if(!root)returnpostorder(root.left)postorder(root.right)console.log(root.val)}postorder(bt)/**结果DEBHIFGCA*/
迭代方式实现如下:
//非递归版functionpostorder(root){if(!root)returnconstoutputStack=[]conststack=[root]while(stack.length){constnode=stack.pop()outputStack.push(node)//这里先入left需要保证left后出,在stack中后出,就是在outputStack栈中先出node.left&&stack.push(node.left)node.right&&stack.push(node.right)}while(outputStack.length){constnode=outputStack.pop()console.log(node.val)}}postorder(bt)/**结果DEBHIFGCA*/
</div> <div class="zixun-tj-product adv-bottom"></div> </div> </div> <div class="prve-next-news">
JavaScript二叉树及遍历算法实例分析的详细内容,希望对您有所帮助,信息来源于网络。