二叉树的一些基本操作

心已赠人 2022-06-18 10:21 167阅读 0赞

## 二叉树的创建 ##

二叉树创建的方式有很多种，可以根据先根遍历的序列和中根遍历的序列对二叉树进行创建，也可以给一个特定的先序序列对二叉树进行创建。用先根序列和中根序列创建二叉树，就是先根序列的第一个元素一定是树的根节点，然后再中根序列中找到这个根节点所在的位置，此位置的左边便是此树的左子树的中根遍历的序列，右边便是此树的右子树的中根遍历序列，用递归的思想就可以很简单的完成此树的创建，代码如下：

BtNode * CreateBtTree(char *pre, char *in, int n)
    {
        BtNode *s =NULL;
        if (n > 0)
        {
            s = BuyBtNode();
            s->data = pre[0];
            int pos = FindIndex(pre, in,n);
            s->leftchild = CreateBtTree(pre + 1, in, pos);
            s->rightchild = CreateBtTree(pre + pos + 1, in + pos + 1, n - pos - 1);
        }
        return s;
    }

根据一个先根 序列去创建一个二叉树，比如此序列：”ABC\#\#DE\#\#F\#\#G\#H\#\#”，遇到一个\#号就代表遇到了NULL，就不再继续，开始返回，同样用递归实现，代码如下：

//这里必须要使用引用，不然++p只是改变的本函数堆栈的指针 
    BtNode* CreateBinaryTree(char *&p)
    {
        if (p == NULL||*p=='#')
            return NULL;
        BtNode*node = BuyBtNode();
        node->data = p[0];
    
        node->leftchild = CreateBinaryTree(++p);
    
        node->rightchild = CreateBinaryTree(++p);
            return node;
    }

还有很多关于二叉树创建的方法，都差不多，这里不再赘述。

## 二叉树的遍历 ##

下面就是关于二叉树的遍历的问题，有先根遍历，中根遍历，后根遍历，他们使用的都是递归的思想，代码实现如下：

void InOderBtTree(BtNode*root)
    {
        if (root == NULL)
            return;
        InOderBtTree(root->leftchild);
        cout << root->data << " ";
        InOderBtTree(root->rightchild);
    }
    void PreOderBtTree(BtNode*root)
    {
        if (root == NULL)
            return;
        cout << root->data << " ";
        PreOderBtTree(root->leftchild);  
        PreOderBtTree(root->rightchild);
    }
    void LastOderBtTree(BtNode*root)
    {
        if (root == NULL)
            return;
        LastOderBtTree(root->leftchild);
        LastOderBtTree(root->rightchild);
        cout << root->data << " ";
    
    }

这里用的是递归的方法实现，下面是使用的是非递归的方式实现，但是要借助栈，代码如下：

void NicePreOderBtTree(BtNode*root)
    {
        if (root == NULL)
            return;
        stack<BtNode*> st;
        BtNode*p = root;
        while (p != NULL||!st.empty())
        {
            while (p != NULL)
            {
                cout << p->data << " ";
                st.push(p);
                p = p->leftchild;
            }
            p = st.top();
            st.pop();
            p = p->rightchild;
        }
        cout << endl;
    }
    
    void NiceInOderBtTree(BtNode *root)
    {
        if (root == NULL)
            return;
        stack<BtNode*> st;
        BtNode*p = root;
        while ( p != NULL || !st.empty())
        {
            while (p != NULL)
            {
                st.push(p);
                p = p->leftchild;
            }
            p = st.top();
            st.pop();
            cout << p->data << " ";
            p = p->rightchild;
        }
        cout << endl;
    }
    void NiceLastOderBtTree(BtNode*root)
    { 
        if (root == NULL)
            return;
        stack<BtNode*> st;
        BtNode*p = root;
        BtNode*tag = NULL;
        while (p != NULL || !st.empty())
        {
            while (p != NULL)
            {
                st.push(p);
                p = p->leftchild;
            }
            p = st.top();
            st.pop();
            if (p->rightchild == NULL || tag == p->rightchild)
            {
                cout << p->data << " ";
                tag = p;
                p = NULL;
            }
            else
            {
                st.push(p);
                p = p->rightchild;
            }
        }
        cout << endl;
    }

## 二叉树的节点个数 ##

计算二叉树的Size,即二叉树的节点个数，利用递归的思想，节点个数就等于左子树的节点个数加上右子树的节点个数加上本身的一个元素，如此重复就形成了递归，代码如下：

int GetSize(BtNode*root)
    {
        if (root == NULL)
            return 0;
        return GetSize(root->leftchild) + GetSize(root->rightchild) + 1;
    }

## 二叉树的深度 ##

二叉树的深度的计算方法和二叉树的节点个数的方法很相似，即左子树和右子树中最大的深度加一，使用递归实现代码如下：

int GetDepth(BtNode*root)
    {
        if (root == NULL)
            return 0;
        int left_depth = GetDepth(root->leftchild);
        int right_depth = GetDepth(root->rightchild);
        return left_depth > right_depth ? left_depth + 1 : right_depth+1;
    }

## 根据孩子找双亲 ##

遇到一个节点看齐左右孩子是否等于此孩子，若等于就将此节点返回，否则就先递归遍历左孩子，若左孩子没有找到，就再去遍历右孩子，如果都没有找到就返回NULL，递归代码实现如下：

BtNode * FindParent(BtNode *ptr, BtNode *child)
    {
        if (ptr == NULL || child == NULL || ptr == child)
            return NULL;
        if (ptr->leftchild == child || ptr->rightchild == child)
            return ptr;
        BtNode*p = FindParent(ptr->leftchild, child);
        if (p == NULL)
        {
            p = FindParent(ptr->rightchild, child);
        }
        return p;
    }

## 遍历第k层 ##

有左孩子右孩子就遍历其左右孩子，每遍历一层就k-1，当k==1时就打印，使用递归代码实现如下：

void Print_K_Item(BtNode *p, int k)
    {
        if (p == NULL || k == 0)
            return;
        if (k == 1)
            cout << p->data << " ";
        Print_K_Item(p->leftchild, k - 1);
        Print_K_Item(p->rightchild, k - 1);
    }

## 二叉树的销毁 ##

二叉树的销毁就是二叉树的后序遍历，之前是打印，销毁就是直接free就可以了，代码实现如下：

void Destory(BtNode*root)
    {
        if (root == NULL)
            return;
        Destory(root->leftchild);
        Destory(root->rightchild);
        free(root);
    }

欢迎批评指正！