【数据结构】二叉树
发布时间：2021-03-31 13:07:01 所属栏目：安全 来源：网络整理
导读：副标题#e# 前言 数据结构还是大二的时候学过的，当然由于是非计算机专业的学生，所以学的也不怎么样，去年用c++实现了最基本的数据结构，链表/栈/队列/二叉树，三月份看的时候还贴到了博客上。然而当时由于代码量不够，其实写的并不是很好，理解也太不到位
|
需要注意的是我在每个结点还保存了父节点，因此在创建的时候要给每个结点的父亲指针赋值。以从键盘输入一棵先序遍历树来创建二叉树为例，代码如下 public void createTree() {
Scanner in = new Scanner(System.in);
root = createPreOrder(in,root);
}
private BinaryTreeNode createPreOrder(Scanner in,root.rchild);
if (root.rchild != null)
root.rchild.parent = root; // 双亲节点主要用在寻找前驱和后继
return root;
}
}
这里我再一次深深的厌恶java不能像C++里面那样有&引用传递或者传递指针(类比这里应该就是传递二级指针)，导致无法在函数里面改变"引用"的值，而必须通过函数的返回值。所以看起来没有C++写的紧凑。
注：代码里面使用到的Stack是自己封装的，所以可能会与jdk中的有所差别。 测试使用封装的BinaryTree类进行测试 public static void main(String[] args) {
BinaryTree tree = new BinaryTree();
int[] array = {1,0};
tree.createTree(array);
System.out.println("先序递归遍历");
tree.preOrder(tree.root);
System.out.println("n中序递归遍历");
tree.inOrder(tree.root);
System.out.println("n后序递归遍历");
tree.postOrder(tree.root);
System.out.println("n先序非递归遍历");
tree.preOrder();
System.out.println("n中序非递归遍历");
tree.inOrder();
System.out.println("n后序非递归遍历");
tree.postOrder();
System.out.println("n层序遍历");
tree.levelOrder();
System.out.println("n层序遍历，每层换行");
tree.levelOrderH();
}
打印结果：
先序递归遍历 1 2 4 7 5 3 6 8 中序递归遍历 4 7 2 5 1 8 6 3 后序递归遍历 7 4 5 2 8 6 3 1 先序非递归遍历 1 2 4 7 5 3 6 8 中序非递归遍历 4 7 2 5 1 8 6 3 后序非递归遍历 7 4 5 2 8 6 3 1 层序遍历 1 2 3 4 5 6 7 8 层序遍历 1 2 3 4 5 6 7 8 add at 2015年11月13日22:25:42 经过网友Gun计划的提醒我添加了一个层序遍历的方法命名为levelOrderH，H意为Human，更人性化一点。每层打印完后换行，采用两个队列，很巧妙地实现，以前做过，所以很快能做出来哈哈。还可以加一个标记行结束也可以实现。 （编辑：宁德站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
站长推荐