域客士单页网站,公司网站怎样添加和修改内容,wordpress 数据库 发布,互联网门户网站有哪些1 问题
重建二叉树#xff1a;给定二叉树的先序遍历#xff08;根左右#xff09;和中序#xff08;左中右#xff09;遍历结果#xff0c;建立这棵二叉树。输入保证二叉树无重复结点
以先序{1, 2, 4, 7, 3, 5, 6, 8}和中序{4, 7, 2, 1, 5, 3, 8, 6}为例 2 分析
先序遍…1 问题
重建二叉树给定二叉树的先序遍历根左右和中序左中右遍历结果建立这棵二叉树。输入保证二叉树无重复结点
以先序{1, 2, 4, 7, 3, 5, 6, 8}和中序{4, 7, 2, 1, 5, 3, 8, 6}为例 2 分析
先序遍历的特点我们知道{1, 2, 4, 7, 3, 5, 6, 8}第一个元素1就是树的根节点然后中序遍历{4, 7, 2, 1, 5, 3, 8, 6}的根节点在中间因为我们从先序遍历里面得知1就是根节点所以在中序遍历{4, 7, 2, 1, 5, 3, 8, 6}中在中序遍历数组1的左边元素都是根节点左子树{4, 7, 2,}这里是3个元素所以在先序数组里面根节点1的后面3个元素也是左子树{2,4,7}也是根节点的左子树在中序遍历1的右边边元素都是{5, 3, 8, 6}都是根节点的右子树然后我们在先序数组里面根节点1的后面第3个元素的后面到尾巴也就是{3,5,6,8}也就是根节点的右子树。然后我们再把问题分解成构建左子树{2,4,7}和构建右子树{3,5,6,8}以此递归处理。 我们构建左子树 再构建右子树 3 代码实现
import java.io.*;class Tree
{public int value;public Tree left;public Tree right;public Tree(int value){this.value value;this.left null;this.right null;}/***前序遍历 */public void printTree(Tree node){if (null node)return;System.out.println(value is node.value);printTree(node.left);printTree(node.right);}/**得到树的根节点*/public Tree getTree(int[] preDatas, int[] inDatas){if (null preDatas || null inDatas){System.out.println(preDatas is null or inDatas is null);return null;}Tree tree buildTree(preDatas, 0, preDatas.length - 1, inDatas, 0, inDatas.length - 1);return tree;}/**构建树的左右子结构*/public Tree buildTree(int[] preDatas, int preStart, int preEnd, int[] inDatas, int inStart, int inEnd){if (null preDatas || null inDatas){System.out.println(preDatas is null or inDatas is null);return null;}System.out.println(preStart is: preStart preEnd is preEnd inStart is inStart inEnd is inEnd);//这里就是进行如果树的左子节点和右子节点是否为空进行设置if (preStart preEnd || inStart inEnd){return null;}Tree tree new Tree(preDatas[preStart]);for (int i inStart; i inEnd; i){ System.out.println(preDatas[preStart] is preDatas[preStart]);if (preDatas[preStart] inDatas[i]){tree.left buildTree(preDatas, preStart 1, preStart i - inStart, inDatas, inStart, i - 1);tree.right buildTree(preDatas, preStart i - inStart 1, preEnd, inDatas, i 1, inEnd);break;}}return tree;}
}class test
{public static void main (String[] args) throws java.lang.Exception{int[] preDatas {1, 2, 4, 7, 3, 5, 6, 8};int[] inDatas {4, 7, 2, 1, 5, 3, 8, 6};Tree test new Tree(0);Tree tree test.getTree(preDatas, inDatas);if (tree null){System.out.println(tree is null);return;}//我们进行前序打印树 test.printTree(tree);}
} 4 运行结果
preStart is:0 preEnd is7 inStart is 0 inEnd is7
preDatas[preStart] is 1
preDatas[preStart] is 1
preDatas[preStart] is 1
preDatas[preStart] is 1
preStart is:1 preEnd is3 inStart is 0 inEnd is2
preDatas[preStart] is 2
preDatas[preStart] is 2
preDatas[preStart] is 2
preStart is:2 preEnd is3 inStart is 0 inEnd is1
preDatas[preStart] is 4
preStart is:3 preEnd is2 inStart is 0 inEnd is-1
preStart is:3 preEnd is3 inStart is 1 inEnd is1
preDatas[preStart] is 7
preStart is:4 preEnd is3 inStart is 1 inEnd is0
preStart is:4 preEnd is3 inStart is 2 inEnd is1
preStart is:4 preEnd is3 inStart is 3 inEnd is2
preStart is:4 preEnd is7 inStart is 4 inEnd is7
preDatas[preStart] is 3
preDatas[preStart] is 3
preStart is:5 preEnd is5 inStart is 4 inEnd is4
preDatas[preStart] is 5
preStart is:6 preEnd is5 inStart is 4 inEnd is3
preStart is:6 preEnd is5 inStart is 5 inEnd is4
preStart is:6 preEnd is7 inStart is 6 inEnd is7
preDatas[preStart] is 6
preDatas[preStart] is 6
preStart is:7 preEnd is7 inStart is 6 inEnd is6
preDatas[preStart] is 8
preStart is:8 preEnd is7 inStart is 6 inEnd is5
preStart is:8 preEnd is7 inStart is 7 inEnd is6
preStart is:8 preEnd is7 inStart is 8 inEnd is7
value is 1
value is 2
value is 4
value is 7
value is 3
value is 5
value is 6
value is 8 5 总结
中途遇到这个一个错误
error: identifier expected
是我在手写函数的时候参数前面忘记了定义类型所以报这个错误。
我们这里用了4个指针分别是先序的起尾指针和中序的起尾指针然后我们不断更新4个指针指针的位置然后当先序的起指针大于尾指针的时候或者中序的起指针大于尾指针的时候我们就构建空指针就这样递归处理就行。
