二叉树遍历详解（附完整代码）

淩亂°似流年 2022-12-13 12:46 154阅读 0赞

## 二叉树 ##

1、最常见的遍历种类  
先序遍历  
中序遍历  
后序遍历  
层次遍历  
二：遍历的递归代码实现分别给出Java 代码和C代码实现

2、二叉树的存储结构定义：  
1）顺序存储结构  
2） 链式存储结构

二叉链表的节点定义代码
    typedef struct BiTNode
    {
        
      TElemType data;//结点数据
      struct BiTNode *lchild, *rchild;//左右孩子指针
    } struct BiTNode, *BiTree;

public class BiTNode
    {
        
       int val;
       BiTNode left;
       BiNode  right;
    }

3、创建一棵二叉树（先序，中序，后序）  
待补充。。。

4、二叉树的遍历代码实现

//Java代码实现
    //二叉树的定义
    * public class TreeNode {
        
     *   int val = 0;
     *   TreeNode left = null;
     *   TreeNode right = null;
     * }
     * //前序遍历
        public void preOrder(TreeNode root){
        
            if (root != null) {
        
                System.out.print(root.val + " ");
                preOrder(root.left);
                preOrder(root.right);
            }
        }
        //中序遍历
        public void inOrder(TreeNode root){
        
            if (root != null) {
        
                inOrder(root.left);
                System.out.print(root.val + " ");
                inOrder(root.right);
            }
        }
        //后序遍历
        public void postOrder(TreeNode root){
        
            if (root != null) {
        
                postOrder(root.left);
                postOrder(root.right);
                System.out.print(root.val + " ");
            }
        }

//C代码实现
    struct TreeNode {
        
     *	int val;
     *	struct TreeNode *left;
     *	struct TreeNode *right;
     * };
    //前序遍历
    void PreOrderTraverse(BiTree T)
    {
        
      if(T==null)
      return;
       printf("%c",T->date);
       PreOrderTraverse(T->lchild);//先先序遍历左子树
       PreOrderTraverse(T->rchild);//最后先序遍历右子树
    }
    //中序遍历
    void InOrderTraverse(BiTree T)
    {
        
      if(T==null)
      return;
       PreOrderTraverse(T->lchild);//中序遍历左子树
       printf("%c",T->date);
       PreOrderTraverse(T->rchild);//中序遍历右子树
      }
       //后序遍历
    void InOrderTraverse(BiTree T)
    {
        
      if(T==null)
       return;
       PreOrderTraverse(T->lchild);//后序遍历左子树
       PreOrderTraverse(T->rchild);//后序遍历右子树
       printf("%c",T->date);
      }