【数据结构】二叉树
发布时间：2021-03-31 13:07:01 所属栏目：安全 来源：网络整理
导读：副标题#e# 前言 数据结构还是大二的时候学过的，当然由于是非计算机专业的学生，所以学的也不怎么样，去年用c++实现了最基本的数据结构，链表/栈/队列/二叉树，三月份看的时候还贴到了博客上。然而当时由于代码量不够，其实写的并不是很好，理解也太不到位
|
副标题[/!--empirenews.page--]
前言数据结构还是大二的时候学过的，当然由于是非计算机专业的学生，所以学的也不怎么样，去年用c++实现了最基本的数据结构，链表/栈/队列/二叉树，三月份看的时候还贴到了博客上。然而当时由于代码量不够，其实写的并不是很好，理解也太不到位。 最近在看算法导论，当然最基本的就是数据结构，于是打算将基本的知识在回顾一下。 我是一个疯狂的人，一旦决定做一件事，就会全天埋头去干，因为总有一种恨不得赶快学完的感觉。前几天我连续写了好几篇博客，讲解一些排序算法，其实在这个过程中，我深深的发现： 书上的伪代码/算法思路能看懂不一定能用代码轻松地实现，因为有很多小细节需要注意。能把代码写出来不一定能给别人讲清楚，就如这里的树的后序非递归遍历算法，我大致感觉和先序非递归有很大相似，但想讲清楚还是想了好久的。 写博客记录自己的学习笔记其实就是一个强迫自己把学到的知识不仅仅停留在会的层次上而是上升到理解的高度的过程。 二叉树?每个节点之多有两棵子树，并且两棵子树有顺序之分，不能颠倒。二叉树的性质： 1.第i层至多有2^(i-1)个结点 2.深度为K的二叉树，至多有2^k-1个结点 3.任何一棵二叉树，叶子结点数目n0=度为2的结点数目n2 + 1 ? ? n=n0+n1+n2 ? ? n=B+1=n1+2*n2+1 ? ? 于是n0=n2+1 4.n个结点的完全二叉树深度为(lgn下取整)+1 二叉树的实现下面主要讲二叉树的链式存储结点数据结构，BinaryTreeNode类描述每个结点 public class BinaryTreeNode {
public int data;
public BinaryTreeNode lchild;
public BinaryTreeNode rchild;
public BinaryTreeNode parent;
public BinaryTreeNode(int data) {
this.data = data;
this.lchild = null;
this.rchild = null;
this.parent = null;
}
}
BinaryTree类
public class BinaryTree {
public BinaryTreeNode root;
// 从数组递归创建二叉树时用来作为数组下标
private int index = 0;
/**
* 通过数组作为输入的一棵先序遍历的树节来创建二叉树
* @param array
*/
public void createTree(int[] array) {
index = 0;
root = createPreOrder(array,root);
}
private BinaryTreeNode createPreOrder(int[] a,BinaryTreeNode root) {
if (a[index] == 0 || index > a.length - 1) {
index++;
root = null;
} else {
root = new BinaryTreeNode(a[index]);
index++;
root.lchild = createPreOrder(a,root.lchild);
if (root.lchild != null)
root.lchild.parent = root; // 双亲节点主要用在寻找前驱和后继
root.rchild = createPreOrder(a,root.rchild);
if (root.rchild != null)
root.rchild.parent = root; // 双亲节点主要用在寻找前驱和后继
}
return root;
}
/**
* 通过键盘输入一棵先序遍历的树节点创建二叉树
*/
public void createTree() {
Scanner in = new Scanner(System.in);
root = createPreOrder(in,root);
}
private BinaryTreeNode createPreOrder(Scanner in,BinaryTreeNode root) {
int a = in.nextInt();
if (a == 0) {
return null;
} else {
root = new BinaryTreeNode(a);
root.lchild = createPreOrder(in,root.lchild);
if (root.lchild != null)
root.lchild.parent = root; // 双亲节点主要用在寻找前驱和后继
root.rchild = createPreOrder(in,root.rchild);
if (root.rchild != null)
root.rchild.parent = root; // 双亲节点主要用在寻找前驱和后继
return root;
}
}
/**
* 先序递归遍历
*/
public void preOrder(BinaryTreeNode root) {
if (root != null) {
System.out.print(root.data + " ");
preOrder(root.lchild);
preOrder(root.rchild);
}
}
/**
* 先序非递归遍历
*/
public void preOrder() {
Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
visitAlongLeft(root,stack);
while (stack.size() > 0) {
BinaryTreeNode node = stack.poll();
visitAlongLeft(node,stack);
}
}
/**
* 沿着某个给定结点root的左分支访问，同时将有孩子入栈
* @param root
* @param 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;
}
}
/**
* 中序递归遍历
* @param root
*/
public void inOrder(BinaryTreeNode root) {
if (root != null) {
inOrder(root.lchild);
System.out.print(root.data + " ");
inOrder(root.rchild);
}
}
/**
* 中序非递归遍历
*/
public void inOrder() {
Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
goAlongLeft(root,stack);
while (stack.size() > 0) {
BinaryTreeNode node = stack.poll();
System.out.print(node.data + " ");
goAlongLeft(node.rchild,stack);
}
}
/**
* 沿着某个给定结点root的左分支入栈
* @param root
* @param stack
*/
private void goAlongLeft(BinaryTreeNode root,Stack<BinaryTreeNode> stack) {
while (root != null) {
stack.push(root);
root = root.lchild;
}
}
/**
* 后序递归遍历
* @param root
*/
public void postOrder(BinaryTreeNode root) {
if (root != null) {
postOrder(root.lchild);
postOrder(root.rchild);
System.out.print(root.data + " ");
}
}
// stack2 用来访问
private void goAlongRight(BinaryTreeNode root,Stack<BinaryTreeNode> stack1,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,myStack1,myStack2);
while (myStack1.size() > 0) {
BinaryTreeNode node = myStack1.poll();
goAlongRight(node,myStack2);
}
while (myStack2.size() > 0) {
BinaryTreeNode node = myStack2.poll();
System.out.print(node.data + " ");
}
}
/**
* 层序遍历
*/
public void levelOrder() {
Queue<BinaryTreeNode> queue = new Queue<BinaryTreeNode>();
if (root != null) {
queue.offer(root);
}
while (!queue.isEmpty()) {
BinaryTreeNode node = queue.poll();
System.out.print(node.data + " ");
if (node.lchild != null)
queue.offer(node.lchild);
if (node.rchild != null)
queue.offer(node.rchild);
}
}
/**
* 层序打印，每层用还行区分
*/
public void levelOrderH()
{
if (root == null) return;
Queue<BinaryTreeNode> current = new Queue<BinaryTreeNode>();
Queue<BinaryTreeNode> next = new Queue<BinaryTreeNode>();
current.offer(root);
while (current.size() > 0) {
BinaryTreeNode node = current.poll();
if (node!=null) {
System.out.print(node.data + " ");
next.offer(node.lchild);
next.offer(node.rchild);
}
if (current.size() == 0) {
System.out.println("");
asign(current,next);
}
}
}
// 将next行的元素给current行
private void asign(Queue<BinaryTreeNode> current,Queue<BinaryTreeNode> next) {
while (next.size() > 0) {
current.offer(next.poll());
}
}
public static void main(String[] args) {
BinaryTree tree = new BinaryTree();
int[] array = {1,2,4,7,5,3,6,8,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.先序非递归遍历 ? ? a.先沿着结点的左分支依次访问，访问时，顺便将其右孩子入栈? ? b.当栈不空时，每弹出一个，重复1 （编辑：宁德站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
站长推荐