亚洲乱码中文字幕综合,中国熟女仑乱hd,亚洲精品乱拍国产一区二区三区,一本大道卡一卡二卡三乱码全集资源,又粗又黄又硬又爽的免费视频

Java中二叉樹的建立和各種遍歷實例代碼

 更新時間:2018年01月05日 14:02:30   作者:GavinZhou_xd  
這篇文章主要介紹了Java中二叉樹的建立和各種遍歷實例代碼,涉及樹節(jié)點的定義,后序遍歷,層序遍歷,深度優(yōu)先和廣度優(yōu)先等相關(guān)內(nèi)容,具有一定借鑒價值,需要的朋友可以參考下

這是個常見的面試題,比如說通過二叉樹的先序和中序遍歷,得到二叉樹的層序遍歷等問題

先序+中序->建樹

假設(shè)現(xiàn)在有個二叉樹,如下:

此時遍歷順序是:

PreOrder: GDAFEMHZ 
InOrder: ADEFGHMZ 
PostOrder: AEFDHZMG

現(xiàn)在給出先序(preOrder)和中序(InOrder),建立一顆二叉樹
或者給出中序(InOrder)和后序(PostOrder), 建立二叉樹,其實是一樣的

樹節(jié)點的定義:

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){
    //后續(xù)遍歷
    //左右根
    if(root.left != null){
      postOrderPrint(root.left);
    }
    if(root.right != null){
      postOrderPrint(root.right);
    }
    System.out.print(root.val + " ");
  }

舉一反三,先序和中序是一樣的,此處不寫了

層序遍歷

可以用一個隊列Queue,初始先把root節(jié)點加入到隊列,當(dāng)隊列不為空的時候取隊列頭的節(jié)點node,打印node的節(jié)點值,如果node的左右孩子不為空將左右孩子加入到隊列中即可

public static void layerOrderPrint(Tree root){
    if(root == null){
      return;
    }
    //層序遍歷
    Queue<Tree> qe = new LinkedList<Tree>();
    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);
      }
    }
  }

深度優(yōu)先和廣度優(yōu)先

其實就是換個說法而已,深度優(yōu)先不就是先序遍歷嘛,廣度優(yōu)先就是層序遍歷

public static void deepFirstPrint(Tree root){
    //深度優(yōu)先遍歷等價于先序遍歷
    //所以可以直接使用先序遍歷
    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){
    //深度優(yōu)先遍歷的非遞歸形式
    if(root == null){
      return;
    }
    Stack<Tree> st = new Stack<Tree>();
    st.add(root);
    while(!st.isEmpty()){
      Tree node = st.pop();
      System.out.print(node.val + " ");
      //棧是后進(jìn)先出的
      //先加右孩子后加左孩子
      if(node.right != null){
        st.add(node.right);
      }
      if(node.left != null){
        st.add(node.left);
      }
    }
  }

main函數(shù):

public static 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); //深度優(yōu)先遍歷
//   Main.deepFirstPrintNoneRec(root); //深度優(yōu)先遍歷的非遞歸版本
  }

總結(jié)

以上就是本文關(guān)于Java中二叉樹的建立和各種遍歷實例代碼的全部內(nèi)容,希望對大家有所幫助。感興趣的朋友可以繼續(xù)參閱本站:

Java編程求二叉樹的鏡像兩種方法介紹

Java語言描述二叉樹的深度和寬度

Java二叉樹路徑和代碼示例

如有不足之處,歡迎留言指出。感謝朋友們對本站的支持!

相關(guān)文章

  • SpringBoot集成Shiro進(jìn)行權(quán)限控制和管理的示例

    SpringBoot集成Shiro進(jìn)行權(quán)限控制和管理的示例

    這篇文章主要介紹了SpringBoot集成Shiro進(jìn)行權(quán)限控制和管理的示例,小編覺得挺不錯的,現(xiàn)在分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2018-03-03
  • 使用SpringBoot+OkHttp+fastjson實現(xiàn)Github的OAuth第三方登錄

    使用SpringBoot+OkHttp+fastjson實現(xiàn)Github的OAuth第三方登錄

    這篇文章主要介紹了使用SpringBoot+OkHttp+fastjson實現(xiàn)Github的OAuth第三方登錄,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2020-02-02
  • Java AOP動態(tài)代理詳細(xì)介紹

    Java AOP動態(tài)代理詳細(xì)介紹

    AOP是一種設(shè)計思想,是軟件設(shè)計領(lǐng)域中的面向切面編程,它是面向?qū)ο缶幊痰囊环N補充和完善。本文將用Java實現(xiàn)AOP代理的三種方式,需要的可以參考一下
    2022-08-08
  • springboot集成activemq的實例代碼

    springboot集成activemq的實例代碼

    本篇文章主要介紹了springboot集成activemq的實例代碼,詳細(xì)的介紹了ActiveMQ和Spring-Boot 集成 ActiveMQ,有興趣的可以了解下。
    2017-05-05
  • 每日六道java新手入門面試題,通往自由的道路第二天

    每日六道java新手入門面試題,通往自由的道路第二天

    這篇文章主要為大家分享了最有價值的6道java面試題,涵蓋內(nèi)容全面,包括數(shù)據(jù)結(jié)構(gòu)和算法相關(guān)的題目、經(jīng)典面試編程題等,對hashCode方法的設(shè)計、垃圾收集的堆和代進(jìn)行剖析,感興趣的小伙伴們可以參考一下
    2021-06-06
  • SpringCloud網(wǎng)關(guān)(Zuul)如何給多個微服務(wù)之間傳遞共享參數(shù)

    SpringCloud網(wǎng)關(guān)(Zuul)如何給多個微服務(wù)之間傳遞共享參數(shù)

    這篇文章主要介紹了SpringCloud網(wǎng)關(guān)(Zuul)如何給多個微服務(wù)之間傳遞共享參數(shù),具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2022-03-03
  • java并發(fā)數(shù)據(jù)包Exchanger線程間的數(shù)據(jù)交換器

    java并發(fā)數(shù)據(jù)包Exchanger線程間的數(shù)據(jù)交換器

    這篇文章主要為大家介紹了java并發(fā)數(shù)據(jù)包使用數(shù)據(jù)交換器Exchanger來進(jìn)行線程之間的數(shù)據(jù)交換。有需要的朋友可以借鑒參考下,希望能夠有所幫助
    2022-03-03
  • java的前期綁定和后期綁定使用示例

    java的前期綁定和后期綁定使用示例

    java的前期綁定在程序執(zhí)行前根據(jù)編譯時類型綁定,調(diào)用開銷較小,如C語言只有前期綁定這種方法調(diào)用
    2014-02-02
  • 啟用Spring事務(wù)管理@EnableTransactionManagement示例解析

    啟用Spring事務(wù)管理@EnableTransactionManagement示例解析

    這篇文章主要為大家介紹了啟用Spring事務(wù)管理@EnableTransactionManagement示例解析,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪
    2023-09-09
  • SpringBoot使用jsr303校驗的實現(xiàn)

    SpringBoot使用jsr303校驗的實現(xiàn)

    這篇文章主要介紹了SpringBoot使用jsr303校驗的實現(xiàn),文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2020-10-10

最新評論