二叉树的遍历

二叉树

DLR–前序遍历（根在前，从左往右，一棵树的根永远在左子树前面，左子树又永远在右子树前面 ）

LDR–中序遍历（根在中，从左往右，一棵树的左子树永远在根前面，根永远在右子树前面）

LRD–后序遍历（根在后，从左往右，一棵树的左子树永远在右子树前面，右子树永远在根前面）

前序遍历

ABDECF

#include <stdio.h>
#include <stdlib.h>
typedef char E;//元素类型
struct TreeNode {
    E element;//节点元素
    struct TreeNode *left;  //左子树
    struct TreeNode *right; //右子树
};
typedef struct TreeNode *Tree;//二叉树节点
void preorder(Tree t) { //前序遍历
    if (t == NULL) {//空树
        return;//返回
    }
    printf("%c", t->element);//访问根节点
    preorder(t->left);//访问左子树
    preorder(t->right);//访问右子树
}
int main(void) {
    Tree a = (Tree) malloc(sizeof(struct TreeNode));
    Tree b = (Tree) malloc(sizeof(struct TreeNode));
    Tree c = (Tree) malloc(sizeof(struct TreeNode));
    Tree d = (Tree) malloc(sizeof(struct TreeNode));
    Tree e = (Tree) malloc(sizeof(struct TreeNode));
    Tree f = (Tree) malloc(sizeof(struct TreeNode));
    a->left = b;
    a->right = c;
    b->left = d;
    b->right = e;
    c->left = NULL;
    c->right = f;
    d->left = NULL;
    d->right = NULL;
    e->left = NULL;
    e->right = NULL;
    f->left = NULL;
    f->right = NULL;
    a->element = 'A';
    b->element = 'B';
    c->element = 'C';
    d->element = 'D';
    e->element = 'E';
    f->element = 'F';
    preorder(a);
}

中序遍历

DBEAC

#include <stdio.h>
#include <stdlib.h>
typedef char E;//元素类型
struct TreeNode {
    E element;//节点元素
    struct TreeNode *left;  //左子树
    struct TreeNode *right; //右子树
};
void inorder(struct TreeNode *t) { //中序遍历
    if (t == NULL) {//空树
        return;//返回
    }
    inorder(t->left);//访问左子树
    printf("%c", t->element);//访问根节点
    inorder(t->right);//访问右子树
}
typedef struct TreeNode *Tree;//二叉树节点
int main(void) {
    Tree a = (Tree) malloc(sizeof(struct TreeNode));
    Tree b = (Tree) malloc(sizeof(struct TreeNode));
    Tree c = (Tree) malloc(sizeof(struct TreeNode));
    Tree d = (Tree) malloc(sizeof(struct TreeNode));
    Tree e = (Tree) malloc(sizeof(struct TreeNode));
    a->element = 'A';
    b->element = 'B';
    c->element = 'C';
    d->element = 'D';
    e->element = 'E';
    a->left = b;
    a->right = c;
    b->left = d;
    b->right = e;
    c->left = NULL;
    c->right = NULL;
    d->left = NULL;
    d->right = NULL;
    e->left = NULL;
    e->right = NULL;
    inorder(a);
    return 0;
}

后序遍历

DEBCA

#include <stdio.h>
#include <stdlib.h>
typedef char E;//元素类型
struct TreeNode {
    E element;//节点元素
    struct TreeNode *left;  //左子树
    struct TreeNode *right; //右子树
};
typedef struct TreeNode *Tree;//二叉树节点
void backorder(Tree root){
    if(root == NULL) return;
    backorder(root->left);
    backorder(root->right);
    printf("%c", root->element);
}
int main(void) {
    Tree a = (Tree) malloc(sizeof(struct TreeNode));
    Tree b = (Tree) malloc(sizeof(struct TreeNode));
    Tree c = (Tree) malloc(sizeof(struct TreeNode));
    Tree d = (Tree) malloc(sizeof(struct TreeNode));
    Tree e = (Tree) malloc(sizeof(struct TreeNode));
    a->element= 'A';
    b->element= 'B';
    c->element= 'C';
    d->element= 'D';
    e->element = 'E';
    a->left = b;
    a->right = c;
    b->left = d;
    b->right = e;
    c->left = NULL;
    c->right = NULL;
    d->left = NULL;
    d->right = NULL;
    e->left = NULL;
    e->right = NULL;
    backorder(a);
}

层序遍历

#include <stdio.h>
#include <stdlib.h>
typedef char E; // 元素类型
struct TreeNode
{
    int element;
    struct TreeNode *left;
    struct TreeNode *right;
};
typedef struct TreeNode *Tree; // 二叉树节点
// 层序遍历
void levelorder(Tree t)
{
    if (t == NULL)
    {           // 空树
        return; // 返回
    }
    Tree queue[100];   // 队列
    int front = 0;     // 队头
    int rear = 0;      // 队尾
    queue[rear++] = t; // 根节点入队
    while (front != rear)
    {                             // 队列不为空
        Tree p = queue[front++];  // 队头元素出队
        printf("%d", p->element); // 访问队头元素
        if (p->left != NULL)
        {                            // 左子树不为空
            queue[rear++] = p->left; // 左子树入队
        }
        if (p->right != NULL)
        {                             // 右子树不为空
            queue[rear++] = p->right; // 右子树入队
        }
    }
}
int main(void)
{
    Tree a = (Tree)malloc(sizeof(struct TreeNode));
    Tree b = (Tree)malloc(sizeof(struct TreeNode));
    Tree c = (Tree)malloc(sizeof(struct TreeNode));
    Tree d = (Tree)malloc(sizeof(struct TreeNode));
    Tree e = (Tree)malloc(sizeof(struct TreeNode));
    a->element = 1;
    b->element = 2;
    c->element = 3;
    d->element = 4;
    e->element = 5;
    a->left = b;
    a->right = c;
    b->left = d;
    b->right = e;
    c->left = NULL;
    c->right = NULL;
    d->left = NULL;
    d->right = NULL;
    e->left = NULL;
    e->right = NULL;
    levelorder(a);
    return 0;

}

java 实现

TreeNode.java
package org.example;

public class TreeNode<E> {
    public E element;
    public TreeNode<E> left, right;

    public TreeNode(E element){
        this.element = element;
    }
}

Main.java
package org.example;

public class Main {
    public static void main(String[] args) {
        TreeNode<Character> a = new TreeNode<>('A');
        TreeNode<Character> b = new TreeNode<>('B');
        TreeNode<Character> c = new TreeNode<>('C');
        TreeNode<Character> d = new TreeNode<>('D');
        TreeNode<Character> e = new TreeNode<>('E');
        TreeNode<Character> f = new TreeNode<>('F');
        a.left = b;
        a.right = c;
        b.left = d;
        b.right = e;
        c.right = f;
        System.out.println("----------------前序遍历（先打印根节点元素，然后左子树，最后右子树）---------------------");
        preOrder(a);
        System.out.println();
        System.out.println("----------------中序遍历（先左子树，然后打印根节点元素，最后右子树）---------------------");
        inOrder(a);
        System.out.println();
        System.out.println("----------------后序遍历（先左子树，然后右子树，最后打印根节点）---------------------");
        postOrder(a);
        System.out.println();
        System.out.println("----------------层序遍历---------------------");
        levelOrder(a);
    }

    private static <T> void preOrder(TreeNode<T> root) { //前序遍历
        if (root == null) return;
        System.out.print(root.element + " ");
        preOrder(root.left);    //先走左边
        preOrder(root.right);   //再走右边
    }

    private static <T> void inOrder(TreeNode<T> root) { //中序遍历
        if (root == null) return;
        inOrder(root.left);
        System.out.print(root.element + " ");
        inOrder(root.right);
    }

    private static <T> void postOrder(TreeNode<T> root) {//后序遍历
        if (root == null) return;
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.element + " ");
    }
    private static <T> void levelOrder(TreeNode<T> root) {//创建一个队列
        LinkedQueue<TreeNode<T>> queue = new LinkedQueue<>();
        queue.offer(root);  //将根结点丢进队列
        while(!queue.isEmpty()) { ////如果队列不为空，就一直不断地取出来
            TreeNode<T> node = queue.poll();
            System.out.print(node.element + " ");
            if(node.left != null) queue.offer(node.left);
            if(node.right != null) queue.offer(node.right);
        }
    }
}