二叉树的创建

小灰灰 2022-06-16 00:57 224阅读 0赞

![这里写图片描述][SouthEast]

先序遍历：根左右：1->2->3->4->5->6->7->8  
中序遍历：左根右：2->3->1->5->6->7->4->8  
后序遍历：左右根：3->2->7->6->5->8->4->1

如何创建一个二叉树，采用自定义来定义每个结点的成员  
采用递归的方式来创建一棵树根左右的方式，不断的进行递归来创建二叉树的左子树，右子树  
例如这里举个例子创建如下的树  
![这里写图片描述][SouthEast 1]  
看它是怎么递归来创建的  
![这里写图片描述][SouthEast 2]

#include<iostream>
    #include<stdlib.h>
    using namespace std;
    template<class T>
    struct BinaryTreeNode
    {
            BinaryTreeNode( const T &data)
            : pLeft( NULL)
            , pRight( NULL)
            , _data( data)
            {
    
            }
             BinaryTreeNode<T >* pLeft;
             BinaryTreeNode<T >* pRight;
             T _data;
    };
    每个结点中包含自己的数据成员，还有指向该结点的左孩子的结点指针，指向该节点的右孩子的结点指针
    通过数组传参来构建二叉树
    template<class T>
    class BinaryTree { public: BinaryTree() //空树 :_pRoot( NULL) { } BinaryTree( const T arr[], size_t size ) { size_t index = 0; _CreatBinaryTree(_pRoot, arr, size , index); } void _CreatBinaryTree(BinaryTreeNode <T>*& pRoot, const T arr[], size_t size ,size_t& index ) { if (index < size&& arr[index ] != '#') { pRoot = new BinaryTreeNode<T >(arr[index]); _CreatBinaryTree( pRoot->pLeft, arr , size, ++index ); _CreatBinaryTree( pRoot->pRight, arr , size, ++index ); } } void Print_Front(BinaryTreeNode <T>* pRoot)//前序遍历二叉树 { BinaryTreeNode<T >* Cur = pRoot; //根左右 if (Cur) { cout <<Cur->_data << " "; Print_Front(Cur->pLeft); Print_Front(Cur->pRight); } } void Print_Middle(BinaryTreeNode <T>* pRoot)//中序遍历，左根右 { BinaryTreeNode<T >* Cur = pRoot; if (Cur) { Print_Middle(Cur->pLeft); cout << Cur->_data << " "; Print_Middle(Cur->pRight); } } void Print_Back(BinaryTreeNode <T>* pRoot) { BinaryTreeNode<T >* Cur = pRoot; if (Cur) { Print_Back(Cur->pLeft); Print_Back(Cur->pRight); cout << Cur->_data << " "; } } BinaryTreeNode<T >* _pRoot; };

其实递归的创建二叉树就是一层一层的进行函数的调用  
二叉树的递归遍历分为：  
前序遍历  
中序遍历  
后序遍历  
在递归的前序遍历：就是先打印根节点在打印左子树节点然后右子树结点，  
思想和递归的创建二叉树的思想是一致的。

[SouthEast]: /images/20220616/f261d78830a1409ca9d84af090f16dc6.png
[SouthEast 1]: /images/20220616/6e7bfa627799428880ae847470b1ceaa.png
[SouthEast 2]: /images/20220616/295b4b6c16a14e1cbb5e5a0c6488c87d.png