数据结构--二叉树的遍历

红太狼 2022-07-30 16:27 24阅读 0赞

# 二叉树的概念 #

二叉树作为最常见以及最常用的的结构，其特点是对于每一个父节点，最多包含两个节点，因此对于一个二叉树，可以将其分为三个部分，根节点，左子树和右子树。一般来说，存储结构分为线性存储结构和链式存储结构。线性存储结构一般来说是以数组的方式呈现的，其特点是在内存中表现为连续的空间分配。而对于链式存储结构，在逻辑上是有种某种关系，比如逻辑连续，但是在实际物理的内存空间上的分配上，却没有任何的规律。对于二叉树而言，一般来说对于满二叉树概念下的完全二叉树，有的时候，很多父节点并没有含有孩子节点，这个时候采用线性存储结构，就会大大的浪费存储空间，当数据量很大的时候，这个时候内存空间就会有很大的浪费，导致内存不足，这个时候采用链式存储结构就会大大的节约存储空间。

## 满二叉树的概念： ##

![20160419203306961][]

如图，对于满二叉树而言，其每一个父节点，都含有两个孩子节点，同时也可以得出，对于层次为n的满二叉树，其还有的节点个数一定为2^n-1。例如上图，层次为4，其节点数为15。（PS:最后的叶子节点15和16的节点标号应该为14,15）。

##  完全二叉树 ##

对应到完全二叉树的概念，其节点的标号在每一层对应于满二叉树，即虽然完全二叉树并没有满二叉树那么多的节点，但是其每一层的孩子节点的表示和满二叉树节点是一一对应的。对比图(a)和图(b),即可理解这一概念。

# 二叉树的遍历 #

对二叉树的遍历，实际上就是通过某种遍历方式，将二叉树的节点进行访问。由于二叉树的逻辑结构的特征，并不能像数组或者vector，栈或者队列那么简单的对元素进行访问，需要根据其结构，即父子节点最多含有两个子节点这一特征进行访问。一般而言，遍历的方法有先序遍历，中序遍历、后序遍历以及层次遍历。

## 先序遍历 ##

先序遍历是通过先访问父子节点，然后访问左子树，然后访问右子树完成遍历。

![20160419205123545][]

对于上图来说，先序遍历的结果为：GDAFEMHZ

## 中序遍历 ##

中序遍历，首先访问的是左子树，后访问其父节点，然后访问其右节点。

对于上图而言，中序遍历的结果为：ADEFGHMZ

## 后序遍历 ##

后序遍历，首先访问的是左子树，后访问对应的右子树，然后方位父节点。

对于上图而言，后序遍历的结果为：AEFDHZMG

## 层次遍历 ##

层序遍历，就是二叉树的逻辑图是咋样的，遍历就是咋样的。

对于上图而言，层次遍历的结果：GDMAFHZE

# 二叉树的遍历实现： #

二叉树的创建： 比较简单的容易理解的方法就是按照程序遍历的方法构建二叉树。实现的过程：

*  树节点的定义

template<class T> class BinaryTree;
    template<class T>
    class TreeNode
    {
        friend class BinaryTree<T>;
    private:
        T data;
        TreeNode<T> *left;
        TreeNode<T> *right;
    public:
        TreeNode();
    };
    
    template<class T>
    TreeNode<T>::TreeNode()
    {
        data='#';
        left=nullptr;
        right=nullptr;
    }

*  二叉树的定义

template<class T>
    class BinaryTree
    {
    public:
        BinaryTree();
        ~BinaryTree();
        TreeNode<T> *createBinaryTree(vector<T> data);
    
        //先序遍历
        void PreOrder();
        void PreOrder(TreeNode<T> *node);
    
        //中序遍历
        void InOrder();
        void InOrder(TreeNode<T> *node);
    
        //后序遍历
        void PostOrder();
        void PostOrder(TreeNode<T> *node);
    
        //层次遍历
        void LevelOrder();
    
        void Visit(TreeNode<T> *node);
    private:
        TreeNode<T>* root;
    };

*  二叉树的创建

//create BinaryTree by level
    template<class T>
    TreeNode<T>* BinaryTree<T>::createBinaryTree(vector<T> dataInput)
    {
        int length=dataInput.size();
        if(length==0)
            return NULL;
    
        queue<TreeNode<T> *> temp;
        int nIndex=0;
        root=new TreeNode<T>;
        root->data=dataInput[nIndex++];
        temp.push(root);
        TreeNode<T> *p=NULL;
        while(!temp.empty() && nIndex<length)
        {
            p=temp.front();
            temp.pop();
            if(nIndex<length && dataInput[nIndex]!='#')
            {
                TreeNode<T> *leftNode=new TreeNode<T>;
                leftNode->data=dataInput[nIndex];
                p->left=leftNode;
                temp.push(leftNode);
            }
            nIndex++;
           if(nIndex<length && dataInput[nIndex]!='#')
            {
                TreeNode<T> *rightNode=new TreeNode<T>;
                rightNode->data=dataInput[nIndex];
                p->right=rightNode;
                temp.push(rightNode);
            }
            nIndex++;
        }
        return root;
    }

*  遍历过程实现

template<class T>
    void BinaryTree<T>::Visit(TreeNode<T> *node)
    {
       cout<<node->data<<"--";
    }
    
    template<class T>
    void BinaryTree<T>::PreOrder()
    {
        PreOrder(root);
    }
    template<class T>
    void BinaryTree<T>::PreOrder(TreeNode<T> *node)
    {
        if(node)
        {
            Visit(node);
        PreOrder(node->left);
        PreOrder(node->right);
        }
    
    }
    
    template<class T>
    void BinaryTree<T>::InOrder()
    {
        InOrder(root);
    }
    
    template<class T>
    void BinaryTree<T>::InOrder(TreeNode<T> *node)
    {
        if(node)
        {
            InOrder(node->left);
            Visit(node);
            InOrder(node->right);
        }
    }
    
    template<class T>
    void BinaryTree<T>::PostOrder()
    {
        PostOrder(root);
    }
    
    template<class T>
    void BinaryTree<T>::PostOrder(TreeNode<T> *node)
    {
        if(node)
        {
            PostOrder(node->left);
            PostOrder(node->right);
            Visit(node);
        }
    }
    
    template<class T>
    void BinaryTree<T>::LevelOrder()
    {
        queue<TreeNode<T> *>q;
        TreeNode<T>* currentNode=root;
        while(currentNode)
        {
            Visit(currentNode);
            if(currentNode->left) q.push(currentNode->left);
            if(currentNode->right) q.push(currentNode->right);
            if(q.empty())
                return ;
            currentNode=q.front();
            q.pop();
    
        }
    }

具体的结果为：

![20160419211539946][]

完整的实现过程是，具体的文件实现下载网址为：[二叉树遍历][Link 1]

[20160419203306961]: /images/20220724/e709e81a723f4c59921dc87f9c71ef92.png
[20160419205123545]: /images/20220724/debb32c3573a43d492bd9aea1f594a17.png
[20160419211539946]: /images/20220724/d0ad2b7acbe74c629af132e7a89cc8d9.png
[Link 1]: http://download.csdn.net/detail/mao19931004/9496251