遍历二叉树（四种方式：前序、中序、后序、层序）

 

 

二叉树顺序存储结构

 

二叉树的顺序存储结构就是用一维数组存储二义树中的结点并且结点的存储位置，也就是数组的下标要能体现结点之间的逻辑关系，比如双亲与孩子的关系，左右兄弟的关系等。二叉树的排序，之后按照，前序排序，中序排序，后序排序，层序排序就可以投影成数组，一般按照中序排序可以投射成由小到大的数组（平衡二叉树，红黑树都是特殊的二叉排序树）

 

顺序存储结构一般只用于完全二叉树。

 

 

 

将这棵二叉树存入到数组中，相应的下标对应其同样的位置：

 

 

 

二叉链表

 

typedef struct BiTNode  /* 结点结构 */

{

  TElemType data;                  /*结点数据 */

  struct BiTNode *lchild,*rchild; /* 左右孩子指针 */

}BiTNode,*BiTree;

 

 

 

 

遍历二叉树

 

二叉树的遍历是指从根结点出发。按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。

 

二叉树的遍历方法

 

1前序遍历

 

规则是若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。

 

 

 

遍历的顺序为:ABDGHCEIF

 

/* 操作结果: 前序递归遍历T */

void PreOrderTraverse(BiTree T)

{ 

if(T==NULL)

return;

printf("%c",T->data);/* 显示结点数据，可以更改为其它对结点操作 */

PreOrderTraverse(T->lchild); /* 再先序遍历左子树 */

PreOrderTraverse(T->rchild); /* 最后先序遍历右子树 */

}

2中序遍历

 

规则是若树为空，则空操作返回，否则从根结点开始(注意并不是先访问根结点)，中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树。

 

 

 

遍历的顺序为:GDHBAEICF

 

/* 操作结果: 中序递归遍历T */

void InOrderTraverse(BiTree T)

{ 

if(T==NULL)

return;

InOrderTraverse(T->lchild); /* 中序遍历左子树 */

printf("%c",T->data);/* 显示结点数据，可以更改为其它对结点操作 */

InOrderTraverse(T->rchild); /* 最后中序遍历右子树 */

}

3后序遍历

 

规则是若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点。

 

 

 

遍历的顺序为：GHDBIEFCA

 

/* 操作结果: 后序递归遍历T */

void PostOrderTraverse(BiTree T)

{

if(T==NULL)

return;

PostOrderTraverse(T->lchild); /* 先后序遍历左子树  */

PostOrderTraverse(T->rchild); /* 再后序遍历右子树  */

printf("%c",T->data);/* 显示结点数据，可以更改为其它对结点操作 */

}

4层序遍历

 

    规则是若树为空，则空操作返回，否则从树的第一层，也就是根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。

 

 

 

遍历的顺序为:ABCDEFGHI

 

 

 

层序遍历：

 

//前序遍历的输入,每层打印自己的，准备好下层

 

public void cengx(Node node){

 

    if(node==null)

        return ;

 

    system.out.print(node.data+" ");

 List<Node> nodeList = new ArrayList<Node>();

 if(node.lchild!=null){

   nodeList.add(node.lchild);

  

  }

  if(node.rchild!=null){

   nodeList.add(node.rchild);

  }

   cxzy(nodeList);//所有子节点

 

    

 

}

 

 

 

cxzy(List<Node> nodeList){

 

List<Node> newnodeList = new ArrayList<Node>();

 

for(nodeList){

  if(nl.lchild!=null){

   newnodeList.add(nl.lchild);

  

  }

  if(nl.rchild!=null){

   newnodeList.add(nl.rchild);

  }

 system.out.print(nl.data+" ");

}

 

 

 

   if(newnodeList.size!=null)

     cxzy(newnodeList);

 

 

      

      }

 

 

层序遍历二：

用对了数据结构或分类恰当，就会有标准的递归，不用一个起头的函数 

 

 

 

public void levelOrder() {

    BiTNode<E> node =root;

    LinkedList<BiTNode<E>> list = new LinkedList<>();

    list.add(node);

    while(!list.isEmpty()) {

        node=list.poll();

        System.out.print(node.data);

        if(node.lchild!=null)

            list.offer(node.lchild);

        if(node.rchild!=null)

            list.offer(node.rchild);

    }

}