`

二叉树-树的构造和遍历

阅读更多

树型结构是一类重要的非线性数据结构。其中以树和二叉树最为常用,直观看来,树是以分支关系定义的层次结构。树结构在客观世界中广泛存在,树在计算机领域中也有广泛的应用,如在编译程序中,可用树来表示源程序的语法结构。

 

树作为非常基础的数据结构,有必要了解它的基本原理和使用场合,复习二叉树的数据结构,要分几个部分循序渐进地进行,这篇博客只涉及二叉树的构造和遍历。

 

首先类用于表示树的一个节点:

 

package algorithm.binarytree;
/**
 * <p>Description: Test</p>
 * <p>Copyright (c) 2010</p>
 * <p>Department: </p>
 * <p>Company: </p>
 * <p>Project:Test</p>
 *
 * @author Tomy Zhou
 * @since 1.0
 * @version algorithm.binarytree; BinaryTreeNode.java
 *         2010-4-26
 **/
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;
    }
   
}

 

 

package algorithm.binarytree;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

/**
 * <p>Description: Test</p>
 * <p>Copyright (c) 2010</p>
 * <p>Department: </p>
 * <p>Company: </p>
 * <p>Project:Test</p>
 *
 * @author Tomy Zhou
 * @since 1.0
 * @version algorithm.binarytree; BinaryTree.java
 *         2010-4-26
 **/
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);
       
    }

}

 

分享到:
评论

相关推荐

    二叉树构造与遍历

    通过对二叉树构造与遍历的深入学习与实践,学生不仅能够掌握二叉树的基本概念和操作,还能在算法设计、数据处理等方面获得实质性的提升。这种理论与实践相结合的学习方式,是提升计算机科学与技术专业学生专业技能的...

    算法-理论基础- 二叉树- 二叉树的遍历(包含源程序).rar

    这些遍历方法在实际应用中有着广泛用途,例如在编译器设计中构造语法树、文件系统的遍历以及数据的序列化和反序列化等。源程序通常会使用递归或栈来实现这些遍历策略,递归方法直观且易于理解,而栈方法则避免了函数...

    构造二叉树与遍历二叉树

    ### 构造二叉树与遍历二叉树 ...总之,通过上述分析我们可以了解到,二叉树不仅是一种重要的数据结构,也是许多高级数据结构的基础,掌握好二叉树的构造与遍历方法对于进一步学习更复杂的算法和数据结构至关重要。

    二叉树遍历序列还原

    给出二叉树的中序遍历序列和后序遍历序列,编程还原该二叉树。 输入:  第1行为二叉树的中序遍历序列  第2行为二叉树的后序遍历序列 输出:  二叉树的按层遍历序列

    二叉树的构造及遍历

    这个是数据结构中关于二叉树的构造及遍历。

    树/二叉树 各种遍历源代码(C++)

    - **中序遍历**:在二叉树中,中序遍历的顺序为左-根-右,通常用于构造二叉搜索树的有序序列。 - **后序遍历**:二叉树的后序遍历为左-右-根,对于非空二叉树,后序遍历可以用来计算表达式的值(Lisp中的读-eval-...

    数据结构(C语言版)--二叉树的遍历

    实验中提供了`Creat_Bt`函数来创建二叉树,通过输入数据(整数和字符)来构造树的结构。在`main`函数中,先调用`Creat_Bt`创建二叉树,然后分别调用三个遍历函数,输出先序、中序和后序遍历的结果。 在实际实验过程...

    实验五 二叉树的构造和遍历.pdf

    本实验主要关注二叉树的构造和遍历,通过Visual C++ 6.0环境进行实现。实验的目的在于加深对二叉树逻辑结构和物理结构的理解,掌握二叉链表的使用,以及如何进行二叉树的各种遍历方法。 首先,二叉树的存储结构通常...

    python 数据结构 算法 LeetCode 牛客 面试 编程之美 动态规划 字典树 快速排序 树 字符串 数组 链表 全排列

    * 遍历-中序遍历-非递归 * 遍历-前序遍历-非递归 * 遍历-后序遍历-非递归 * 二叉查找树-两数之和 * 二叉查找树-中第K小的元素 * 二叉查找树-从有序数组中构造二叉查找树 * 二叉查找树-从有序链表构造平衡的二叉查找...

    根据先序与中序遍历结果建立二叉树

    其中,二叉树的遍历是理解二叉树的基础之一,常见的遍历方法有先序遍历、中序遍历和后序遍历。 - **先序遍历**:访问顺序为“根—左—右”。 - **中序遍历**:访问顺序为“左—根—右”。 - **后序遍历**:访问顺序...

    二叉树的各种遍历,二叉搜索树的建立,前中序构建二叉树

    首先,我们要了解二叉树的三种基本遍历方式:前序遍历、中序遍历和后序遍历。这些遍历方法主要通过递归和非递归两种方式实现。 1. **前序遍历**(根-左-右):首先访问根节点,然后递归地遍历左子树,最后遍历右子...

    漫话数据结构-二叉树的存储和遍历.pptx

    例如,给定先序遍历序列`A B D H I E J C F G`和中序遍历序列`H D I B J E A F C G`,可以按照上述步骤构造出对应的二叉树,并验证其先序、中序、后序遍历序列是否匹配。 总之,理解二叉树的存储结构和遍历方法是...

    二叉树的建立及遍历

    二叉树是一种特殊的树结构,每个节点最多只有两个子节点,分为左子节点和右子节点。本问题涉及的核心知识点是二叉树的遍历及其构造。根据前序和中序遍历序列,我们可以唯一地恢复一棵二叉树。下面我们将详细探讨这个...

    二叉树先中序求后序 给出该二叉树的后序遍历结果;

    这可以通过已知的先序和中序遍历来构造二叉树,然后再进行后序遍历。 1. 首先,从先序遍历序列中找到根节点,它是序列中的第一个元素。 2. 接着,在中序遍历序列中找到根节点,将序列分为左右两部分,左侧是左子树...

    二叉树的构造与遍历

    二叉树的构造与前序遍历等基本操,简单的C++程序

    二叉树的三种遍历swf

    - **构建表达式树**:前序遍历可以用来构造表达式树,方便进行表达式的求值。 - **压缩编码**:后序遍历在某些树形编码算法中起到关键作用,如霍夫曼编码。 - **数据序列化与反序列化**:将二叉树转换为线性序列(如...

    算法-树形结构- 树与二叉树- 无根树转有根树.rar

    文档可能包含以下内容:无根树的表示方法、树的遍历算法、树的性质、二叉树的特性、有根树的构造方法、以及转换过程中的注意事项。此外,可能还会涵盖相关的编程实现,如使用递归或栈队列进行树的遍历和构造。 理解...

    数据结构二叉树的构造及遍历代码

    二叉树的简单构造及二叉树的前中后不同方法的遍历

    二叉树递归遍历,非递归遍历,按层次遍历

    例如,前序遍历适合构造和复制二叉树,中序遍历通常用于构造二叉搜索树,后序遍历可用于计算表达式树的结果。层次遍历则常用于显示树的层次结构,如在图形界面中绘制树形视图。 对于二叉树的操作,除了遍历外,还...

Global site tag (gtag.js) - Google Analytics