C/C++ 二叉树的创建、遍历及树的深度链表实现

清疚 2022-02-02 04:55 144阅读 0赞

**关于二叉树的创建、先序遍历、中序遍历、后序遍历和求树的深度链表实现。**  
**代码如下，如有问题可以留言。**

/* 二叉树的创建及遍历 */
    
    #include <iostream>
    #include <cstring>
    #include <cstdlib>
    
    using namespace std;
    
    #define ElementType string //如果想用整型可以把string修改为int
    
    struct tree {
        ElementType data;
        struct tree* left;
        struct tree* right;
    };
    
    struct tree* CreatTree (struct tree* root) { //创建二叉树
        ElementType num;
        cin >> num;
        if (num == ".")
            return NULL;
        root = (struct tree*)malloc(sizeof(struct tree)); //给结点分配内存
        root->data = num;
        cout << "请输入" << root->data << "的左子树：";
        root->left = CreatTree(root->left); //递归添加左子树
        cout << "请输入" << root->data << "的右子树：";
        root->right = CreatTree(root->right); //递归添加右子树
        return root;
    }
    
    void PreOrderTraversal (struct tree* root) { //递归法先序遍历（顺序：根 -- 左 -- 右）
        if (root == NULL)
            return;
        cout << root->data << " ";  //先输出根节点
        PreOrderTraversal(root->left);
        PreOrderTraversal(root->right);
    }
    
    void InOrderTraversal (struct tree* root) { //递归法中序遍历（顺序：左 -- 根 -- 右）
        if (root == NULL)
            return;
        InOrderTraversal(root->left);
        cout << root->data << " ";
        InOrderTraversal(root->right);
    }
    
    void PostOrderTraversal (struct tree* root) { //递归法后序遍历（顺序：左 -- 右 -- 根）
        if (root == NULL)
            return;
        PostOrderTraversal(root->left);
        PostOrderTraversal(root->right);
        cout << root->data << " ";
    }
    
    int Tree_Depth (struct tree* root) { // 递归法求树的深度
        if (root != NULL) {
            int Left_D  = Tree_Depth(root->left); // 先求左子树的最大深度
            int Right_D = Tree_Depth(root->right); // 再求右子树的最大深度
            int Max = max(Left_D, Right_D);  // 最后取最大的深度
            return Max + 1;
        }
        return 0;
    }
    
    int main() {
        cout << "请输入头节点：";
        struct tree* root = CreatTree(root); // 创建根节点
        
        PreOrderTraversal(root);
        cout << endl;
        
        InOrderTraversal(root);
        cout << endl;
        
        PostOrderTraversal(root);
        cout << endl;
        
        cout << Tree_Depth(root) << endl;
        
        return 0;
    }