一、几种遍历方法
深度遍历：
- 先序遍历二叉树的操作定义为:
若二叉树为空,则空操作;否则
(1)访问根结点；
(2)先序遍历左子树；
(3)先序遍历右子树。 - 中序遍历二叉树的操作定义为:
若三叉树为空,则空操作;否则
(1)中序遍历左子树；
(2)访问根结点；
(3)中序遍历右子树。 - 后序遍历二叉树的操作定义为
若二叉树为空,则空操作;否则
(1)后序遍历左子树；
(2)后序遍历右子树；
(3)访问根结点。
广度遍历：
- 层次遍历
(1)严格的从左至右
(2)从上到下
二、例子
- 先序遍历：1 2 4 3 5
- 中序遍历：4 2 1 3 5
- 后序遍历：4 2 5 3 1
- 层次遍历：1 2 3 4 5
二、代码实现（C语言，数据结构）
- 先序遍历
// 先序遍历
void PreorderTraversal(BiTree T) {
if(T) {
printf("%d ",T->data);
PreorderTraversal(T->lchild);
PreorderTraversal(T->rchild);
}
}
- 中序遍历
// 中序遍历
void InorderTraversal(BiTree T) {
if(T) {
InorderTraversal(T->lchild);
printf("%d ",T->data);
InorderTraversal(T->rchild);
}
}
- 后序遍历
// 后序遍历
void PostorderTraversal(BiTree T) {
if(T) {
PostorderTraversal(T->lchild);
PostorderTraversal(T->rchild);
printf("%d ",T->data);
}
}
- 层次遍历
// 层次遍历
void LevelorderTraversal(BiTree T) {
if(T) {
// 不用队列，只能取数组了
BiTree B[100];
// 根节点第一个
B[0] = T;
// 巧妙之处
int first = 0;
int after = 1;
// 循环
while(first < after) {
printf("%d ",B[first]->data);
if(B[first]->lchild) {
B[after] = B[first]->lchild;
after++;
} // of if for lchild
if(B[first]->rchild) {
B[after] = B[first]->rchild;
after++;
} // of if for rchild
first++;
} // end while
} // end if
} // end LevelorderTraversal
- 二叉树的存储
typedef int TElemType;
// 二叉树的二叉链表存储表示
typedef struct BiTNode {
TElemType data;
struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
void CreatBiTree(BiTree &T) {
//
T = (BiTree)malloc(sizeof(BiTNode));
//
TElemType data;
scanf("%d",&data);
if(data == -1) T = NULL;
if(T) {
T->data = data;
printf("输入%d节点的左子节点：n",data);
CreatBiTree(T->lchild);
printf("输入%d节点的右子节点：n",data);
CreatBiTree(T->rchild);
} // end if
} // end CreatBiTree
- C语言完整代码
#include#include typedef int TElemType; // 二叉树的二叉链表存储表示 typedef struct BiTNode { TElemType data; struct BiTNode *lchild, *rchild; }BiTNode, *BiTree; void CreatBiTree(BiTree &T) { // T = (BiTree)malloc(sizeof(BiTNode)); // TElemType data; scanf("%d",&data); if(data == -1) T = NULL; if(T) { T->data = data; printf("输入%d节点的左子节点：n",data); CreatBiTree(T->lchild); printf("输入%d节点的右子节点：n",data); CreatBiTree(T->rchild); } // end if } // end CreatBiTree // 先序遍历 void PreorderTraversal(BiTree T) { if(T) { printf("%d ",T->data); PreorderTraversal(T->lchild); PreorderTraversal(T->rchild); } } // 中序遍历 void InorderTraversal(BiTree T) { if(T) { InorderTraversal(T->lchild); printf("%d ",T->data); InorderTraversal(T->rchild); } } // 后序遍历 void PostorderTraversal(BiTree T) { if(T) { PostorderTraversal(T->lchild); PostorderTraversal(T->rchild); printf("%d ",T->data); } } // 层次遍历 void LevelorderTraversal(BiTree T) { if(T) { // 不用队列，只能取数组了 BiTree B[100]; // 根节点第一个 B[0] = T; // 巧妙之处 int first = 0; int after = 1; // 循环 while(first < after) { printf("%d ",B[first]->data); if(B[first]->lchild) { B[after] = B[first]->lchild; after++; } // of if for lchild if(B[first]->rchild) { B[after] = B[first]->rchild; after++; } // of if for rchild first++; } // end while } // end if } // end LevelorderTraversal int main(void) { printf("输入根节点：n"); BiTree T; CreatBiTree(T); printf("先序遍历："); PreorderTraversal(T); printf("n"); printf("中序遍历："); InorderTraversal(T); printf("n"); printf("后序遍历："); PostorderTraversal(T); printf("n"); printf("层次遍历："); LevelorderTraversal(T); printf("n"); return 0; }
- 效果图
三、代码实现（Java）
有点难，感觉。先想一下
- 先序遍历
public void PreorderTraversal() {
System.out.print(data + " ");
if(lchild != null) {
lchild.PreorderTraversal();
}
if(rchild != null) {
rchild.PreorderTraversal();
}
}
- 中序遍历
public void InorderTraversal() {
if(lchild != null) {
lchild.InorderTraversal();
}
System.out.print(data + " ");
if(rchild != null) {
rchild.InorderTraversal();
}
}
- 后序遍历
public void PostorderTraversal() {
if(lchild != null) {
lchild.PostorderTraversal();
}
if(rchild != null) {
rchild.PostorderTraversal();
}
System.out.print(data + " ");
}
- 层次遍历
public static void LevelorderTraversal(BiTree T) {
if(T != null) {
// 不用队列，只能取数组了
BiTree[] B = new BiTree[100];
// 根节点第一个
B[0] = T;
// 巧妙之处
int first = 0;
int after = 1;
// 循环
while(first < after) {
System.out.printf("%d ",B[first].data);
if(B[first].lchild != null) {
B[after] = B[first].lchild;
after++;
} // of lchild
if(B[first].rchild != null) {
B[after] = B[first].rchild;
after++;
} // of rchild
first++;
} // end while
} // end if
} // end LevelorderTraversal
- 比较简单的二叉树存储
public BiTree CreatBiTree() {
// 创建根节点
BiTree T = new BiTree(1);
// 创建树枝，值域
BiTree T_l = new BiTree(2);
BiTree T_r = new BiTree(3);
BiTree T_l_l = new BiTree(4);
BiTree T_r_r = new BiTree(5);
// 指针域
T.lchild = T_l;
T.rchild = T_r;
T_l.lchild = T_l_l;
T_r.lchild = T_r_r;
return T;
}
- 源码：
//package pta;
public class BiTree {
int data;
BiTree lchild;
BiTree rchild;
BiTree() {}
BiTree(int elem) {
data = elem;
lchild = null;
rchild = null;
}
public BiTree CreatBiTree() {
// 创建根节点
BiTree T = new BiTree(1);
// 创建树枝，值域
BiTree T_l = new BiTree(2);
BiTree T_r = new BiTree(3);
BiTree T_l_l = new BiTree(4);
BiTree T_r_r = new BiTree(5);
// 指针域
T.lchild = T_l;
T.rchild = T_r;
T_l.lchild = T_l_l;
T_r.lchild = T_r_r;
return T;
}
public void PreorderTraversal() {
System.out.print(data + " ");
if(lchild != null) {
lchild.PreorderTraversal();
}
if(rchild != null) {
rchild.PreorderTraversal();
}
}
public void InorderTraversal() {
if(lchild != null) {
lchild.InorderTraversal();
}
System.out.print(data + " ");
if(rchild != null) {
rchild.InorderTraversal();
}
}
public void PostorderTraversal() {
if(lchild != null) {
lchild.PostorderTraversal();
}
if(rchild != null) {
rchild.PostorderTraversal();
}
System.out.print(data + " ");
}
public static void LevelorderTraversal(BiTree T) {
if(T != null) {
// 不用队列，只能取数组了
BiTree[] B = new BiTree[100];
// 根节点第一个
B[0] = T;
// 巧妙之处
int first = 0;
int after = 1;
// 循环
while(first < after) {
System.out.printf("%d ",B[first].data);
if(B[first].lchild != null) {
B[after] = B[first].lchild;
after++;
} // of lchild
if(B[first].rchild != null) {
B[after] = B[first].rchild;
after++;
} // of rchild
first++;
} // end while
} // end if
} // end LevelorderTraversal
public static void main(String[] args) {
BiTree BT = new BiTree();
System.out.print("先序遍历：");
BT.CreatBiTree().PreorderTraversal();
System.out.println();
System.out.print("中序遍历：");
BT.CreatBiTree().InorderTraversal();
System.out.println();
System.out.print("后序遍历：");
BT.CreatBiTree().PostorderTraversal();
System.out.println();
System.out.print("层次遍历：");
LevelorderTraversal(BT.CreatBiTree());
System.out.println();
}
}
- 效果图：
