二叉树的创建和遍历-C语言实现

桃扇骨 2021-09-14 15:34 366阅读 0赞

# 二叉树的创建和遍历-C语言实现 #

--------------------

## 链式存储结构 ##

struct BinaryTreeNode {
            //数据
            char data;
            //左子树
            BinaryTreeNode *leftChild;
            //右子树
            BinaryTreeNode *rightChild;
        };

### 三种遍历方式 ###

*  中序遍历
    
    1.  中序遍历其左子树
    2.  访问根节点
    3.  中序遍历其右子树
 *  先序遍历（前序遍历）
    
    1.  访问根节点
    2.  先序遍历其左子树
    3.  先序遍历其右子树
 *  后序遍历  
    
    
    1.  后序遍历其左子树
    2.  后序遍历其右子树
    3.  访问根节点

### 树的形状 ###

![二叉树][SouthEast]

### 代码实现 ###

#include <iostream>
    #include <stack>
    #include<vector>
    #include <queue>
    
    using namespace std;
    
    //起别名
    typedef struct BinaryTreeNode *BinaryTree;
    
    struct BinaryTreeNode {
        //数据
        char data;
        //左子树
        BinaryTreeNode *leftChild;
        //右子树
        BinaryTreeNode *rightChild;
    };
    
    /** * 访问二叉树的节点 * @param binaryTree */
    void visit(BinaryTree binaryTree) {
        if (binaryTree) {
            cout << binaryTree->data << " ";
        }
    }
    
    /** * 创建一棵二叉树，约定用户遵照前序遍历的方式输入数据 * @param binaryTree */
    void createTree(BinaryTree *binaryTree) {
        // abd**fe***cg*h**i** 根据创建二叉树
        char dataTemp;
        cin >> dataTemp;
        //用*来表示该节点的数据为空即该节点为空
        if ('*' == dataTemp) {
            *binaryTree = NULL;
        } else {
            //先创建该结点
            *binaryTree = (BinaryTree) (malloc(sizeof(BinaryTreeNode)));
            //前序遍历：数据->左子树->右子树
            (*binaryTree)->data = dataTemp;
            createTree(&(*binaryTree)->leftChild);
            createTree(&(*binaryTree)->rightChild);
        }
    }
    
    /** * 中序遍历二叉树（递归算法） * @param binaryTree */
    void InOrderTraversal(BinaryTree binaryTree) {
        if (binaryTree) {
            InOrderTraversal(binaryTree->leftChild);
            visit(binaryTree);
            InOrderTraversal(binaryTree->rightChild);
        }
    }
    
    /** * 中序遍历（非递归） * @param binaryTree */
    void InOrderTraversalNO(BinaryTree binaryTree) {
        if (binaryTree == NULL) {
            return;
        }
        //初始化栈
        stack<BinaryTreeNode *> myStack;
        BinaryTree temp = binaryTree;
        while (temp != NULL || !myStack.empty()) {
            //根指针进栈，遍历左子树
            if (temp != NULL) {
                myStack.push(temp);
                temp = temp->leftChild;
            } else {
                //根指针退栈，访问根节点，遍历右子树
                temp = myStack.top();
                myStack.pop();
                visit(temp);
                temp = temp->rightChild;
            }
        }
    }
    
    /** * 先序遍历二叉树(递归算法) * @param binaryTree */
    void PreOrderTraversal(BinaryTree binaryTree) {
        if (binaryTree) {
            visit(binaryTree);
            PreOrderTraversal(binaryTree->leftChild);
            PreOrderTraversal(binaryTree->rightChild);
        }
    }
    
    /** * 先序遍历（非递归） * @param binaryTree */
    void PreOrderTraversalNO(BinaryTree binaryTree) {
        if (binaryTree == NULL) {
            return;
        }
        //初始化栈
        stack<BinaryTreeNode *> myStack;
        BinaryTree temp = binaryTree;
        while (temp != NULL || !myStack.empty()) {
            //根指针进栈，遍历左子树
            if (temp != NULL) {
                visit(temp);
                myStack.push(temp);
                temp = temp->leftChild;
            } else {
                //根指针退栈，访问根节点，遍历右子树
                temp = myStack.top();
                myStack.pop();
                temp = temp->rightChild;
            }
        }
    }
    
    /** * 后序遍历二叉树（递归算法） * @param binaryTree */
    void PostOrderTraversal(BinaryTree binaryTree) {
        if (binaryTree) {
            PostOrderTraversal(binaryTree->leftChild);
            PostOrderTraversal(binaryTree->rightChild);
            visit(binaryTree);
        }
    }
    
    /* * 要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点P， * 先将其入栈。如果P不存在左孩子和右孩子，则可以直接访问它； * 或者P存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点。 * 若非上述两种情况，则将P的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候， * 左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。 */
    void PostOrderTraversalNO(BinaryTree binaryTree) {
        if (binaryTree == NULL) {
            return;
        }
        BinaryTree temp = binaryTree;
        stack<BinaryTreeNode *> myStack;
        //当前结点
        BinaryTree current;
        //前一次访问的结点
        BinaryTree pre = NULL;
        myStack.push(binaryTree);
        while (!myStack.empty()) {
            current = myStack.top();
            if ((current->leftChild == NULL && current->rightChild == NULL) ||
                (pre != NULL && (pre == current->leftChild || pre == current->rightChild))) {
                //如果当前结点没有孩子结点或者孩子节点都已被访问过
                visit(current);
                myStack.pop();
                pre = current;
            } else {
                if (current->rightChild != NULL) {
                    myStack.push(current->rightChild);
                }
                if (current->leftChild != NULL) {
                    myStack.push(current->leftChild);
                }
            }
        }
    }
    
    char ch;
    bool flag;
    
    void findpath(BinaryTree binaryTree, char x, vector<char> &v) {
        if (binaryTree == NULL) {
            return;
        }
        v.push_back(binaryTree->data);
        if (binaryTree->data == x) {
            flag = 1;
            for (int i = 0; i < v.size(); i++) {
                putchar(v[i]);
            }
            putchar(10);
            return;
        }
        findpath(binaryTree->leftChild, x, v);
        findpath(binaryTree->rightChild, x, v);
        v.pop_back();
    }
    
    /** * 二叉树的层序遍历 * @param binaryTree */
    void levelOrderTraversal(BinaryTree binaryTree) {
        if (binaryTree == NULL) {
            return;
        }
        //定义使用的队列
        queue<BinaryTreeNode *> myQueue;
        BinaryTree temp = binaryTree;
        //根节点入队
        myQueue.push(temp);
        //队列不为空的时候循环
        while (!myQueue.empty()) {
            //队头元素出队
            temp = myQueue.front();
            myQueue.pop();
            //访问temp指向的节点
            visit(temp);
            //左子树不为空，入队左子树
            if (temp->leftChild != nullptr) {
                myQueue.push(temp->leftChild);
            }
            //右子树不为空，入队右子树
            if (temp->rightChild != nullptr) {
                myQueue.push(temp->rightChild);
            }
        }
    }
    
    /** * 获取双分支节点的个数 * @param binaryTree */
    int PreOrderTraversalGet2(BinaryTree binaryTree) {
        if (binaryTree == NULL) {
            return 0;
        }
        int number = 0;
        //初始化栈
        stack<BinaryTreeNode *> myStack;
        BinaryTree temp = binaryTree;
        while (temp != NULL || !myStack.empty()) {
            //根指针进栈，遍历左子树
            if (temp != NULL) {
                if (temp->rightChild != NULL && temp->leftChild != NULL) {
                    number++;
                }
                myStack.push(temp);
                temp = temp->leftChild;
            } else {
                //根指针退栈，访问根节点，遍历右子树
                temp = myStack.top();
                myStack.pop();
                temp = temp->rightChild;
            }
        }
        return number;
    }
    
    /** * 求二叉树的深度 * @param binaryTree * @return */
    int postOrderGetHeight(BinaryTree binaryTree) {
        if (binaryTree) {
            //求左子树的深度
            int leftHeight = postOrderGetHeight(binaryTree->leftChild);
            //求右子树的深度
            int rightHeight = postOrderGetHeight(binaryTree->rightChild);
            int max = leftHeight > rightHeight ? leftHeight : rightHeight;
            return max + 1;
        } else {
            return 0;
        }
    }
    
    /* 如果需要构建一颗如下所示的二叉树： A B C D F G I E H 输入ABD**FE***CG*H**I** 即可创建该二叉树 * */
    int main() {
        BinaryTree binaryTree = NULL;
        createTree(&binaryTree);
        cout << "中序遍历：（递归）" << endl;
        InOrderTraversal(binaryTree);
        cout << endl;
        cout << "中序遍历：（非递归）" << endl;
        InOrderTraversalNO(binaryTree);
        cout << endl;
    
        cout << "先序遍历：（递归）" << endl;
        PreOrderTraversal(binaryTree);
        cout << endl;
        cout << "先序遍历：（非递归）" << endl;
        PreOrderTraversalNO(binaryTree);
        cout << endl;
    
        cout << "后序遍历：（递归）" << endl;
        PostOrderTraversal(binaryTree);
        cout << endl;
        cout << "后序遍历：（非递归）" << endl;
        PostOrderTraversalNO(binaryTree);
        cout << endl;
    
        cout << "层序遍历：" << endl;
        levelOrderTraversal(binaryTree);
        cout << endl;
    
        cout << "二叉树的深度：" << postOrderGetHeight(binaryTree) << endl;
        cout << "二叉树的中双分支节点的个数为：" << PreOrderTraversalGet2(binaryTree) << endl;
    
        char x;
        cout << "请输入查找路径字符：";
        cin >> x;
        vector<char> v;
        cout << "根节点到" << x << "的路径为：";
        findpath(binaryTree, x, v);
        cout << endl;
        return 0;
    }

[SouthEast]: /images/20210911/952e448e7cc3445ca9aa818f8bf166c6.png