《数据结构》中二叉树的存储与遍历
摘要：二叉树是一种非线性数据结构，它的存储和遍历比线性结构复杂，本文将讲述二叉树的存储和遍历。
关键字：二叉树；存储；遍历
Abstract: a binary tree is a nonlinear data structure, its storage and traverse than linear structure is complex, this article will talk about binary tree’s storage and traverse.
Keyword: binary tree; Storage; traverse
中图分类号：C37文献标识码：A 文章编号：
二叉树是《数据结构》中重要的内容。二叉树是一种非线性结构，它的存储与遍历与比线性表要复杂。下面给出了二叉树的存储和遍历方法。二叉树公式
一．二叉树的存储
二叉树的存储既可以采用链式存储结构来存储也可以采用数组来存储。本文采用数组来存储。考虑到二叉树至多只有两个孩子，有些结点有孩子，有些结点没有孩子，有些结点有两个孩子。为了唯一地表示结点以及每个结点的左右孩子，需要为每个结点编一个序号，该序号就是数组的下标。以图1所示二叉树为例。
图1 二叉树图 图2 编号之后的原二叉树
为了给每个结点唯一编号，不妨引入四层的满二叉树，从上到下从左到右开始编号。参照四层满满二叉树对原二叉树各个结点进行编号，如图2所示。从图中可以看出即使是满二叉树也满足编号要求，无论是满二叉树还是一般二叉树，每个结点的左孩子的序号都等于父结点序号乘以2，右孩子的编号都是父结点的编号乘以2再加1。
存储二叉树的算法如下：
public class Shu {
class Tree{
    int data;
    Tree lchild;
    Tree rchild;
}
    Tree []t;
    public void createT(int m){

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。