二叉树的节点

二叉树的节点定义

template <class T>
class BTNode{
    public:
        T value;            // 关键字 (键值)
        BSTNode *left;      // 左孩子
        BSTNode *right;     // 右孩子

        BSTNode(T v, BTNode *l = nullptr, BTNode *r = nullptr):
            value(v),left(l),right(r) {}
};

二叉树的遍历

二叉树的遍历，有三种方法：

• 递归法
• 栈迭代法
• MORRIS 迭代法

下面我们分别分析下三种方法：

递归法

三种方式中，递归法最好理解，具体实现如下：

前序遍历（递归法）

template <class T>
void BSTree<T>::BTPreOrder(BSTNode<T>& node) const
{
    if(node == nullptr) return;
    cout << node->value << " " ;
    BTPreOrder(node->left);
    BTPreOrder(node->right);
}

中序遍历（递归法）

template <class T>
void BSTree<T>::BTPMidOrder(BSTNode<T>& node) const
{
    if(node == nullptr) return;
    BTPMidOrder(node->left);
    cout << node->value << " " ;
    BTPMidOrder(node->right);
}

后序遍历（递归法）

template <class T>
void BSTree<T>::BTPostOrder(BSTNode<T>& node) const
{
    if(node == nullptr) return;
    BTPostOrder(node->left);
    BTPostOrder(node->right);
    cout << node->value << " " ;
}

栈迭代法

前序遍历（栈迭代法）

template <class T>
void BSTree<T>::BTPreOrder(BSTNode<T>& node)
{
    stack<TreeNode*> nodeStack;
    BSTNode<T>* node = root;
    while (node || !nodeStack.empty()) {
        if (node) {
            nodeStack.push(node);
            cout << node->value << " " ;
            node = node->left;
        }
        else {
            node = nodeStack.top();
            nodeStack.pop();
            node = node->right;
        }
    }
}

中序遍历（栈迭代法）

template <class T>
void BSTree<T>::BTMidOrder(BSTNode<T>& node)
{
    stack<TreeNode*> nodeStack;
    BSTNode<T>* node = root;
    while (node || !nodeStack.empty()) {
        if (node) {
            nodeStack.push(node);
            node = node->left;
        }
        else {
            node = nodeStack.top();
            cout << node->value << " " ;
            nodeStack.pop();
            node = node->right;
        }
    }
}

MORRIS 迭代法

#ifdef PRO_ORDER
BSTree<T>* BSTree<T>::rightReverse(BSTree<T>* root) {
    BSTree<T>* head = nullptr;
    while (root) {
        BSTree<T>* next = root->right;
        root->right = head;
        head = root;
        root = next;
    }
    return head;
}
void BSTree<T>::printEdge (BSTree<T>* root) {
    root = rightReverse(root);
    BSTree<T>* head = root;
    while (head != NULL) {
        result.push_back(head->val);
        head = head->right;
    }
    root = rightReverse(root);
}
#endif
void BSTree<T>::BSTOrder()
{
    if (node == nullptr) return;
    BSTNode<T>* node = root;
    while (node) {
        if (node->left) {
            /* 如果存在左子树，则需要设置索引 */
            BSTNode<T>* index = node->left;
            while(index->right && index->right != node)
            {
                index = index->right;
            }

            if (!index->right) {
                /* 首次寻找到索引，设置索引，继续遍历左子树 */
#ifdef PRE_ORDER
                cout <<node->value << " " ;
#endif
                index->right = node;
                node = node->left;
            }
            else {
                /* 非首次寻找到索引，说明左子树遍历完成，根据索引去遍历右子树 */
#ifdef MID_ORDER
                cout <<node->value << " " ;
#endif
                node = node->right;
                /* 恢复索引 */
                index->right = nullptr;
#ifdef PRO_ORDER
                printEdge(root);
#endif
            }
        }
        else {
            /* 没有左子树 遍历右子树 */
#ifndef PRO_ORDER
            cout <<node->value << " " ;
#endif
            node = node->right;
        }
#ifdef PRO_ORDER
        printEdge(root);
#endif
    }
}