【数据结构】二叉树
发布时间：2021-03-30 22:12:58 所属栏目：安全 来源：网络整理
导读：前言 数据结构还是大二的时候学过的，当然由于是非计算机专业的学生，所以学的也不怎么样，去年用c++实现了最基本的数据结构，链表/栈/队列/二叉树，三月份看的时候还贴到了博客上。然而当时由于代码量不够，其实写的并不是很好，理解也太不到位。 最近在看
|
代码如下 public void preOrder() {
Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
visitAlongLeft(root,stack);
}
}
private void visitAlongLeft(BinaryTreeNode root,Stack<BinaryTreeNode> stack) {
while (root != null) {
System.out.print(root.data + " ");
if (root.rchild != null)
stack.push(root.rchild);
root = root.lchild;
}
}
3.中序非递归遍历 ? ? a.沿着节点的左分支走，并将其入栈，直到最左下? ? b.当栈不空时，每弹出一个，访问之，并对其右孩子执行a的操作 public void inOrder() {
Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
goAlongLeft(root,stack);
}
}
private void goAlongLeft(BinaryTreeNode root,Stack<BinaryTreeNode> stack) {
while (root != null) {
stack.push(root);
root = root.lchild;
}
}
注：两个辅助函数的命名一个是visitAlongLeft一个是goAlongLeft也能看出来他们的区别。 这里巧妙地使用了两个栈,采用和先序遍历一样的思路
代码如下 private void goAlongRight(BinaryTreeNode root,Stack<BinaryTreeNode> stack2) {
while (root != null) {
stack2.push(root); // 访问
if (root.lchild != null)
stack1.push(root.lchild);
root = root.rchild;
}
}
public void postOrder() {
Stack<BinaryTreeNode> myStack1 = new Stack<BinaryTreeNode>();
Stack<BinaryTreeNode> myStack2 = new Stack<BinaryTreeNode>();
goAlongRight(root,myStack2);
}
while (myStack2.size() > 0) {
BinaryTreeNode node = myStack2.poll();
System.out.print(node.data + " ");
}
}
5.中序非递归遍历和先序思路类似，层序非递归遍历比较简单在此不再解释 6.创建二叉树 先序递归遍历同时也提供了一种创建二叉树的方法，大致思路是首先创建树根，然后递归创建左子树再递归创建右子树。 （编辑：好传媒网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
