二叉树及其遍历(Java)
你好，我是goldsunC
让我们一起进步吧！
什么是二叉树？
二叉树又称
knuth树，是一个由有限节点所组成的集合，此集合可以为空集合，或由一个树根及左右两个子树所组成。
为什么使用二叉树?
mn-(m-1)=m(n-1)+1，则n元树的链接浪费率为
。根据这个式子我们可以发现，当n=2时，树的链接浪费率最低为
，因此我们常常使用二叉树结构。
二叉树的节点数
二叉树的存储方式
数组表示法
A,B,C,D代表节点的值，其余的为空节点，它们的位置如图所示，那么如果让它们放进数组，应该是这样的：
| 索引 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| 值 | A | B | C | D |
小于父节点的值放在左子节点，大于父节点的值放在右子节点的规则，因此左子树的值一定全部小于树根，右子树的值一定大于树根。
public class arrayBinaryTree {
public static void main(String[] args) {
int i,level;
int[] data = {6,3,5,9,7,8,4,2}; // 原始数据
int btree[] = new int[16]; // 二叉树数组大小，长度16是因为使用后15个空间，让索引从1开始，比较好理解
for (i=0; i<16; i++)
btree[i] = 0;
System.out.println("原始数组内容：");
for (i=0;i<8;i++)
System.out.print("["+data[i]+"]");
System.out.println();
// 将原始数据添加入二叉树
for (i=0;i<8;i++) {
for (level=1;btree[level]!=0;) {
if (data[i]>btree[level])
level = level*2+1;
else
level = level*2;
}
btree[level] = data[i];
}
System.out.println("二叉树：");
for (i=1;i<16;i++)
System.out.print("["+btree[i]+"]");
}
}
OUT:
原始数组内容：
[6][3][5][9][7][8][4][2]
二叉树：
[6][3][9][2][5][7][0][0][0][4][0][0][8][0][0]
链表表示法
TreeNode和
BinaryTree类，其中前者代表二叉树中的一个节点，后者就代表一棵二叉树。
存放的数据、左子节点的指针和右子节点的指针。二叉树中应该实现一个方法即将数据插入到二叉树中。
/*
TreeNode 二叉树节点
*/
class TreeNode {
int value;
TreeNode leftNode,rightNode;
public TreeNode(int value) {
this.value = value;
leftNode = null;
rightNode = null;
}
}
/*
BinaryTree 二叉树
*/
class BinaryTree {
public TreeNode rootNode;
public BinaryTree(int[] data) {
for (int i=0;i<data.length;i++)
Add_Node_To_BinaryTree(data[i]);
}
/*
将节点加入二叉树中
*/
void Add_Node_To_BinaryTree(int value) {
TreeNode currentNode = rootNode;
// 如果根节点为空，先创建根节点
if (rootNode == null) {
rootNode = new TreeNode(value);
return;
}
// 循环寻找适合当前节点的位置
while (true) {
if (value<currentNode.value) {
if (currentNode.leftNode == null) {
currentNode.leftNode = new TreeNode(value);
return;
}
else currentNode = currentNode.leftNode;
}else {
if (currentNode.rightNode == null) {
currentNode.rightNode = new TreeNode(value);
return;
}else currentNode = currentNode.rightNode;
}
}
}
// 打印各个节点值(中序遍历，即结果从小到大排序)
void printTree(TreeNode node) {
if (node != null) {
printTree(node.leftNode);
System.out.print("["+node.value+"]");
printTree(node.rightNode);
}
}
}
public class LinkBinaryTree {
public static void main(String[] args) {
int[] content = {11, 13, 15, 17, 19, 28, 26, 24, 22, 20};
BinaryTree binarytree = new BinaryTree(content);
binarytree.printTree(binarytree.rootNode);
}
}
OUT:
[11][13][15][17][19][20][22][24][26][28]
中序遍历的方法打印出了二叉树存储的数据，可以看到数据是从小到大排列的。
二叉树遍历
ABC,ACB,BAC,BCA,CAB,CBA，不过既然二叉树满足
左子节点值小于父节点而右子节点值大于父节点关系，那么从左向右遍历和从右向左遍历得到的结果是类似的，只要将结果反转一下就一样了，因此我们可以规定遍历规则为
一律从左向右，那么就剩下三种遍历方式了：
BAC,ABC,BCA。
这三种遍历方式就是
-
中序遍历(BAC)：左子树->树根->右子树 -
前序遍历(ABC)：树根->左子树->右子树 -
后序遍历(BCA)：左子树->右子树->树根
ABDECF
DBEACF
DEBFCA
// 前序遍历
void PreprintTree(TreeNode node) {
if (node != null) {
System.out.print("["+node.value+"]");
PreprintTree(node.leftNode);
PreprintTree(node.rightNode);
}
}
// 中序遍历
void MidprintTree(TreeNode node) {
if (node != null) {
MidprintTree(node.leftNode);
System.out.print("["+node.value+"]");
MidprintTree(node.rightNode);
}
}
// 后序遍历
void PosprintTree(TreeNode node) {
if (node != null) {
PosprintTree(node.leftNode);
PosprintTree(node.rightNode);
System.out.print("["+node.value+"]");
}
}
• end •
走在路上
goldsunC