二叉树的定义
二叉树(binary tree)是结点的有限集合，这个集合或者空，或者由一个根及两个互不相交的称为这个根的左子树或右子树构成.
从定义可以看出，二叉树包括：1.空树 2.只有一个根节点 3.只有左子树 4.只有右子树 5.左右子树都存在 有且仅有这5中表现形式
二叉树与一般树的区别
一般树的子树不分次序，而二叉树的子树有左右之分.
由于二叉树也是树的一种，所以大部分的树的概念，对二叉树也适用.
二叉树的存贮：每个节点只需要两个指针域（左节点，右节点）,有的为了操作方便也会 增加指向父级节点的指针，除了指针域以外，还会有一个数据域用来保存当前节点的信息
二叉树的特点：
性质1：在二叉树的第i层上至多有2^(i-1)个节点(i >= 1)
性质2：深度为k的二叉树至多有2^(k-1)个节点(k >=1)
性质3：对于任意一棵二叉树T而言，其叶子节点数目为N0,度为2的节点数目为N2，则有N0 = N2 + 1。
性质4：具有n个节点的完全二叉树的深度 。
二叉树的遍历
二叉树的遍历分为三种：前序遍历 中序遍历 后序遍历
前序遍历：按照“根左右”,先遍历根节点，再遍历左子树 ，再遍历右子树
中序遍历：按照“左根右“,先遍历左子树，再遍历根节点，最后遍历右子树
后续遍历：按照“左右根”，先遍历左子树，再遍历右子树，最后遍历根节点
其中前，后，中指的是每次遍历时候的根节点被遍历的顺序
二叉树遍历：
前根左右
中左根右
后左右根
==================================================================
二叉树遍历的java实现
package 树;
import java.util.ArrayList;
import java.util.List;
public class Tree {
private Node root;
private List<Node> list=new ArrayList<Node>();
public Tree(){
init();
}
//树的初始化:先从叶节点开始,由叶到根
public void init(){
Node x=new Node("X",null,null);
Node y=new Node("Y",null,null);
Node d=new Node("d",x,y);
Node e=new Node("e",null,null);
Node f=new Node("f",null,null);
Node c=new Node("c",e,f);
Node b=new Node("b",d,null);
Node a=new Node("a",b,c);
root =a;
}
//定义节点类：
private class Node{
private String data;
private Node lchid;//定义指向左子树的指针
private Node rchild;//定义指向右子树的指针
public Node(String data,Node lchild,Node rchild){
this.data=data;
this.lchid=lchild;
this.rchild=rchild;
}
}
/**
* 对该二叉树进行前序遍历 结果存储到list中 前序遍历:ABDXYCEF
*/
public void preOrder(Node node)
{
list.add(node); //先将根节点存入list
//如果左子树不为空继续往左找，在递归调用方法的时候一直会将子树的根存入list，这就做到了先遍历根节点
if(node.lchid != null)
{
preOrder(node.lchid);
}
//无论走到哪一层，只要当前节点左子树为空，那么就可以在右子树上遍历，保证了根左右的遍历顺序
if(node.rchild != null)
{
preOrder(node.rchild);
}
}
/**
* 对该二叉树进行中序遍历 结果存储到list中，中序结果XdYbaecf
*/
public void inOrder(Node node)
{
if(node.lchid!=null){
inOrder(node.lchid);
}
list.add(node);
if(node.rchild!=null){
inOrder(node.rchild);
}
}
/**
* 对该二叉树进行后序遍历 结果存储到list中，后续结果：XYdbefca
*/
public void postOrder(Node node)
{
if(node.lchid!=null){
postOrder(node.lchid);
}
if(node.rchild!=null){
postOrder(node.rchild);
}
list.add(node);
}
/**
* 返回当前数的深度
* 说明:
* 1、如果一棵树只有一个结点，它的深度为1。
* 2、如果根结点只有左子树而没有右子树，那么树的深度是其左子树的深度加1；
* 3、如果根结点只有右子树而没有左子树，那么树的深度应该是其右子树的深度加1；
* 4、如果既有右子树又有左子树，那该树的深度就是其左、右子树深度的较大值再加1。
*
* @return
*/
public int getTreeDepth(Node node) {
if(node.lchid == null && node.rchild == null)
{
return 1;
}
int left=0,right = 0;
if(node.lchid!=null)
{
left = getTreeDepth(node.lchid);
}
if(node.rchild!=null)
{
right = getTreeDepth(node.rchild);
}
return left>right?left+1:right+1;
}
//得到遍历结果
public List<Node> getResult()
{
return list;
}
public static void main(String[] args) {
Tree tree=new Tree();
System.out.println("根节点是:"+tree.root);
//tree.preOrder(tree.root);
tree.postOrder(tree.root);
for(Node node:tree.getResult()){
System.out.println(node.data);
}
System.out.println("树的深度是"+tree.getTreeDepth(tree.root));
}
}
另一种写法：
本文只介绍二叉树的构造和遍历。
构造一个二叉树的节点：
public class BinaryTreeNode<T> {
public T data;
public BinaryTreeNode leftChild, rightChild;
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
public BinaryTreeNode getLeftChild() {
return leftChild;
}
public void setLeftChild(BinaryTreeNode leftChild) {
this.leftChild = leftChild;
}
public BinaryTreeNode getRightChild() {
return rightChild;
}
public void setRightChild(BinaryTreeNode rightChild) {
this.rightChild = rightChild;
}
}
构造树：
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Stack;
public class BinaryTree<T> {
BinaryTreeNode<T> root;
public BinaryTree(){
}
/**
* 二叉树的创建
* @param list
*/
public void createBiTree(List<T> list){
Iterator<T> iterator = list.iterator();
while(iterator.hasNext()){
BinaryTreeNode<T> node = new BinaryTreeNode<T>();
node.setData(iterator.next());
insertTree(node);
}
}
/**
* 插入时，从根节点开始判断它是否有Child，如果没有，则将节点的孩子
* 指向为传入参数的引用
*
* @param node
*/
public void insertTree(BinaryTreeNode<T> node) {
if (root == null) {
root = node;
} else {
BinaryTreeNode<T> current = root;
while (true) {//循环用于左右节点都有时，遍历下级节点
if (current.leftChild == null) {
current.leftChild = node;
//跳出循环
return;
} else if (root.rightChild == null) {
current.rightChild = node;
return;
} else {
current = current.leftChild;
}
}
}
}
/**
* 先序递归遍历-按照root，left子树和right子树顺序遍历
*
*/
public void preOrderTraverse(BinaryTreeNode node){
System.out.println(node.getData());
if(node.getLeftChild()!=null){
preOrderTraverse(node.getLeftChild());
}
if(node.getRightChild()!=null){
preOrderTraverse(node.getRightChild());
}
}
/**
* 先序循环遍历-按照root，left子树和right子树顺序遍历
*
*/
public void preOrderTraverseLoop(BinaryTreeNode node){
//System.out.println(node.getData());
Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
stack.push(node);
while(!stack.isEmpty()){
BinaryTreeNode biNode = stack.pop();
System.out.println(biNode.getData());
BinaryTreeNode left = biNode.leftChild;
if(left!=null){
stack.push(left);
}
BinaryTreeNode right = biNode.rightChild;
if(right!=null){
stack.push(right);
}
}
}
public static void main(String[] args) {
Integer[] ints = new Integer[]{1,3,9,8,7,6,2,98,76};
List list = new ArrayList<Integer>(ints.length);
for (int i = 0; i < ints.length; i++) {
list.add(ints[i]);
}
BinaryTree<Integer> binaryTree = new BinaryTree<Integer>();
binaryTree.createBiTree(list);
binaryTree.preOrderTraverse(binaryTree.root);
System.out.println("=========================");
binaryTree.preOrderTraverseLoop(binaryTree.root);
}
}
我的总结:
二叉树是一个相当重要的数据结构，它的应用面非常广，并且由他改进生成了很多重要的树类数据结构，如红黑树，堆等，应用价值之高后面深入学习便有体会，因此，掌握它的基本特征和遍历方式实现是学好后续数据结构的基础，理论方面其实我们看到二叉树的形状，我们自己画图都能总结出来，但是代码实现这一块，初学者不是很好理解，树的遍历利用了递归的思想，递归的思想本质无非就是循环，方法调方法，所以，理解二叉树遍历的代码实现最好的方式就是按照它的遍历思想自己画出图来一步一步的遍历一遍，先把这个遍历过程想明白了，然后再根据递归的思想，什么时候调什么样的方法，自然就能很容易想明白了
相关推荐
java编程，二叉树的中序遍历，递归实现
二叉树，一个基于Java实现的二叉树学习项目。包含二叉树生成、遍历。适用人群：计算机，电子信息工程、数学等专业的大学生学习二叉树等数据结构，作为“参考资料”使用。 二叉树，一个基于Java实现的二叉树学习项目...
完全二叉树的层序遍历-labview完全二叉树的层序遍历-labview完全二叉树的层序遍历-labview完全二叉树的层序遍历-labview完全二叉树的层序遍历-labview完全二叉树的层序遍历-labview完全二叉树的层序遍历-labview完全...
除了代码实现，课程设计文档可能包含了二叉树的概念解释、层序遍历的算法描述、以及如何使用Java语言实现这一算法的详细步骤。同时，`课程设计.doc`可能包含项目报告，详细阐述了设计目的、实现方法、遇到的问题及...
对于数据结构，二叉树的实现的了解。通过java实现，包括了建立，查找，遍历，比较的功能。
二叉树遍历是访问二叉树中所有节点的过程，通常有三种主要方法：前序遍历、中序遍历和后序遍历。这些遍历方式对于理解和操作二叉树数据结构至关重要。 1. **前序遍历**（Preorder Traversal）： - 访问根节点。 -...
中序遍历是二叉树遍历的一种方法，它按照“左-根-右”的顺序访问树中的所有节点，对于理解树的性质和执行某些操作非常有用。本课程设计将详细介绍如何使用Java编程语言实现二叉树的中序遍历。 首先，我们先构建...
在计算机科学中，二叉树是一种常见的...对于实际的编程实现，你需要根据提供的代码和数据进行调整，确保逻辑正确，并遵循二叉树遍历的规则。在进行这类问题的解决时，理解和熟悉二叉树的性质以及各种遍历方法至关重要。
详细介绍了JAVA中二叉树的非递归遍历方式，三种方式都是采用栈来辅助完成，其中前序遍历采用的是先入右子节点再入左子节点的方法，这样弹出栈时左在前，右在后。中序遍历的话则是要先一直到达最左的子节点，然后才弹...
在计算机科学中，二叉树遍历是访问树中所有节点的一种基本操作，通常有三种主要的遍历方式：前序遍历、中序遍历和后序遍历。这些遍历方法在数据结构和算法领域中有着广泛的应用，特别是在编译器设计、搜索算法和数据...
主要有三种遍历方式：前序遍历、中序遍历和后序遍历。 1. 前序遍历：根节点 -> 左子树 -> 右子树 2. 中序遍历：左子树 -> 根节点 -> 右子树 3. 后序遍历：左子树 -> 右子树 -> 根节点 递归遍历是实现这三种遍历的...
java实现二叉树非递归前序中序后序遍历
后序遍历是三种基本的二叉树遍历方法之一，另外两种为前序遍历和中序遍历。后序遍历的基本思想是从根节点出发，首先遍历左子树，然后遍历右子树，最后访问根节点。 #### 二、后序遍历算法原理 **1. 递归实现** ...
二叉树遍历是一种访问二叉树所有节点的方法，通常分为三种主要类型：先序遍历、中序遍历和后序遍历。在Java编程语言中，我们可以使用递归或迭代的方式来实现这些遍历方法。 **先序遍历**（根-左-右）是最常见的遍历...
在提供的"二叉树的递归和非递归遍历"压缩包文件中，可能包含了Java源代码，演示了如何实现这两种遍历方式。通过阅读和理解这些代码，你可以更好地掌握二叉树遍历的原理和实践，这对于理解和解决涉及二叉树的算法问题...
因此，满二叉树的前序遍历、中序遍历和后序遍历均可以通过递归方式实现。 以前序遍历为例，满二叉树的前序遍历顺序为：根、左、右。 在具体实现过程中，我们可以通过构造一个满二叉树，然后进行前序遍历来获取遍历...
在Java编程中，二叉树是一种常见的数据结构，它由节点组成，每个节点都有一个值，并且可以有至多两个子节点，分别称为左子节点和右子节点。本篇文章将详细探讨如何实现二叉树的层次遍历，即按照从根节点到叶子节点的...
接下来，我们将详细探讨这三种遍历方式以及它们的实现。 1. 前序遍历（Preorder Traversal） 前序遍历的顺序是：根节点 -> 左子树 -> 右子树。首先访问根节点，然后递归地遍历左子树，最后遍历右子树。在非递归实现...