二叉树的构造和遍历

喜欢ヅ旅行 2022-08-22 11:27 138阅读 0赞

# 二叉树的构造 #

// 二叉树节点定义
    typedef struct BNode
    {
        char data;
        BNode *left;
        BNode *right;
    } BNode, *BTree;
    
    // 创建二叉树
    int creatBTree(BTree &tree)
    {
        char data;
        cin >> data;
        if (data == '#') // 使用#表示空节点
            tree = NULL;
        else
        {
            tree = new BNode; // 创建根节点
            tree->data = data;
            creatBTree(tree->left); // 创建左子树
            creatBTree(tree->right);// 创建右子树
        }
        return 0;
    }
    // 删除二叉树
    int destoryBTree(BTree tree)
    {
        // 
        if (tree)
        {
            BTree left = tree->left;
            BTree right = tree->right;
            delete tree;
            if (left)
                destoryBTree(left);
            if (right)
                destoryBTree(right);
        }
        //if (tree)
        //{
        
        //  if (tree->left)
        //      destoryBTree(tree->left);
        //  if (tree->right)
        //      destoryBTree(tree->right);
        //  delete tree;
        //}
        return 0;
    }

# 二叉树的遍历 #

// 访问二叉树
    void visit(BTree tree)
    {
        if (tree)
            cout << tree->data << " ";
    }

## 二叉树的前序遍历 ##

// 递归方式
    void preOrder(BTree tree)
    {
        if (tree) {
            visit(tree);
            preOrder(tree->left);
            preOrder(tree->right);
        }
    }

// 前序遍历的非递归版本
    // 分析过程
    /*
    分析：
    “右子树之间”的访问顺序呈现栈规律即“先入栈后访问”
    
    前序遍历：
    1 优先访问根节点和左子树，其右子树的根节点入栈暂存
    2 右子树的根节点出栈后的按照1的顺序访问
    */
    void preOrder2(BTree tree)
    {
        stack<BTree> sTree;
        while (tree || !sTree.empty() )
        {
            if (tree)
            {
                // 访问根节点
                visit(tree);         
    
                // 根节点的右子节点入栈保存
                if (tree->right)
                    sTree.push(tree->right);
                // 优先访问左子节点
                tree = tree->left;
            }
            else
            {
                tree = sTree.top();
                sTree.pop();
            }
        }
    }

//先序遍历(非递归)
    //访问T->data后，将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，再先序遍历T的右子树。
    void PreOrder3(BTree tree) {
    {
        stack<BTree> stack;
        while (tree || !stack.empty()) {   //栈不空或者p不空时循环
            if (tree) {
                stack.push(tree);          //存入栈中
                visit(tree);               //访问根节点
                tree = tree->left;       //遍历左子树
            } else {
                p = stack.top();           //退栈
                stack.pop();
                tree = tree->right;       //访问右子树
            }
        }
    }

## 二叉树的中序遍历 ##

// 递归遍历
    void midOrder(BTree tree)
    {
        if (tree) {
            midOrder(tree->left);
            visit(tree);
            midOrder(tree->right);
        }
    }

// 中序遍历的非递归版本
    // 分析过程
    /*
    分析
    根节点与左子树呈现栈的规律
    不同根节点的右子树之间呈现栈的规律
    注：把树划分成由只由左子树组成树好理解！！！
    
    遍历
    1 若根节点存在，根节点入栈
    2 左子树入栈，直到左子树的根节点没有左子树（左节点）
    3 左子树根节点出栈并访问，使用右子树的根节点更新原根节点信息，循环执行1、2、3
    */
    void midOrder2(BTree tree)
    {
        stack<BTree> sTree;
        while (tree || !sTree.empty())
        {
            if (tree)
            {
                sTree.push(tree);
                tree = tree->left;
            }
            else
            {
                tree = sTree.top();
                sTree.pop();
                visit(tree);
                tree = tree->right;
            }
    
        }
    }

## 二叉树的后序遍历 ##

// 递归遍历
    void postOrder(BTree tree)
    {
        if (tree)
        {
            postOrder(tree->left);
            postOrder(tree->right);
            visit(tree);
        }
    }

// 后序遍历
    /*
    <思路一>
    分析:
    1 将tree节点入栈，然后沿着左子树一直搜索，直到搜索到没有左孩子的节点；
    2 这个节点出现在栈顶，但不能出栈并访问它，其有孩子还没有被访问。
    3 按照 1、2的规则对其右子树进行处理，这个节点再次出现在栈顶时，出栈并访问。
    
    注：整个过程中，每个节点都两次出现在栈顶，节点第二次出现在栈顶时才能访问它，可以设置一个bool值来标识。
    */
    typedef struct BNodePost
    {
        BTree bTree;
        bool isFirst;
    }BNodePost, *BTreePost;
    
    void postOrder2(BTree tree)
    {
        stack<BTreePost> sBTreePost;
        BTreePost bTreePost;
        while (tree || !sBTreePost.empty())
        {
            if (tree)
            {
                // 沿左子树一直搜索并压栈，知道没有左子树
                BTreePost p = new BNodePost();
                p->bTree = tree;
                p->isFirst = true;
                sBTreePost.push(p);
                tree = tree->left;  
            }
            else
            {
                bTreePost = sBTreePost.top();
                sBTreePost.pop();
                if (bTreePost->isFirst) // 第一次出现在栈顶
                {
                    bTreePost->isFirst = false;
                    sBTreePost.push(bTreePost);
                    tree = bTreePost->bTree->right;
                }
                else // 第二次出现在栈顶
                {
                    visit(bTreePost->bTree);
                    delete bTreePost;
                }               
            }   
        }
    }

/*
    <思路二>
    分析:
    后续遍历特点：根节点在其左孩子有孩子被访问过之后才能被访问
    1 tree节点入栈
        1.1 此节点不存在左孩子右孩子，可以直接访问它
        1.2 此节点存在左孩子或右孩子，但其左孩子或右孩子节点已被访问过，可以直接访问该节点
    2 非1.1、1.2情况，将tree节点右孩子先入栈，左孩子再入栈，这样来保证每次取栈顶元素的顺序即先访问左孩子再访问右孩子。 
    */
    void postOrder3(BTree tree)
    {
        stack<BTree> sBTree;
        BTree preTree = NULL; // 上一次被访问的节点
    
        if (tree)
            sBTree.push(tree);
    
        while (!sBTree.empty())
        {
            BTree curTree = sBTree.top(); // 当前节点
            if ( (!curTree->left && !curTree->right)
                || (preTree && (preTree == curTree->left|| preTree == curTree->right)) 
                )
            {
                visit(curTree);
                sBTree.pop();
                preTree = curTree;
            }
            else
            {
                if (curTree->right)
                    sBTree.push(curTree->right);
                if (curTree->left)
                    sBTree.push(curTree->left);
            }
        }
    }

## 二叉树的层次遍历 ##

// 层次遍历：典型的BFS
    /*
    分析过程：
    层次遍历以树的高度来划分遍历的层次。
    其中，层次遍历访问的方式为二叉树存储的方式
    即:1 2*1 2*1+1 2*2 2*2+1 2*(2*1+1) 2*(2*1+1)+1 ....
    那么层次遍历就是按二叉树节点存储位置顺序访问即可
    根-左子节点-右子节点
    */
    
    /* 
    执行过程：
    1 根节点入栈
    2 根节点出栈，访问根节点
    3 根节点的左右子节点入栈
    4 重复2、3操作
    */
    void levelOrder(BTree tree)
    {
        queue<BTree> qTree;
        if (tree)
        {
            qTree.push(tree);
        }
        while (!qTree.empty())
        {
            // 根节点出队，访问根节点
            BTree curTree = qTree.front();
            qTree.pop();
            visit(curTree);
    
            // 左子节点不为空，入队
            if (curTree->left)
                qTree.push(curTree->left);
            // 右子节点不为空，入队
            if (curTree->right)
                qTree.push(curTree->right);
    
        }
    }

# 二叉树的输入与删除 #

// 输入与输出
    //ABC##DE#G##F###
    //先序遍历        ：A B C D E G F
    //先序遍历(非递归)：A B C D E G F
    //
    //中序遍历        ：C B E G D F A
    //中序遍历(非递归)：C B E G D F A
    //
    //后序遍历        ：C G E F D B A
    //后序遍历(非递归)：C G E F D B A
    //
    //层次遍历        ：A B C D E F G
    //
    
    ///       A
    ///      /
    ///     B
    ///    / \
    ///   C   D
    ///      / \
    ///     E   F
    ///      \
    ///       G

# 参考 #

1 [赵4老师版本][4]  
2 [二叉树的非递归遍历][Link 1]

[4]: http://bbs.csdn.net/topics/391957666?page=1#post-401188530
[Link 1]: http://www.cnblogs.com/dolphin0520/archive/2011/08/25/2153720.html