Flask接口签名sign原理与实例代码浅析
346
2023-02-28
Java中二叉树的建立和各种遍历实例代码
这是个常见的面试题,比如说通过二叉树的先序和中序遍历,得到二叉树的层序遍历等问题
先序+中序->建树
假设现在有个二叉树,如下:
此时遍历顺序是:
PreOrder: GDAFEMHZ
InOrder: ADEFGHMZ
PostOrder: AEFDHZMG
现在给出先序(preOrder)和中序(InOrder),建立一颗二叉树
或者给出中序(InOrder)和后序(PostOrder), 建立二叉树,其实是一样的
树节点的定义:
class Tree{
char val;
Tree left;
Tree right;
Tree(char val, Tree left, Tree right){
this.val = val;
this.left = left;
this.right = right;
}
Tree(){
}
Tree(char val){
this.val = val;
this.left = null;
this.right =null;
}
}
建树:
public static Tree buildTree(char[] preOrder, char[] inOrder){
//preOrder是先序序列
//inOrder是中序序列
if(preOrder == null || preOrder.length == 0){
return null;
}
Tree root = new Tree(preOrder[0]);
//找到inOrder中的root的位置
int inOrderIndex = 0;
for (char i = 0; i < inOrder.length; i++){
if(inOrder[i] == root.val){
inOrderIndex = i;
}
}
//preOrder的左子树和右子树部分
char[] preOrderLeft = Arrays.copyOfRange(preOrder, 1, 1+inOrderIndex);
char[] preOrderRight = Arrays.copyOfRange(preOrder, 1+inOrderIndex, preOrder.length);
//inOrder的左子树和右子树部分
char[] inOrderLeft = Arrays.copyOfRange(inOrder, 0, inOrderIndex);
char[] inOrderRight = Arrays.copyOfRange(inOrder, inOrderIndex+1, inOrder.length);
//递归建立左子树和右子树
Tree leftChild = buildTree(preOrderLeft, inOrderLeft);
Tree rightChild = buildTree(preOrderRight, inOrderRight);
root.left = leftChild;
root.right = rightChild;
return root;
}
中序+后序去建树其实是一样的,此处不写了
各种遍历
后序遍历
public static void postOrderPrint(Tree root){
//后续遍历
//左右根
if(root.left != null){
postOrderPrint(root.left);
}
if(root.right != null){
postOrderPrint(root.right);
}
System.out.print(root.val + " ");
}
举一反三,先序和中序是一样的,此处不写了
层序遍历
可以用一个队列Queue,初始先http://把root节点加入到队lkWsuodsjP列,当队列不为空的时候取队列头的节点node,打印node的节点值,如果node的左右孩子不为空将左右孩子加入到队列中即可
public static void layerOrderPrint(Tree root){
if(root == null){
return;
}
//层序遍历
Queue
qe.add(root);
while(!qe.isEmpty()){
Tree node = qe.poll();
System.out.print(node.val + " ");
if(node.left != null){
qe.add(node.left);
}
if(node.right != null){
qe.add(node.right);
}
}
}
深度优先和广度优先
其实就是换个说法而已,深度优先不就是先序遍历嘛,广度优先就是层序遍历
public static void deepFirstPrint(Tree root){
//深度优先遍历等价于先序遍历
//所以可以直接使用先序遍历
if(root == null){
return;
}
System.out.print(root.val + " ");
if(root.left != null){
deepFirstPrint(root.left);
}
if(root.right != null){
deepFirstPrint(root.right);
}
}
public static void deepFirstPrintNoneRec(Tree root){
//深度优先遍历的非递归形式
if(root == null){
return;
}
Stack
st.add(root);
while(!st.isEmpty()){
Tree node = st.pop();
System.out.print(node.val + " ");
//栈是后进先出的
//先加右孩子后加左孩子
if(node.right != null){
st.add(node.right);
}
if(node.left != null){
st.add(node.left);
}
}
}
main函数:
public stathttp://ic void main(String[] args) {
char[] preOrder = "GDAFEMHZ".toCharArray();
char[] inOrder = "ADEFGHMZ".toCharArray();
Tree root = Main.buildTree(preOrder, inOrder);
// Main.postOrderPrint(root); //后序遍历
// Main.layerOrderPrint(root); //层序遍历
// Main.deepFirstPrint(root); //深度优先遍历
// Main.deepFirstPrintNoneRec(root); //深度优先遍历的非递归版本
}
总结
以上就是本文关于java中二叉树的建立和各种遍历实例代码的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站:
《Java编程求二叉树的镜像两种方法介绍》
《Java语言描述二叉树的深度和宽度》
《Java二叉树路径和代码示例》
如有不足之处,欢迎留言指出。感谢朋友们对本站的支持!
版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。
发表评论
暂时没有评论,来抢沙发吧~