logo头像

生活多彩,尽情享受!

二叉树

二叉树

二叉树是一个连通的无环图,并且每一个顶点的度不大于3。有根2叉数还要满足根节点的度不大于2。有了根节点之后,每个顶点定义了唯一的父节点,和最多2个子节点。

二叉树性质

  • 二叉树的每个节点至多只有二棵子树,二叉树的子树有左右之分,次序不能颠倒。
  • 二叉树的第 i 层至多有 2^(i-1) 个节点。
  • 深度为 k 的二叉树至多有 2^k - 1个节点。
  • 对任何一棵二叉树 T,如果其终端节点数为n0,度为2的节点数为n2,则 n0 = n2 + 1。
  • 一棵深度为 k,且有2^k - 1 个节点的书称为满二叉树
  • 若设二叉树的高度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第h层有叶子结点,并且叶子结点都是从左到右依次排布,称为完全二叉树
  • 平衡二叉树 又称为 AVL 树,它是一棵二叉排序树,具有如下性质:它是一棵空树或者它的左右两个子树的高度差的绝对值不超过1,并且左右两颗子树都是一棵平衡二叉树。

二叉树节点的数据结构

二叉树由一系列树节点构成,每个节点包括三部分:一个存储数据元素的数据域,一个存储左子节点地址的指针域,另一个是存储右子节点地址的指针域。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public class BinaryTreeNode {

private int data;

private BinaryTreeNode left;

private BinaryTreeNode right;

public BinaryTreeNode() {
}

public BinaryTreeNode(int data, BinaryTreeNode left, BinaryTreeNode right) {
this.data = data;
this.left = left;
this.right = right;
}

public int getData() {
return data;
}

public void setData(int data) {
this.data = data;
}

public BinaryTreeNode getLeft() {
return left;
}

public void setLeft(BinaryTreeNode left) {
this.left = left;
}

public BinaryTreeNode getRight() {
return right;
}

public void setRight(BinaryTreeNode right) {
this.right = right;
}
}

二叉树的遍历

前序遍历

  • 递归方式

    如果二叉树为空,空操作;如果二叉树不为空,访问根节点,遍历左子树,遍历右子树。

    1
    2
    3
    4
    5
    6
    7
    8
    public void preOrder(BinaryTreeNode root) {
    if (null == root) {
    return;
    }
    System.out.print(root.getData() + "\t");
    preOrder(root.getLeft());
    preOrder(root.getRight());
    }
  • 非递归方式

    用一个辅助 Stack,总是先把右孩子放进栈

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    /**
    * 前序遍历————非递归方式 1
    *
    * @param root 根节点
    */
    public void preOrderNonRecursive1(BinaryTreeNode root) {
    if (null == root) {
    return;
    }
    Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();// 辅助栈
    BinaryTreeNode cur = root;
    while (null != cur || !stack.isEmpty()) {
    while (null != cur) {// 不断把左子节点入栈,直到 cur 为空
    stack.push(cur);
    System.out.print(cur.getData() + "\t");// 前序遍历,先打印当前节点,再打印左子节点,然后再把右子节点添加到栈中
    cur = cur.getLeft();
    }
    if (!stack.isEmpty()) {// 栈不为空,弹出栈元素
    cur = stack.pop();// 此时弹出最左边的节点
    cur = cur.getRight();// 令当前节点为右子节点
    }
    }
    }

    /**
    * 前序遍历————非递归方式 2
    *
    * @param root 根节点
    */
    public void preOrderNonRecursive2(BinaryTreeNode root) {
    if (null == root) {
    return;
    }
    Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();// 辅助栈
    stack.add(root);
    while (!stack.isEmpty()) {
    BinaryTreeNode temp = stack.pop();
    System.out.print(temp.getData() + "\t");// 前序遍历,先根节点
    if (null != temp.getRight()) {// 先添加右孩子,因为栈是先入后出
    stack.add(temp.getRight());
    }
    if (null != temp.getLeft()) {
    stack.add(temp.getLeft());
    }
    }
    }

中序遍历

  • 递归方式

    如果根节点不为空,遍历左子树,然后访问根节点,最后遍历右子树

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    /**
    * 中序遍历————递归方式
    *
    * @param root 根节点
    */
    public void inOrderRecursive(BinaryTreeNode root) {
    if (null == root) {
    return;
    }
    inOrderRecursive(root.getLeft());
    System.out.print(root.getData() + "\t");
    inOrderRecursive(root.getRight());
    }
  • 非递归方式

    先把根节点的全部左孩子都入栈,然后输出栈顶元素,再处理栈顶元素的右子树

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    /**
    * 中序遍历————非递归方式
    *
    * @param root 根节点
    */
    public void inOrderNonRecursive(BinaryTreeNode root) {
    if (null == root) {
    return;
    }
    Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
    BinaryTreeNode cur = root;
    while (null != cur || !stack.isEmpty()) {
    while (null != cur) {// 不断将左子节点入栈,直到 cur 为空为止
    stack.push(cur);
    cur = cur.getLeft();
    }
    if (null != stack) {// 栈不为空,弹出栈元素
    stack.pop();// 此时弹出左边的元素
    System.out.print(cur.getData() + "\t");// 先打印左子节点,然后访问根节点,最后打印右子节点
    cur = cur.getRight();// 令当前节点为右子节点
    }
    }
    }

后序遍历

  • 递归方式

    如果二叉树不为空,先遍历左子树,再遍历右子树,最后访问根节点

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    /**
    * 后序遍历————递归方式
    *
    * @param root 根节点
    */
    public void postOrderRecursive(BinaryTreeNode root) {
    if (null == root) {
    return;
    }
    postOrderRecursive(root.getLeft());
    postOrderRecursive(root.getRight());
    System.out.print(root.getData() + "\t");
    }
  • 非递归方式

    双栈法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    /**
    * 后序遍历————非递归方式
    *
    * @param root 根节点
    */
    public void postOrderNonRecursive(BinaryTreeNode root) {
    if (null == root) {
    return;
    }
    Stack<BinaryTreeNode> stack1 = new Stack<BinaryTreeNode>();// 保存树节点
    Stack<BinaryTreeNode> stack2 = new Stack<BinaryTreeNode>();// 保存后序遍历的结果
    stack1.add(root);
    while (!stack1.isEmpty()) {
    BinaryTreeNode temp = stack1.pop();
    stack2.push(temp);// 将弹出的元素加到 stack2
    if (null != temp.getLeft()) {// 左子节点先入栈
    stack1.push(temp.getLeft());
    }
    if (null != temp.getRight()) {// 由子节点再入栈
    stack1.push(temp.getRight());
    }
    }
    while (!stack2.isEmpty()) {
    System.out.print(stack2.pop().getData() + "\t");
    }
    }

层次遍历

思路:分层遍历二叉树(从上到下,从左到右),相当于广度优先,使用队列实现。
队列初始化,将根节点压入队列。当队列不为空,进行如下操作:弹出一个节点,访问,若左子节点或右子节点不为空,将其压入队列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* 层次遍历
*
* @param root 根节点
*/
public void levelTraversal(BinaryTreeNode root) {
if (null == root) {
return;
}
Queue<BinaryTreeNode> queue = new LinkedList<BinaryTreeNode>();// 队列保存树节点
queue.add(root);
while (!queue.isEmpty()) {
BinaryTreeNode temp = queue.poll();// 弹出一个节点
System.out.print(temp.getData() + "\t");
if (null != temp.getLeft()) {// 添加左节点到队列
queue.add(temp.getLeft());
}
if (null != temp.getRight()) {// 添加右节点到队列
queue.add(temp.getRight());
}
}
}