溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這是個常見的面試題，比如說通過二叉樹的先序和中序遍歷，得到二叉樹的層序遍歷等問題
先序+中序->建樹
假設現在有個二叉樹，如下：
此時遍歷順序是：
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，初始先把root節點加入到隊列，當隊列不為空的時候取隊列頭的節點node，打印node的節點值，如果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);
}
}
}
深度優先和廣度優先
其實就是換個說法而已，深度優先不就是先序遍歷嘛，廣度優先就是層序遍歷
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<Tree> st = new Stack<Tree>();
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 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); //深度優先遍歷
// Main.deepFirstPrintNoneRec(root); //深度優先遍歷的非遞歸版本
}
總結
以上就是本文關于Java中二叉樹的建立和各種遍歷實例代碼的全部內容，希望對大家有所幫助。感興趣的朋友可以繼續參閱本站：
《Java編程求二叉樹的鏡像兩種方法介紹》
《Java語言描述二叉樹的深度和寬度》
《Java二叉樹路徑和代碼示例》
如有不足之處，歡迎留言指出。感謝朋友們對本站的支持！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
