我要评论二叉树(binary tree)是一颗树，其中每个节点都不能有多于两个的儿子。
1.二叉树节点
作为图的特殊形式，二叉树的基本组成单元是节点与边；作为数据结构，其基本的组成实体是二叉树节点（binary tree node），而边则对应于节点之间的相互引用。
如下，给出了二叉树节点的数据结构图示和相关代码：
// 定义节点类：
private static class binnode {
private object element;
private binnode lchild;// 定义指向左子树的指针
private binnode rchild;// 定义指向右子树的指针
public binnode(object element, binnode lchild, binnode rchild) {
this.element = element;
this.lchild = lchild;
this.rchild = rchild;
}
}
2.递归遍历
二叉树本身并不具有天然的全局次序，故为实现遍历，需通过在各节点与其孩子之间约定某种局部次序，间接地定义某种全局次序。
按惯例左兄弟优先于右兄弟，故若将节点及其孩子分别记作v、l和r，则下图所示，局部访问的次序可有vlr、lvr和lrv三种选择。根据节点v在其中的访问次序，三种策略也相应地分别称作先序遍历、中序遍历和后序遍历，下面将分别介绍。
2.1 先序遍历
图示：
代码实现：
/**
* 对该二叉树进行前序遍历 结果存储到list中 前序遍历
*/
public static void preorder(binnode node) {
list.add(node); // 先将根节点存入list
// 如果左子树不为空继续往左找，在递归调用方法的时候一直会将子树的根存入list，这就做到了先遍历根节点
if (node.lchild != null) {
preorder(node.lchild);
}
// 无论走到哪一层，只要当前节点左子树为空，那么就可以在右子树上遍历，保证了根左右的遍历顺序
if (node.rchild != null) {
preorder(node.rchild);
}
}
2.2 中序遍历
图示：
代码实现：
/**
* 对该二叉树进行中序遍历 结果存储到list中
*/
public static void inorder(binnode node) {
if (node.lchild != null) {
inorder(node.lchild);
}
list.add(node);
if (node.rchild != null) {
inorder(node.rchild);
}
}
2.3 后序遍历
实例图示：
代码实现：
/**
* 对该二叉树进行后序遍历 结果存储到list中
*/
public static void postorder(binnode node) {
if (node.lchild != null) {
postorder(node.lchild);
}
if (node.rchild != null) {
postorder(node.rchild);
}
list.add(node);
}
附：测试相关代码
private static binnode root;
private static list<binnode> list = new arraylist<binnode>();
public static void main(string[] args) {
init();
// todo auto-generated method stub
//preorder(root);
//inorder(root);
postorder(root);
for (int i = 0; i < list.size(); i++) {
system.out.print(list.get(i).element + " ");
}
}
// 树的初始化:先从叶节点开始,由叶到根
public static void init() {
binnode b = new binnode("b", null, null);
binnode a = new binnode("a", null, b);
binnode c = new binnode("c", a, null);
binnode e = new binnode("e", null, null);
binnode g = new binnode("g", null, null);
binnode f = new binnode("f", e, g);
binnode h = new binnode("h", f, null);
binnode d = new binnode("d", c, h);
binnode j = new binnode("j", null, null);
binnode k = new binnode("k", j, null);
binnode m = new binnode("m", null, null);
binnode o = new binnode("o", null, null);
binnode p = new binnode("p", o, null);
binnode n = new binnode("n", m, p);
binnode l = new binnode("l", k, n);
root = new binnode("i", d, l);
}
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持移动技术网。
您可能感兴趣的文章:
如您对本文有疑问或者有任何想说的，请 点击进行留言回复，万千网友为您解惑！
网友评论