# 二叉树

本文讲解二叉树的基本操作：

* 查找节点
* 计算树的高度
* 清空树
* 递归遍历：先序遍历、中序遍历、后序遍历
* 按层遍历
* 前序、中序的非递归遍历
* 树的路径
* 树的左旋和右旋

**来看一下树的结构：**

```java
class TreeNode {
    String value;
    TreeNode left;
    TreeNode right;
    public TreeNode() {

    }
    public TreeNode(String value) {
        this.value = value;
    }
}
```

首先，为了方便后面看到效果，先手动初始化一个有4个节点的二叉树：

```java
Tree tree = new Tree();
TreeNode root = new TreeNode("root");
TreeNode node1 = new TreeNode("ndoe1");
TreeNode node2 = new TreeNode("ndoe2");
TreeNode node3 = new TreeNode("ndoe3");
root.left = node1;
root.right = node2;
node1.left = node3;
```

## 一、查找节点

```java
//查找节点
public TreeNode findNode(TreeNode treeNode, String value) {
  if(null == treeNode)
    return null;

  if(treeNode.value.equals(value))
    return treeNode;

  TreeNode leftNode = findNode(treeNode.left, value);//递归左子树
  TreeNode rightNode = findNode(treeNode.right, value);//递归右子树
  if(leftNode.value.equals(value))
    return leftNode;
  if(rightNode.value.equals(value))
    return rightNode;

  return null;
}
```

## 二、计算树的深度

```java
//计算树的深度
//递归方法
public int deepth(TreeNode treeNode) {
  if(treeNode == null)
    return 0;
  int left = deepth(treeNode.left);
  int right = deepth(treeNode.right);
  return left > right? left + 1: right + 1;
}
```

## 三、清空树

```java
//清空二叉树
public void clearTreeNode(TreeNode treeNode) {
  if(null != treeNode) {
    clearTreeNode(treeNode.left);
    clearTreeNode(treeNode.right);
    treeNode = null;
  }
}
```

## 四、递归遍历

```java
//遍历1 先序遍历
public void showDLR(TreeNode treeNode) {
  if(null != treeNode) {
    showData(treeNode);
    showDLR(treeNode.left);
    showDLR(treeNode.right);
  }
}
//遍历2 中序遍历
public void showLDR(TreeNode treeNode) {
  if(null != treeNode) {
    showLDR(treeNode.left);
    showData(treeNode);
    showLDR(treeNode.right);
  }
}
//遍历3 后序遍历
public void showLRD(TreeNode treeNode) {
  if(null != treeNode) {
    showLRD(treeNode.left);
    showLRD(treeNode.right);
    showData(treeNode);
  }
}
```

## 五、按层遍历

```java
//遍历4 按层遍历 借助队列 先进先出
public void showByLevel(TreeNode treeNode) {
  if(null == treeNode)
    return;

  LinkedList<TreeNode> list = new LinkedList<>();
  TreeNode current;
  list.offer(treeNode);//将根节点入队

  while(!list.isEmpty()) {
    current = list.poll();//队首出队
    showData(current);//打印节点
    if(null != current.left) {
      list.offer(current.left);
    }
    if(null != current.right) {
      list.offer(current.right);
    }
  }
}
```

运行结果：

```java
树的深度是：3
先序遍历：
root-->ndoe1-->ndoe3-->ndoe2-->
中序遍历：
ndoe3-->ndoe1-->root-->ndoe2-->
后序遍历：
ndoe3-->ndoe1-->ndoe2-->root-->
按层遍历
root-->ndoe1-->ndoe2-->ndoe3-->
```

## 六、先序，中序遍历的非递归实现

```java
//遍历5 前序遍历的非递归实现
public void showDLRNotRecursion(TreeNode treeNode) {
  Stack<TreeNode> stack = new Stack<>();
  TreeNode node = treeNode;
  while(null != node || stack.size() >0) {
    while(null != node) {
      showData(node);
      stack.push(node);
      node = node.left;
    }
    if(stack.size() > 0) {
      node = stack.pop();
      node = node.right;
    }
  }
}
//遍历6  中序遍历的非递归实现
public void showLDRNotRecursion(TreeNode treeNode) {
  Stack<TreeNode> stack = new Stack<>();
  TreeNode node = treeNode;
  while(null != node || stack.size() > 0) {
    while(null != node) {
      stack.push(node);
      node = node.left;
    }
    if(stack.size() > 0) {
      node = stack.pop();
      showData(node);
      node = node.right;
    }
  }
}
```

## 七、树的路径

```java
public static void main(String[] args) {
    TreeNode node1 = new TreeNode("1");
    TreeNode node2 = new TreeNode("2");
    TreeNode node3 = new TreeNode("3");
    TreeNode node4 = new TreeNode("4");
    TreeNode node5 = new TreeNode("5");
    TreeNode node6 = new TreeNode("6");
    TreeNode node7 = new TreeNode("7");
    node1.left = node2;
    node1.right = node3;
    node2.left = node4;
    node2.right = node5;
    node5.left = node6;
    node5.right = node7;

    List<TreeNode> list = new ArrayList<>();
    list.add(node1);
    lujing(list, node1);
}
// 打印二叉树的所有路径
public static void lujing(List<TreeNode> list, TreeNode node) {
        if (node.left == null && node.right == null) {
            for (int i = 0; i < list.size(); i++) {
                System.out.print(list.get(i).val + " --> ");
            }
            System.out.println();
            return;
        }

        if (node.left != null) {
            List<TreeNode> newList = new ArrayList<>(list);
            newList.add(node.left);
            lujing(newList, node.left);
        }

        if (node.right != null) {
            List<TreeNode> newList = new ArrayList<>(list);
            newList.add(node.right);
            lujing(newList, node.right);
        }
    }
```

## 八、二叉树的左旋和右旋

* **左旋：**&#x8282;点右儿子的左儿子（若存在）变为节点的右儿子，节点变为右儿子的左儿子；
* **右旋：**&#x8282;点左二子的右儿子（若存在）变为节点的左二子，节点变为左二子的右儿子。

举个例子：

![](/files/-M7h5aPo35hFDswJ5ted)

可以看到，如果旋转前是一个二叉排序树，那么旋转后仍然是一个二叉排序树。

```java
// 左旋
public static void zuoxuan(TreeNode head) {
    TreeNode headRight = head.right;
    head.right = headRight.left;
    headRight.left = head;
}

// 右旋
public static void youxuan(TreeNode head) {
    TreeNode headLeft = head.left;
    head.left = headLeft.right;
    headLeft.right = head;
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jun-wang.gitbook.io/learnjava/ji-shu-xue-xi/shu-ju-jie-gou/er-cha-shu.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.