浅析二叉树的遍历以及二叉查找树

不多说了，又是忘掉了这个东西，手动扣点代码，找找感觉
二叉查找树，首先，它得是棵树，对吧，而且还是个二叉树对吧，大体长这个样子

呃呃，为了后面省事，这张直接给出了平衡二叉树，那个是一种特殊的二叉查找树，后续会撸源码，这次只说二叉查找树。好的，回到上面的树，首先这棵树是由各个节点组成的（这不废话），然后每个节点只有两个出度，分别为左孩子以及右孩子（两个指针，指向相同的节点），还有一个重要的性质是，对于某一节点其左子树上的所有节点全部小于它的值，其右子树上的所有节点值全部都大于其值，其定义如下：

struct Node{
    struct Node *left;
    struct Node *right;
    int val;
    Node(int x):val(x), left(NULL), right(NULL){}
};

只有这一个结构只能保证有左右两个孩子，不能保证数值大小的性质，这就要在我们插入的时候费点心思了，代码如下（注：我是把该树建了一个类，第一段代码时.h文件，所有操作在里面完成，后面不再赘述）：

#ifndef BSTTREE_H
#define BSTTREE_H
#include <iostream>
#include <stack>
struct Node{
    struct Node *left;
    struct Node *right;
    int val;
    Node(int x):val(x), left(NULL), right(NULL){}
};

class BSTTree
{
public:
    BSTTree();
    ~BSTTree();
    void preOrderWithRecur(struct Node *node);
    void preOrderNon_Recur(struct Node *node);
    void inOrderWithRecur(struct Node *node);
    void inOrderNon_Recur(struct Node *node);
    void postOrderWithRecur(struct Node *node);
    void postOrderNon_Recur(struct Node *node);
    bool isExist(struct Node *node, int k);
    bool insert(struct Node *node, int k);
    int getHeight(struct Node *node);
    bool delNode(struct Node *node, int k);
    struct Node *root;
private:
    bool delRoot();
    bool delNodeLeftNULL(struct Node *parent, struct Node *node);
    bool delNodeRightNULL(struct Node *parent, struct Node *node);
    bool delRootLeftNULL();
    bool delRootRightNULL();

};

#endif // BSTTREE_H

插入代码如下，过程就是从根找起，直到找到自己的位置~~~

bool BSTTree::isExist(Node *node, int k){
    struct Node *p = node;
    while(p){
        if(p->val == k) return true;
        else if(p->val > k) p = p->left;
        else p = p->right;
    }
    return false;
}
bool BSTTree::insert(struct Node *node, int k){
    if(isExist(node, k))
        return false;
    struct Node *p = node, *parent = NULL;
    while(p){
        parent = p;
        if(p->val > k) p = p->left;
        else p = p->right;
    }
    p = new struct Node(k);
    if(root == NULL){ root = p; return true;}
    else if(parent->val > p->val) parent->left = p;
    else parent->right = p;
    return true;
}

这里特殊情况就是在树为空的时候，要判断一下（因为那时候祖宗还没出现。。。）
接下来讲一下删除，相信大家通过.h文件已经了解到，我是分了好多情况进行讨论来实现的，（因为自己实力有限，看着各种嵌套有点乱）总体来讲，分成两个部分，一个是删除根节点，一个是删除非根节点，因为如果删除非根节点的话，就需要知道其父节点信息，所以分了一下，再有就是在这两大类下面又各自分了两类--->左子树为空，右子树为空，具体代码如下：

bool BSTTree::delNode(struct Node *node, int k){
    struct Node *parent, *child;
    if(root == NULL) return false;
    if(root->val == k) return delRoot();
    node = root;
    while(node){
        if(node->val == k) break;
        parent = node;
        if(node->val > k) node = node->left;
        else node = node->right;
    }
    if(node == NULL) return false;
    if(node->left== NULL && node->right == NULL){
        if(node == parent->left) parent->left = NULL;
        else parent->right = NULL;
        delete node;
        node = NULL;
        return true;
    }else if(node->left==NULL)
        return delNodeLeftNULL(parent, node);
    else if(node->right== NULL)
        return delNodeRightNULL(parent, node);
    else{
        parent = node, child = node->right;
        int temp;
        while(child->left){ parent = child; child = child->left;}
        temp=node->val; node->val = child->val; child->val = temp;
        if(child == parent->left) parent->left = child->right;
        else parent->right = child->right;
        delete child, child = NULL;
        return true;
    }
}
bool BSTTree::delNodeLeftNULL(struct Node *parent, struct Node *node){
    if(parent->left == node) parent->left = node->right;
    else parent->right = node->right;
    delete node;
    node = NULL;
    return true;
}
bool BSTTree::delNodeRightNULL(struct Node *parent, struct Node *node){
    if(parent->left == node) parent->left = node->left;
    else parent->right = node->left;
    delete node;
    node = NULL;
    return true;
}
bool BSTTree::delRoot(){
    if(root->left == NULL && root->right == NULL){
        delete root;
        root = NULL;
        return true;
    }else if(root->left == NULL){
        return delRootLeftNULL();
    }else if(root->right == NULL){
        return delRootRightNULL();
    }else{
        struct Node *parent = root, *child = root->right;
        int temp;
        while(child->left){ parent = child; child = child->left;}
        temp = root->val; root->val = child->val; child->val = temp;
        if(child == parent->left) parent->left = child->right;
        else parent->right = child->right;
        delete child;
        child = NULL;
        return true;
    }
}
bool BSTTree::delRootLeftNULL(){
    struct Node *p = root;
    root = root->right;
    delete p;
    return true;
}
bool BSTTree::delRootRightNULL(){
    struct Node *p = root;
    root = root->left;
    delete p;
    return true;
}

当左右子树都为空的时候，直接删除就行，但是要注意父节点的指针置为NULL，要不然就是野指针了，知道什么奇奇怪怪的东西就不太好了~~~左（右）子树为空时直接将父节点指针指向对应右（左）子树即可，然后删除节点，至于左右子树都为非空，则需要找到右子树的后继，然后调换数值，后续就按照删除一个左子树为空的节点即可，几种情况分别如下图所示，只列举了右子树为空的情况，其中parent表示被删除节点的父节点指针，child表示要删除节点指针：
左右都为空：

右为空：

左右均非空：


接下直接上遍历代码了，包括递归和非递归的，非递归要借助栈来实现，剩下的感觉只要理解中序遍历就行了，剩下两个都是在它的基础上改了一点：

void BSTTree::preOrderWithRecur(struct Node *node){
    if(node){
        std::cout<< node->val<<"  ";
        preOrderWithRecur(node->left);
        preOrderWithRecur(node->right);
    }
}
void BSTTree::inOrderWithRecur(struct Node *node){
    if(node){
        inOrderWithRecur(node->left);
        std::cout<<node->val<<"  ";
        inOrderWithRecur(node->right);
    }
}
void BSTTree::postOrderWithRecur(struct Node *node){
    if(node){
        postOrderWithRecur(node->left);
        postOrderWithRecur(node->right);
        std::cout<<node->val<<"  ";
    }
}
void BSTTree::preOrderNon_Recur(struct Node *node){
    std::stack<struct Node*> s;
    struct Node *p = node;
    while(p || !s.empty()){
        while(p){
            std::cout<<p->val<<"  ";
            s.push(p);
            p=p->left;
        }
        p = s.top(), s.pop();
        if(p->right) p = p->right;
        else p = NULL;
    }
}
void BSTTree::inOrderNon_Recur(struct Node *node){
    std::stack<struct Node*> s;
    struct Node *p = node;
    while(p || !s.empty()){
        while(p){
            s.push(p);
            p=p->left;
        }
        p = s.top(), s.pop();
        std::cout<<p->val<<"  ";
        if(p->right) p = p->right;
        else p = NULL;
    }
}
void BSTTree::postOrderNon_Recur(struct Node *node){
    std::stack<struct Node*> s;
    struct Node *p = node;
    while(p || !s.empty()){
        while(p){
            s.push(p);
            p=p->left;
        }
        p = s.top(), s.pop();
        std::cout<<p->val<<"  ";
        if(!s.empty() && p == s.top()->left) p = s.top()->right;
        else p = NULL;
    }
}

还请各位看官老爷多提宝贵意见~~~