1 关于二叉树

1.1 主要性质

1. 一棵非空二叉树的第i层最多有$2^i$（i >= 1)个节点
2. 一棵深度为k的二叉树最多有$2^k$-1个节点
3. 一棵非空二叉树，设叶子节点数为$n_0$，度为2的节点数为$n_2$，则$n_0$ = $n_2$ + 1
4. 设有n个节点的完全二叉树的深度为k，则 k = [$lo{g}_{2}n$] + 1 （[$lo{g}_{2}n$]表示不大于$lo{g}_{2}n$的最大整数）

1.2 二叉树的遍历

1、二叉树的遍历规则

• 先序：根节点、左孩子、右孩子
• 中序：左孩子、根节点、右孩子
• 后序：左孩子、右孩子、根节点
• 层序：按照二叉树深度递增的顺序，每层从左到右遍历

2、举例

以上图为例，其各遍历结果分别为：

先序遍历 [A, B, D, E, F, C]
中序遍历 [D, B, F, E, A, C]
后序遍历 [D, F, E, B, C, A]
层次遍历 [A, B, C, D, E, F]当使用序列构造二叉树时，对应序列最后一个叶子节点之前的空节点不能省略。且序列最后一个元素为对应序列最后一个叶子节点。
先序遍历 [A, B, D, null, null, E, F, null, null, null, C]
层次遍历 [A, B, C, D, E, null, null, null, null, F]

以上图为例，其各遍历结果分别为：

先序遍历 [5, 4, 11, 7, 2, 8, 13, 10, 1]        
中序遍历 [7, 11, 2, 4, 5, 13, 8, 10, 1]
后序遍历 [7, 2, 11, 4, 13, 1, 10, 8, 5]
层序遍历 [5, 4, 8, 11, 13, 10, 7, 2, 1]当使用序列构造二叉树时，对应序列最后一个叶子节点之前的空节点不能省略。且序列最后一个元素为对应序列最后一个叶子节点。
先序遍历 [5, 4, 11, 7, null, null, 2, null, null, null, 8, 13, null, null, 10, null, 1]
层序遍历 [5, 4, 8, 11, null, 13, 10, 7, 2, null, null, null, 1]

2 二叉树的创建及遍历

2.1 C语言实现

2.1.1 递归遍历

#include <malloc.h>
#include <stdio.h>
#include <stdlib.h>typedef char elemType;
typedef struct BiTNode {elemType data;struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;BiTree createBiTree();                     // 先序输入节点的值，构造二叉树
void PreOrderRecursiveTraverse(BiTree T);  // 先序递归遍历二叉树
void InOrderRecursiveTraverse(BiTree T);   // 中序递归遍历二叉树
void PostOrderRecursiveTraverse(BiTree T); // 后序递归遍历二叉树
void visit(elemType x);                    // 输出元素x
BiTNode* SearchNode(BiTree T, elemType x); // 在以T为根节点的二叉树中查找元素为x的节点
int CountLeaf(BiTree T);                   // 求二叉树叶子节点个数
int BiTreeHigh(BiTree T);                  // 求二叉树的深度
int CountNodes(BiTree T);                  // 求二叉树叶子节点个数int main(void)
{BiTree root;printf("请按先序顺序输入节点值，输入‘#’代表节点为空：\n");root = createBiTree();printf("先序递归：");PreOrderRecursiveTraverse(root);printf("\n");printf("中序递归：");InOrderRecursiveTraverse(root);printf("\n");printf("后序递归：");PostOrderRecursiveTraverse(root);printf("\n");BiTNode* temp = SearchNode(root, 'E');printf("查找出的节点元素为：%c\n", temp->data);int leaves1 = CountLeaf(root);printf("二叉树叶子节点总数为：%d\n", leaves1);int nodes = CountNodes(root);printf("二叉树节点总数为：%d\n", nodes);int high = BiTreeHigh(root);printf("二叉树深度为：%d\n", high);return 0;
}// 先序输入节点的值，构造二叉树
BiTree createBiTree()
{char ch;BiTree T;if ((ch = getchar()) == '#') {T = NULL;} else {T = (BiTNode*)malloc(sizeof(BiTNode));T->data = ch;T->lchild = createBiTree();T->rchild = createBiTree();}return T;
}
// 输出元素x
void visit(elemType x) { printf("%c, ", x); }
// 先序遍历二叉树
void PreOrderRecursiveTraverse(BiTree T)
{if (T != NULL) {visit(T->data);PreOrderRecursiveTraverse(T->lchild);PreOrderRecursiveTraverse(T->rchild);}
}
// 中序遍历二叉树
void InOrderRecursiveTraverse(BiTree T)
{if (T) {InOrderRecursiveTraverse(T->lchild);visit(T->data);InOrderRecursiveTraverse(T->rchild);}
}
// 后序遍历二叉树
void PostOrderRecursiveTraverse(BiTree T)
{if (T) {PostOrderRecursiveTraverse(T->lchild);PostOrderRecursiveTraverse(T->rchild);visit(T->data);}
}
// 在以T为根节点的二叉树中查找元素为x的节点
BiTNode* SearchNode(BiTree T, elemType x)
{if (!T) return NULL;if (T->data == x) {return T;} else {BiTNode* temp;temp = SearchNode(T->lchild, x);if (!temp) {return SearchNode(T->rchild, x);}return temp;}return NULL;
}// 求二叉树的深度
int BiTreeHigh(BiTree T)
{int lh, rh, h;if (T == NULL) {h = 0;} else {lh = BiTreeHigh(T->lchild);rh = BiTreeHigh(T->rchild);h = (lh > rh ? lh : rh) + 1;}return h;
}
// 求二叉树叶子节点个数
int CountLeaf(BiTree T)
{if (T == NULL) {return 0;} else if ((T->lchild == NULL) && (T->rchild == NULL)) {return 1;} else {return (CountLeaf(T->lchild) + CountLeaf(T->rchild));}
}
// 求二叉树总节点个数
int CountNodes(BiTree T)
{if (T) {if ((T->lchild == NULL) && (T->rchild == NULL)) {return 1;} else {return (CountNodes(T->rchild) + CountNodes(T->lchild) + 1);}}return 0;
}

请按先序顺序输入节点值，输入‘#’代表节点为空：
ABD##EF###C##
先序递归：A, B, D, E, F, C,
中序递归：D, B, F, E, A, C,
后序递归：D, F, E, B, C, A,
查找出的节点元素为：E
二叉树叶子节点总数为：3
二叉树节点总数为：6
二叉树深度为：4C:\Users\fy\Documents\workspace\visual_studio\CMakeProject1\out\build\x64-Debug\CMakeProject1.exe (进程 9424)已退出，代 码为 0。
按任意键关闭此窗口. . .

2.1.2 非递归遍历

先序

先序遍历的过程是首先访问根结点.然后先序遍历根的左子树，最后先序遍历根的右子树。对于根的左子树和右子树，遍历的过程相同。如果用非递归方法，就要在遍历左子树之前先保存右子树根结点的地址(指针)，以便在完成左子树的遍历之后取出右子树根结点的地址，再遍历这棵右子树。同样,在遍历左子树的左子树之前也要先保存左子树的右子树根结点的地址，以此类推。可以看出,对这些地址的保存和取出符合后进先出的原则,可设置一个辅助栈来保存这些右子树根结点的地址。为了方便编写算法,这个辅助栈保存所有经过的结点的指针,包括空的根指针和空的孩子指针。

中序

中序遍历的过程是首先中序遍历左子树,然后访问根结点，最后中序遍历根的右子树。对于根的左子树和右子树,遍历的过程相同。如果用非递归方法，就要在遍历左子树之前先保存根结点的地址(指针),以便在完成左子树的遍历之后取出根结点的地址访问根结点,然后再中序遍历右子树。同样,在中序遍历左子树的左子树之前也要先保存左子树的根结点地址，以此类推。可以看出,对这些地址的保存和取出符合后进先出的原则,可设置一个辅助栈来保存所经过的结点的地址。为了方便编写算法,栈中也保存空树的空指针。中序遍历二叉树的非递归算法如下:

后序

后序遍历的过程是首先后序遍历左子树，然后后序遍历根的右子树,最后访问根结点。如果用非递归方法，就要在遍历左子树之前先保存根结点的地址，以便在完成左子树遍历之后根据根结点的地址遍历右子树和访问根结点。对于根的左子树和根的右子树，遍历的过程相同。对这些地址的保存和使用符合后进先出的原则，可设置-一个辅助栈来保存所经过的结点的地址。因为后序遍历的特点是只有在遍历了左子树和右子树之后才能访问根结点,所以为了表明子树是否被遍历过,可再设置一个辅助变量。

2.1.3 层次遍历

由层次遍历的定义可以推知，在进行层次遍历时，对一层结点访问完后再按照它们的访问次序对各个结点的左孩子和右孩子顺序访问，这样一层一层地进行，先遇到的结点先访问,这与队列的操作原则比较吻合。因此，在进行层次遍历时可设置一个队列结构,遍历从二叉树的根结点开始，首先将根结点指针入队列，然后从队头取出一个元素,每取一个元素执行下面两个操作:

• 访问该元素所指的结点;
• 若该元素所指结点的左、右孩子指针非空，则将该元素所指结点的非空左孩子指针和右孩子指针顺序入队。

若队列非空,重复以上过程,当队列为空时,二叉树的层次遍历结束。在下面的层次遍历算法中,二叉树以二叉链表存储，一 维数组Queue[ MAXNODE ]用于实现队列,变量front和rear分别表示当前队列首元素和队列尾元素在数组中的位置。

#include <malloc.h>
#include <stdio.h>
#include <stdlib.h>typedef char elemType;
typedef struct BiTNode {elemType data;struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
BiTree createBiTree();                  // 先序输入节点的值，构造二叉树
void PreOrderTraverseNonRec(BiTree T);  // 先序非递归遍历二叉树
void InOrderTraverseNonRec(BiTree T);   // 中序非递归遍历二叉树
void PostOrderTraverseNonRec(BiTree T); // 后序非递归遍历二叉树
void LevelOrderTraverse(BiTree T);      // 层次遍历二叉树（从上到下，每层从左到右）#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef struct StackNode {BiTNode** top;BiTNode** base;int size;
} Stack;
Stack* InitStack();             // 初始化空栈
int isEmpty(Stack* S);          // 判断栈空
BiTNode* GetTop(Stack* S);      // 取栈顶数据
int push(Stack* S, BiTNode* p); // 入栈
BiTNode* pop(Stack* S);         // 出栈#define MAXSIZE 100
typedef struct {BiTNode* data[MAXSIZE]; // 指针数组，数组中的每一个元素指向BiTNode类型的节点// front:指向队列中第一个元素// rear:指向队列中最后一个元素下一位置int front, rear;
} Queue;int main(void)
{BiTree root;printf("请按先序顺序输入节点值，输入‘#’代表节点为空：\n");root = createBiTree();printf("先序非递归：");PreOrderTraverseNonRec(root);printf("\n");printf("中序非递归：");InOrderTraverseNonRec(root);printf("\n");printf("后序非递归：");PostOrderTraverseNonRec(root);printf("\n");printf("按层次遍历：");LevelOrderTraverse(root);printf("\n");return 0;
}// 先序输入节点的值，构造二叉树
BiTree createBiTree()
{char ch;BiTree T;if ((ch = getchar()) == '#') {T = NULL;} else {T = (BiTNode*)malloc(sizeof(BiTNode));T->data = ch;T->lchild = createBiTree();T->rchild = createBiTree();}return T;
}
// 输出元素x
void visit(elemType x) { printf("%c, ", x); }
Stack* InitStack()
{Stack* S;S = (Stack*)malloc(sizeof(Stack));S->base = (BiTNode**)calloc(STACK_INIT_SIZE, sizeof(BiTNode*));S->top = S->base;S->size = STACK_INIT_SIZE;return S;
}
// 取栈顶数据
BiTNode* GetTop(Stack* S)
{BiTNode* p = NULL;if (S->top == S->base) {return NULL;}p = *(S->top - 1);return p;
}
// 入栈
int push(Stack* S, BiTNode* p)
{if (S->top - S->base >= S->size) {S->base = (BiTNode**)realloc(S->base, (STACKINCREMENT + STACK_INIT_SIZE) * sizeof(BiTNode*));if (!S->base) {printf("入栈失败！\n");return 0;}S->top = S->base + S->size;S->size += STACKINCREMENT;}*S->top++ = p;return 1;
}
// 出栈
BiTNode* pop(Stack* S)
{if (S->top == S->base) {printf("出栈失败！\n");return NULL;}return *--S->top;
}
// 判断栈空
int isEmpty(Stack* S) { return S->top == S->base; }// 先序非递归遍历二叉树
void PreOrderTraverseNonRec(BiTree T)
{Stack* S = InitStack();BiTNode* p;push(S, T);while (!isEmpty(S)) {p = GetTop(S);//向左走到尽头while (p != NULL) {visit(p->data);push(S, p->lchild);p = GetTop(S);}/*向左走到尽头*//*while (p = GetTop(S)) {*//*visit(p->data);*//*push(S, p->lchild);*//*}*/p = pop(S); //空指针退栈if (!isEmpty(S)) {p = pop(S);push(S, p->rchild); //向右一步}}
}
// 中序非递归遍历二叉树
void InOrderTraverseNonRec(BiTree T)
{Stack* S = InitStack();BiTNode* p;push(S, T);while (!isEmpty(S)) {p = GetTop(S);//向左走到尽头while (p != NULL) {push(S, p->lchild);p = GetTop(S);}pop(S); //空指针退栈if (!isEmpty(S)) {p = pop(S);visit(p->data);push(S, p->rchild);}}
}
// 后序非递归遍历二叉树
void PostOrderTraverseNonRec(BiTree T)
{Stack* S = InitStack();BiTNode *p = T, *q; // q指向最近被访问过的节点，用作标志do {//向左走到尽头while (p) {push(S, p);p = p->lchild;}q = NULL;while (!isEmpty(S)) {p = GetTop(S);//右子树为空或已经访问过if ((p->rchild == NULL) || q == p->rchild) {visit(p->data);q = p;pop(S);}// 右子树非空且未被遍历else {p = p->rchild; //向右一步break;}}} while (!isEmpty(S));
}
// 层次遍历二叉树（从上到下，每层从左到右）
void LevelOrderTraverse(BiTree T)
{Queue Q;BiTNode* temp = NULL;Q.front = Q.rear = 0;if (T) {Q.data[Q.rear] = T;Q.rear = (Q.rear + 1) % MAXSIZE;while (Q.front != Q.rear) {temp = Q.data[Q.front];visit(temp->data);Q.front = (Q.front + 1) % MAXSIZE;if (temp->lchild) {Q.data[Q.rear] = temp->lchild;Q.rear = (Q.rear + 1) % MAXSIZE;}if (temp->rchild) {Q.data[Q.rear] = temp->rchild;Q.rear = (Q.rear + 1) % MAXSIZE;}}}
}

请按先序顺序输入节点值，输入‘#’代表节点为空：
ABD##EF###C##
先序非递归：A, B, D, E, F, C,
中序非递归：D, B, F, E, A, C,
后序非递归：D, F, E, B, C, A,
按层次遍历：A, B, C, D, E, F,C:\Users\fy\Documents\workspace\visual_studio\CMakeProject1\out\build\x64-Debug\CMakeProject1.exe (进程 12164)已退出，代码为 0。
按任意键关闭此窗口. . .

2.2 java实现

C:\Users\fy\Documents\workspace\idea\leetcode\src\MyBinaryTree\
├──BinaryTree.java
├──MyUtils.java
├──TestBiTree.java
├──TreeNode.java
└──二叉树.png

MyBinaryTree.TreeNode.java

package MyBinaryTree;public class TreeNode<T> {public T val;public TreeNode<T> left;public TreeNode<T> right;TreeNode() {}TreeNode(T val) {this.val = val;}TreeNode(T val, TreeNode<T> left, TreeNode<T> right) {this.val = val;this.left = left;this.right = right;}
}

MyBinaryTree.BinaryTree.java

package MyBinaryTree;import java.util.*;public class BinaryTree<T> {// 节点个数private int size;// 头节点private TreeNode<T> root;private static int index;public int getSize() {return size;}public TreeNode<T> getRoot() {return root;}// 层序遍历创建二叉树，空节点值为null。列表最后一个元素为树中层序遍历最后一个叶子节点的值public void createBiTreeByLevelOrder(List<T> levelOrder) {// 列表为空或头节点值为空if (levelOrder.size() == 0 || levelOrder.get(0) == null) {return;}// 根节点赋值this.root = new TreeNode<>(levelOrder.get(0));size++;Queue<TreeNode<T>> que = new LinkedList<>();que.offer(this.root);int i = 0;while (!que.isEmpty()) {TreeNode<T> node = que.poll();int leftIndex = 2 * i + 1;int rightIndex = 2 * i + 2;// 左孩子赋值if (leftIndex < levelOrder.size() && levelOrder.get(leftIndex) != null) {node.left = new TreeNode<>(levelOrder.get(leftIndex));size++;que.offer(node.left);}// 右孩子赋值if (rightIndex < levelOrder.size() && levelOrder.get(rightIndex) != null) {node.right = new TreeNode<>(levelOrder.get(rightIndex));size++;que.offer(node.right);}i += 1;}}// 先序递归遍历创建二叉树，空节点值为null。列表最后一个元素为树中先序遍历最后一个叶子节点的值public void createBiTreeByPreOrder(List<T> preOrder) {if (preOrder.size() == 0) {return;}BinaryTree.index = 0;this.root = createBiTreeByPreOrderHelper(preOrder, BinaryTree.index);// this.root = createBiTreeByPreOrderHelper(preOrder);}// private TreeNode<T> createBiTreeByPreOrderHelper(List<T> preOrder) {//     TreeNode<T> node = null;//     if (BinaryTree.index < preOrder.size() && preOrder.get(BinaryTree.index) != null) {//         node = new TreeNode<>(preOrder.get(BinaryTree.index));//         this.size++;////         BinaryTree.index++;//         node.left = createBiTreeByPreOrderHelper(preOrder);//         BinaryTree.index++;//         node.right = createBiTreeByPreOrderHelper(preOrder);//     }//     return node;// }private TreeNode<T> createBiTreeByPreOrderHelper(List<T> preOrder, int index) {TreeNode<T> node = null;if (BinaryTree.index < preOrder.size() && preOrder.get(BinaryTree.index) != null) {node = new TreeNode<>(preOrder.get(BinaryTree.index));this.size++;node.left = createBiTreeByPreOrderHelper(preOrder, BinaryTree.index++);node.right = createBiTreeByPreOrderHelper(preOrder, BinaryTree.index++);}return node;}// 返回二叉树递归先序遍历结果public List<T> preOrderRecursive() {List<T> res = new ArrayList<>();preOrderRecursiveHelper(this.root, res);return res;}private void preOrderRecursiveHelper(TreeNode<T> root, List<T> res) {if (root != null) {res.add(root.val);preOrderRecursiveHelper(root.left, res);preOrderRecursiveHelper(root.right, res);}}// 返回二叉树非递归先序遍历结果public List<T> preOrderNonRecursive() {List<T> res = new ArrayList<>();if (root == null) return res;TreeNode<T> node = root;Deque<TreeNode<T>> stack = new ArrayDeque<>();while (node != null || !stack.isEmpty()) {// 向左走到尽头while (node != null) {res.add(node.val);stack.push(node);node = node.left;}// 向右走一步node = stack.pop();node = node.right;}return res;}// 返回二叉树非递归中序遍历结果public List<T> inOrderNonRecursive() {List<T> res = new ArrayList<>();if (root == null) return res;TreeNode<T> node = root;Deque<TreeNode<T>> stack = new ArrayDeque<>();while (node != null || !stack.isEmpty()) {// 向左走到尽头while (node != null) {stack.push(node);node = node.left;}// 向右走一步node = stack.pop();res.add(node.val);node = node.right;}return res;}// 返回二叉树非递归后序遍历结果public List<T> postOrderNonRecursive() {List<T> res = new ArrayList<>();if (root == null) return res;// prev 是前一个访问的节点TreeNode<T> node = root, prev = null;Deque<TreeNode<T>> stack = new ArrayDeque<>();while (node != null || !stack.isEmpty()) {while (node != null) {stack.push(node);node = node.left;}node = stack.pop();// 右节点存在且未被访问if (node.right != null && node.right != prev) {stack.push(node);node = node.right;}//右节点存在但已被访问else {res.add(node.val);prev = node;node = null;}}return res;}// 层序遍历二叉树public List<T> levelOrder() {List<T> res = new ArrayList<>();if (root == null) return res;Queue<TreeNode<T>> que = new ArrayDeque<>();que.offer(root);while (!que.isEmpty()) {TreeNode<T> node = que.poll();res.add(node.val);// 左孩子入队if (node.left != null) {que.offer(node.left);}// 右孩子入队if (node.right != null) {que.offer(node.right);}}return res;}
}

MyBinaryTree.TestBiTree.java

package MyBinaryTree;import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;public class TestBiTree {public static void main(String[] args) {// 先序序列，空节点值为null。列表最后一个元素为树中先序遍历最后一个叶子节点的值List<Character> preOrderList = new ArrayList<>(Arrays.asList('A', 'B', 'D', null, null, 'E', 'F', null, null, null, 'C'));// 层序序列，空节点值为null。列表最后一个元素为树中层次遍历最后一个叶子节点的值List<Character> levelOrderList = new ArrayList<>(Arrays.asList('A', 'B', 'C', 'D', 'E', null, null, null, null, 'F'));BinaryTree<Character> bitree = new BinaryTree<>();// bitree.createBiTreeByPreOrder(preOrderList);bitree.createBiTreeByLevelOrder(levelOrderList);System.out.println("1 先序递归遍历");System.out.println(bitree.preOrderRecursive());System.out.println("2 先序非递归遍历");System.out.println(bitree.preOrderNonRecursive());System.out.println("3 中序非递归遍历");System.out.println(bitree.inOrderNonRecursive());System.out.println("4 后序非递归遍历");System.out.println(bitree.postOrderNonRecursive());System.out.println("5 层次遍历");System.out.println(bitree.levelOrder());new MyUtils<Character>().genGraphvizDotFileOfBiTree(bitree.getRoot());}
}

1 先序递归遍历
[A, B, D, E, F, C]
2 先序非递归遍历
[A, B, D, E, F, C]
3 中序非递归遍历
[D, B, F, E, A, C]
4 后序非递归遍历
[D, F, E, B, C, A]
5 层次遍历
[A, B, C, D, E, F]Process finished with exit code 0

MyBinaryTree.MyUtils.java

package MyBinaryTree;import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintStream;
import java.util.ArrayList;
import java.util.List;public class MyUtils<T> {public void genGraphvizDotFileOfBiTree(TreeNode<T> root) {List<String> code = new ArrayList<>();String line = " -> ";code.add("digraph G {");code.add("\tnode[shape=circle,color=blue];");code.add("\tedge[arrowhead=none]");graphvizDfs(root, code, line);code.add("}");File f = new File(String.valueOf(root.hashCode()) + ".dot");PrintStream out = null;try {out = new PrintStream(f);}catch (FileNotFoundException e) {e.printStackTrace();}System.setOut(out);System.out.println(String.join("\n", code));System.setOut(System.out);}private void graphvizDfs(TreeNode<T> node, List<String> code, String line) {if (node == null) return;String start = String.valueOf(node.val);if (node.left != null) {code.add("\t" + start + line + node.left.val + "[side=left]");}if (node.right != null) {code.add("\t" + start + line + node.right.val + "[side=right]");}graphvizDfs(node.left, code, line);graphvizDfs(node.right, code, line);}
}

bitree.dot

digraph G {node[shape=circle,color=blue];edge[arrowhead=none]3 -> 4[side=left]3 -> 5[side=right]4 -> 1[side=left]4 -> 2[side=right]2 -> 0[side=left]
}

2.3 C++实现

#include <iostream>
#include <queue>
#include <stack>
#include <vector>
using namespace std;#define nil INT_MIN// 二叉树结点定义
struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode() : val(0), left(nullptr), right(nullptr) {}TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};// 创建二叉树
TreeNode *createBinaryTree(vector<int> &vals, int n, int index)
{TreeNode *node = nullptr;if (index < n && vals[index] != nil) {node = new TreeNode(vals[index]);node->left = createBinaryTree(vals, n, 2 * index + 1);node->right = createBinaryTree(vals, n, 2 * index + 2);}return node;
}// 打印一个结点信息
void visit(const TreeNode *node) { cout << node->val << ' '; }// 递归遍历
void preOrder(TreeNode *root, void (*visit)(const TreeNode *node))
{if (root) {visit(root);preOrder(root->left, visit);preOrder(root->right, visit);}
}
void inOrder(TreeNode *root, void (*visit)(const TreeNode *node))
{if (root) {inOrder(root->left, visit);visit(root);inOrder(root->right, visit);}
}
void postOrder(TreeNode *root, void (*visit)(const TreeNode *node))
{if (root) {postOrder(root->left, visit);postOrder(root->right, visit);visit(root);}
}// 非递归遍历
void preOrderNonRecursive(TreeNode *root, void (*visit)(const TreeNode *node))
{stack<TreeNode *> stk;TreeNode *p = root;while (p || !stk.empty()) {// 向左走到尽头while (p) {visit(p);stk.push(p);p = p->left;}p = stk.top();stk.pop();p = p->right;}
}
void inOrderNonRecursive(TreeNode *root, void (*visit)(const TreeNode *node))
{stack<TreeNode *> stk;TreeNode *p = root;while (p || !stk.empty()) {// 向左走到尽头while (p) {stk.push(p);p = p->left;}p = stk.top();stk.pop();visit(p);p = p->right;}
}
/** 后序：左子树 右子树 根结点* 思想：1 沿着根的左孩子，依次入栈，直到左孩子为空*      2 读栈顶元素，若其右孩子不空且未被访问过，将右子树执行步骤 1；*        否则，栈顶元素出栈并访问*/
void postOrderNonRecursive(TreeNode *root, void (*visit)(const TreeNode *node))
{stack<TreeNode *> stk;// p 为当前访问的结点，rencent 为最近访问过的结点TreeNode *p = root, *recent = nullptr;while (p || !stk.empty()) {// 走到最左边if (p) {stk.push(p);p = p->left;}// 向右else {p = stk.top();// 若右子树存在且未被访问if (p->right && p->right != recent) {p = p->right;stk.push(p);p = p->left;}// 出栈并访问else {stk.pop();visit(p);recent = p;// 每次出栈访问完一个结点就相当于遍历完以该结点为根的子树，需将 p 置空p = nullptr;}}}
}// 层次遍历
void levelOrder(TreeNode *root, void (*visit)(const TreeNode *node))
{queue<TreeNode *> q;q.push(root);while (!q.empty()) {TreeNode *node = q.front();q.pop();visit(node);if (node->left)q.push(node->left);if (node->right)q.push(node->right);}
}
int main(int argc, char const *argv[])
{vector<int> vals{5, 6, 9, 3, nil, 44, 1, 11, 22};TreeNode *root = createBinaryTree(vals, vals.size(), 0);cout << "1、递归遍历\n";cout << "先序：";preOrder(root, visit);cout << endl;cout << "中序：";inOrder(root, visit);cout << endl;cout << "后序：";postOrder(root, visit);cout << endl << endl;cout << "2、非递归遍历\n";cout << "先序：";preOrderNonRecursive(root, visit);cout << endl;cout << "中序：";inOrderNonRecursive(root, visit);cout << endl;cout << "后序：";postOrderNonRecursive(root, visit);cout << endl << endl;cout << "3、层次遍历\n";cout << "层次遍历：";levelOrder(root, visit);cout << endl << endl;return 0;
}

1、递归遍历
先序：5 6 3 11 22 9 44 1
中序：11 3 22 6 5 44 9 1
后序：11 22 3 6 44 1 9 52、非递归遍历
先序：5 6 3 11 22 9 44 1
中序：11 3 22 6 5 44 9 1
后序：11 22 3 6 44 1 9 53、层次遍历
层次遍历：5 6 9 3 44 1 11 22

2.4 Morris遍历

在二叉树的遍历中，无论是先序、中序、后序或是层序遍历，都需要额外的辅助空间。而morris（莫里斯）遍历则是一种不需要额外空间的遍历算法，它能以$O(1)$的空间复杂度实现二叉树的遍历。

morris遍历的思想类似于中序线索二叉树的思想，若是一个节点无右孩子，则让其右指针指向其后继节点，这样便能像链表一样顺序访问每个节点。且遍历时会恢复节点指针的原始值，因此不会使树的结构发生改变。

2.4.1 morris先序遍历

假设当前节点为cur，并且开始时赋值为根节点root，cur的中序前驱节点为pre。

1、若cur不为空

• 若cur没有左孩子，则访问cur，并向右走一步
• 若cur有左孩子，则找到cur的前驱节点pre
  • 若pre的右指针为空，则将pre右指针指向cur（类似线索二叉树），并向左走一步
  • 若pre的右指针指向cur，则将pre右指针置空（还原树结构），并向右走一步

2、cur为空时，停止遍历

2.4.2 morris中序遍历

morris中序遍历思想与先序相同，只是访问节点的顺序不同。

2.4.3 morris后序遍历

morris后序遍历思想与先序、中序类似，只是对节点的处理逻辑稍有变化。因为后序遍历中，右孩子需要先于根节点访问。

要点：
1、若一个节点无左孩子，则直接访问此节点。
2、若一个节点有左孩子，则将此节点左孩子至其前驱节点这一区间逆序访问，从而得到后序序列。

如下图所示：对于节点A，将其左孩子至前驱这段，逆序访问。实现时，将此段节点像逆转单链表一样逆转，然后访问，再逆转恢复原来的结构。

示例java代码

先序遍历：[A, B, D, E, F, C]
中序遍历：[D, B, F, E, A, C]
后序遍历：[D, F, E, B, C, A]

package MyBinaryTree;public class TreeNode<T> {public T val;public TreeNode<T> left;public TreeNode<T> right;TreeNode() {}public TreeNode(T val) {this.val = val;}public TreeNode(T val, TreeNode<T> left, TreeNode<T> right) {this.val = val;this.left = left;this.right = right;}
}

package MyBinaryTree;import java.util.*;// 用于处理二叉树的一些静态方法
public class BiTreeUtils {// 层序遍历创建二叉树，空节点值为null。列表最后一个元素为树中层序遍历最后一个叶子节点的值public static <T> TreeNode<T> createBiTreeByLevelOrder(List<T> levelOrder) {// 列表为空或头节点值为空if (levelOrder.size() == 0 || levelOrder.get(0) == null) {return null;}// 根节点赋值TreeNode<T> root = new TreeNode<>(levelOrder.get(0));Queue<TreeNode<T>> que = new LinkedList<>();que.offer(root);int i = 0;while (!que.isEmpty()) {TreeNode<T> node = que.poll();int leftIndex = 2 * i + 1;int rightIndex = 2 * i + 2;// 左孩子赋值if (leftIndex < levelOrder.size() && levelOrder.get(leftIndex) != null) {node.left = new TreeNode<>(levelOrder.get(leftIndex));que.offer(node.left);}// 右孩子赋值if (rightIndex < levelOrder.size() && levelOrder.get(rightIndex) != null) {node.right = new TreeNode<>(levelOrder.get(rightIndex));que.offer(node.right);}i += 1;}return root;}// morris前序遍历public static <T> List<T> morrisPreOrder(TreeNode<T> root) {List<T> res = new ArrayList<>();TreeNode<T> cur = root;while (cur != null) {// 如果没有左子树，则访问当前节点。并向右走一步if (cur.left == null) {res.add(cur.val);cur = cur.right;}// 有左子树else {// 找到cur的前驱节点preTreeNode<T> pre = cur.left;while (pre.right != null && pre.right != cur) {pre = pre.right;}// 第一次访问cur，则将pre右孩子指向cur。并向左走一步if (pre.right == null) {res.add(cur.val);pre.right = cur;cur = cur.left;}// 第二次访问cur，则将pre右孩子指针恢复（设为null）。并向右走一步else {pre.right = null;cur = cur.right;}}}return res;}// morris中序遍历public static <T> List<T> morrisInOrder(TreeNode<T> root) {List<T> res = new ArrayList<>();TreeNode<T> cur = root;while (cur != null) {// 如果没有左子树，则访问当前节点。并向右走一步if (cur.left == null) {res.add(cur.val);cur = cur.right;}// 有左子树else {// 找到cur的前驱节点preTreeNode<T> pre = cur.left;while (pre.right != null && pre.right != cur) {pre = pre.right;}// 第一次访问cur，则将pre右孩子指向cur。并向左走一步if (pre.right == null) {pre.right = cur;cur = cur.left;}// 第二次访问cur，则将pre右孩子指针恢复（设为null）。并向右走一步else {pre.right = null;res.add(cur.val);cur = cur.right;}}}return res;}// morris后序遍历public static <T> List<T> morrisPostOrder(TreeNode<T> root) {List<T> res = new ArrayList<>();TreeNode<T> cur = root;while (cur != null) {// 如果没有左子树，向右走一步if (cur.left == null) {cur = cur.right;}// 有左子树else {// 找到cur的前驱节点preTreeNode<T> pre = cur.left;while (pre.right != null && pre.right != cur) {pre = pre.right;}// 第一次访问cur，则将pre右孩子指向cur。并向左走一步if (pre.right == null) {pre.right = cur;cur = cur.left;}// 第二次访问cur，则将pre右孩子指针恢复（设为null）。并向右走一步else {pre.right = null;handle(cur.left, res);cur = cur.right;}}}handle(root, res);return res;}private static <T> void handle(TreeNode<T> node, List<T> res) {TreeNode<T> temp = reverse(node);TreeNode<T> cur = temp;while (cur != null) {res.add(cur.val);cur = cur.right;}reverse(temp);}// 反转以node开始的一系列节点，并返回反转后的起始节点private static <T> TreeNode<T> reverse(TreeNode<T> node) {TreeNode<T> prev = null, temp = null;// 思想和反转单链表一样while (node != null) {temp = node.right;node.right = prev;prev = node;node = temp;}return prev;}
}

package MyBinaryTree;import java.util.*;public class TestBinaryTree {public static void main(String[] args) {// 层序序列，空节点值为null。列表最后一个元素为树中层次遍历最后一个叶子节点的值List<Character> levelOrderList = new ArrayList<>(Arrays.asList('A', 'B', 'C', 'D', 'E', null, null, null, null, 'F'));TreeNode<Character> root = BiTreeUtils.createBiTreeByLevelOrder(levelOrderList);System.out.println("morris先序遍历：");System.out.println(BiTreeUtils.morrisPreOrder(root));System.out.println("morris中序遍历：");System.out.println(BiTreeUtils.morrisInOrder(root));System.out.println("morris后序遍历：");System.out.println(BiTreeUtils.morrisPostOrder(root));}
}

morris先序遍历：
[A, B, D, E, F, C]
morris中序遍历：
[D, B, F, E, A, C]
morris后序遍历：
[D, F, E, B, C, A]Process finished with exit code 0

注：mirros后序遍历也可以用如下代码实现，可以结合下图思考。
dot tree.dot | gvpr -c -f D:\workspace\toolbox\graphviz\binarytree.gvpr | neato -n -Tpng -o tree.png

digraph binaryTree{node[shape=circle,color=blue]edge[arrowhead=none]dummyRoot[color=red,shape=ellipse]dummyRoot->A[side=left]A->B[side=left]A->C[side=right]B->D[side=left]B->E[side=right]E->F[side=left]
}   

    // morris后序遍历public static <T> List<T> morrisPostOrder(TreeNode<T> root) {List<T> res = new ArrayList<>();TreeNode<T> dummyRoot = new TreeNode<>(null, root, null);TreeNode<T> cur = dummyRoot;while (cur != null) {// 如果没有左子树，向右走一步if (cur.left == null) {cur = cur.right;}// 有左子树else {// 找到cur的前驱节点preTreeNode<T> pre = cur.left;while (pre.right != null && pre.right != cur) {pre = pre.right;}// 第一次访问cur，则将pre右孩子指向cur。并向左走一步if (pre.right == null) {pre.right = cur;cur = cur.left;}// 第二次访问cur，则将pre右孩子指针恢复（设为null）。并向右走一步else {pre.right = null;handle(cur.left, res);cur = cur.right;}}}// handle(root, res);return res;}