二叉树的遍历及创建

typedef char T;struct TreeNode
{T _data;TreeNode* left;TreeNode* right;
};

         1、二叉树的遍历---DFS

                                                      3

                                         5                       6

                                   1          #            8       # 

                               4      7                  #  #

                             #  #  2   #

                                    # #

 

1、1前序遍历（PreOrder）---DFS

        前序遍历，即根-左子树-右子树，左右子树又分为根-左子树-右子树

void PreOrder(TreeNode* root)
{if (root == NULL)return;cout << root->_data << " ";PreOrder(root->left);PreOrder(root->right);
}

3 5 1 4 7 2 6 8

1、2中序遍历（MidOrder）---DFS

        中序遍历，即左子树-根-右子树，左右子树又分为左子树-根-右子树

void MidOrder(TreeNode* root)
{if (root == NULL)return;MidOrder(root->left);cout << root->_data << " ";MidOrder(root->right);
}

4 1 2 7 5 3 8 6

         1、3后序遍历（PostOrder）---DFS

    中序遍历，即左子树-右子树-根，左右子树又分为左子树-右子树-根

void PostOrder(TreeNode* root)
{if (root == NULL)return;PostOrder(root->left);PostOrder(root->right);cout << root->_data << " ";
}