二叉树，二叉树遍历，二叉树搜索
树形结构
树形结构应该就比较容易理解了，树是二维数据结构中的一种，至于说二叉树又是树的一种了。
树和图的区别在这里说明一下，重点：
树形结构为二维数据结构中的一种特殊结构
1.树形结构有一个根节点2.树形结构没有回路（就是只能一直往下，有回路的称为图，树是图的一种）3.树形结构我们称为 有向循环图几个关键字，拓补结构，树，图，有向循环图
二叉树
就三种，一种根节点，一种节点，一种叶子节点二叉树，就是只有两个枝的结构
二叉树代码实现：
//二叉树结构function Rout(value) {this.value = value;this.left = null;this.right = null;}// 赋值var a = new Rout("a");var b = new Rout("b");var c = new Rout("c");var d = new Rout("d");var e = new Rout("e");var f = new Rout("f");var g = new Rout("g");// 结构图a.left = b;a.right = c;b.left = d;b.right = e;c.left = f;c.right = g;
跟节点应该好理解
叶子节点：下边没有其他节点节点：既不是根节点，也不是叶子节点的普通节点
满二叉树：
1.所有的叶子节点都在最底层
2.每个非叶子节点都有两个子节点
完全二叉树：
若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。
国内定义
1.叶子节点都在最后一层或者倒数第二层2.叶子节点都向左聚拢
国际定义
1.叶子节点都在最后一层或者倒数第二层2.如果有叶子节点，就必然有两个叶子节点
画了一个二叉树，这是一个满的二叉树，接下来我们说遍历，遍历分为三种：
1.前序遍历
2.中序遍历
3.后序遍历
前序遍历：深度优先原则
先打印当前的，再打印左边的，再打印右边的
中序：先打印左边的，再打印当前的，再打印右边的
后序遍历：先打印左边的，再打印右边的，再打印当前的
总的来说：
专业的名词了解下：
前序遍历：先根次序遍历
中序遍历：中根次序遍历
后序遍历：后根次序遍历
前序遍历代码实现：
//输出 前序遍历function f1(root){//判断if(root == null) return;console.log(root.value);f1(root.left);f1(root.right);}//调用f1(a);
中序遍历代码实现：
//输出 中序遍历function f1(root) {//判断if (root == null) return;f1(root.left);console.log(root.value);f1(root.right);}//调用f1(a);
后序遍历代码实现：
//输出 后序遍历function f1(root) {//判断if (root == null) return;f1(root.left);f1(root.right);console.log(root.value);}//调用f1(a);
二叉树的搜索，搜索肯定就分为两种搜了，应该很容易理解
深度优先
广度优先
深度搜索代码示例：
// 深度搜索代码function dfsSearch(root,target){//判断 代码的严谨性 返回 true 或者 falseif(root == null) return false;if(root.value == target) return true;//赋值var left = deepSearch(root.left,target);var right = deepSearch(root.right,target);//返回return left || right;}//调用 打印输出 搜索h节点是否存在console.log(dfsSearch(a,"h"));
广度搜索代码：
// 广度搜索代码function bfsSearch(rootlist,target){//判断 代码的严谨性if(rootlist == null || rootlist.length == 0) return false;//创建存储空间var childlist = [];//循环存储信息for(var i = 0;i < rootlist.length;i++){//判断为false时是否继续if(!rootlist[i]) continue;//判断if(rootlist[i] != null && rootlist[i].value == target){return true;}else{//添加左子树childlist.push(rootlist[i].left);//添加右子树childlist.push(rootlist[i].right);}}//返回return bfsSearch(childlist,target);}//调用 打印输出 搜索h节点是否存在console.log(bfsSearch([a],"h"));
深搜代码，查找h是否存在，返回true或者false
代码里面都是用到了大量的递归，都是跟链表的逆置是一个思想的
小拓展：
二叉树的比较：判断两个二叉树是否相等
（1）首先，创建两个二叉树
//二叉树结构function Rout(value) {this.value = value;this.left = null;this.right = null;}//第一个二叉树// 赋值var a = new Rout("a");var b = new Rout("b");var c = new Rout("c");var d = new Rout("d");var e = new Rout("e");var f = new Rout("f");var g = new Rout("g");// 结构图a.left = b;a.right = c;b.left = d;b.right = e;c.left = f;c.right = g;//第二个二叉树// 赋值var a1 = new Rout("a");var b1 = new Rout("b");var c1 = new Rout("c");var d1 = new Rout("d");var e1 = new Rout("e");var f1 = new Rout("f");var g1 = new Rout("g");// 结构图a1.left = b1;a1.right = c1;b1.left = d1;b1.right = e1;c1.left = g1;c1.right = f1;
(2)比较两个二叉树是否相等
//比较是否相等function twiceOver(rootlist1, rootlist2) {//判断 代码的严谨性if (rootlist1 == rootlist2) return true; //为同一颗树if (rootlist1 == null && rootlist2 != null || rootlist1 != null && rootlist2 == null) return false; //其中一个二叉树结构不同时if (rootlist1.value != rootlist2.value) return false; //相同位置的值不相等时//赋值判断var twiceleft = twiceOver(rootlist1.left, rootlist2.left); //判断左子树是否相等var twiceright = twiceOver(rootlist1.right, rootlist2.right); //判断右子树是否相等//返回return twiceleft && twiceright; //只要左右子树都相等二叉树才相等}//调用console.log(twiceOver(a, a1));
面试中注意事项：
填空题和笔试题都有可能出现的
1.给出前序中序还原二叉树，要求写出后序遍历
2.给出后序中序还原二叉树，要求写出前序遍历
注意：必须要有中序遍历，没有中序遍历，不能实现还原二叉树
还原二叉树代码示例：
1.根据前序、中序遍历，还原二叉树，进行后序遍历
//根据前序、中序遍历，还原二叉树，进行后序遍历var qian = ["a","b","d","e","c","f","g"];var zhong = ["d","b","e","a","f","c","g"];//构造函数function f2(qian,zhong){//判断 代码的严谨性if(qian == null || zhong == null || qian.length == 0 || zhong.length == 0 || qian.length != zhong.length) return null;//获取根节点var root = new Rout(qian[0]);//找到根节点中序遍历 中 的位置var index = zhong.indexOf(root.value);//分离前序遍历//前序遍历的左子树var qianleft = qian.slice(1,index + 1);//前序遍历的右子树var qianright = qian.slice(1 + index,qian.length);//分离中序遍历//中序遍历的左子树var zhongleft = zhong.slice(0,index);//中序遍历的右子树var zhongright = zhong.slice(1 + index,zhong.length);// 还原二叉树// 根据左子树还原二叉树的左子树root.left = f2(qianleft,zhongleft);// 根据右子树还原二叉树的右子树root.right = f2(qianright,zhongright);//返回return root;}// 输出 后序遍历var root = f2(qian,zhong);console.log(root.left);console.log(root.right);后序遍历console.log(root.left.left.value);console.log(root.left.right.value);console.log(root.left.value);console.log(root.right.left.value);console.log(root.right.right.value);console.log(root.right.value);console.log(root.value);
2.根据后序、中序遍历，还原二叉树，进行前序遍历
//根据后序、中序遍历，还原二叉树，进行前序遍历var hou = ["d", "e", "b", "f", "g", "c", "a"];var zhong = ["d", "b", "e", "a", "f", "c", "g"];//构造函数function f2(hou, zhong) {//判断 代码的严谨性if (hou == null || zhong == null || hou.length == 0 || zhong.length == 0 || hou.length != zhong.length) return null;//获取根节点var root = new Rout(hou[hou.length - 1]);//根据根节点获取中序遍历 中 的位置var index = zhong.indexOf(root.value);//分离后序遍历//后序遍历的左子树var houleft = hou.slice(0, index);//后序遍历的右子树var houright = hou.slice(index, hou.length - 1);//分离中序遍历//中序遍历的左子树var zhongleft = zhong.slice(0, index);//中序遍历的右子树var zhongright = zhong.slice(index + 1, zhong.length);//还原二叉树//根据左子树还原二叉树的左子树root.left = f2(houleft, zhongleft);// 根据右子树还原二叉树的右子树root.right = f2(houright, zhongright);//返回return root;}// 输出var root = f2(hou, zhong);console.log(root.left);console.log(root.right);// 前序遍历console.log(root.value);console.log(root.left.value);console.log(root.left.left.value);console.log(root.left.right.value);console.log(root.right.value);console.log(root.right.left.value);console.log(root.right.right.value);
拼搏现实的明天。
向右看齐
港控/mmm°
柔情只为你懂
灰太狼
还没有评论，来说两句吧...