登录 / 注册
开启思考
 
  • 推荐
  • 评论
  • 收藏

二叉树

2023-01-29    299次浏览

　【数据机构和算法】章节中的【二叉树】，一直都觉得比较难。

　　使用C++语言用类进行了封装，以便于今后学习！

 

　　首先，定义了二叉树的节点类

View Code 
// BinaryTreeNode.h: interface for the BinaryTreeNode class.
// 二叉树的节点 NODE
// 节点 、 左节点 、右节点
// 2011-12-13 chen ang
//////////////////////////////////////////////////////////////////////

#if !defined(AFX_BINARYTREENODE_H__C6FD71B8_0809_43C0_B6C3_E6B7B5B032D2__INCLUDED_)
#define AFX_BINARYTREENODE_H__C6FD71B8_0809_43C0_B6C3_E6B7B5B032D2__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

template<class T>
class BinaryTreeNode  
{
private:
    T                        m_element;        //节点数据域
    BinaryTreeNode<T>*        m_pLeft;        //左节点指针
    BinaryTreeNode<T>*        m_pRight;        //右节点指针
    BinaryTreeNode<T>*        m_pParent;        //父节点指针:使用三叉链表存储
public:
    //默认的构造函数
    BinaryTreeNode()
    {
        memset(&m_element, 0, sizeof(T));
        m_pLeft        = NULL;
        m_pRight    = NULL;
        m_pParent    = NULL;
    };        
    //析构函数            
    virtual ~BinaryTreeNode(){};            
    //传参的构造函数:二叉链表
    BinaryTreeNode(const T& element, BinaryTreeNode<T>* l=NULL, BinaryTreeNode<T>* r=NULL)
    {
        m_element    = element;
        m_pLeft        = l;
        m_pRight    = r;
        m_pParent    = NULL;
    };    
    //传参的构造函数:三叉链表
    BinaryTreeNode(const T& element, BinaryTreeNode<T>* p, BinaryTreeNode<T>* l=NULL, BinaryTreeNode<T>* r=NULL)
    {
        m_element    = element;
        m_pLeft        = l;
        m_pRight    = r;
        m_pParent    = p;
    };    
    //设置节点内容
    void SetValue(const T& element)
    {
        m_element = element;
    };
    //设置左节点指针
    void SetLeftChild(BinaryTreeNode<T>* l)
    {
        m_pLeft    = l;
    };
    //设置右节点指针
    void SetRightChild(BinaryTreeNode<T>* r)
    {
        m_pRight = r;
    };
    //设置父节点指针
    void SetParent(BinaryTreeNode<T>* p)
    {
        if (NULL == m_pParent)
        {
            m_pParent = p;
        }
    };
    //获取节点内容
    T GetValue() const
    {
        return m_element;
    };
    //获取节点内容
    void DisplayValue() const
    {
        cout<<GetValue()<<" ";
    };
    //获取左节点指针
    BinaryTreeNode<T>* GetLeftChild() const
    {
        return m_pLeft;
    };
    //获取右节点指针
    BinaryTreeNode<T>* GetRightChild() const
    {
        return m_pRight;
    };
    //获取父节点指针
    BinaryTreeNode<T>* GetParent() const
    {
        return m_pParent;
    };
    //重载赋值函数
    BinaryTreeNode<T>& operator=(const BinaryTreeNode<T>& node)
    {
        m_element    = node.m_element;
        m_pLeft        = node.m_pLeft;
        m_pRight    = node.m_pRight;
        m_pParent    = node.m_pParent;
    };
    //判断当前节点是否为叶节点:是则返回true, 否则返回false
    bool IsLeaf() const
    {
        if ((NULL == m_pLeft) && (NULL == m_pRight))
        {
            return true;
        }
        else
        {
            return false;
        };
    };
};

#endif // !defined(AFX_BINARYTREENODE_H__C6FD71B8_0809_43C0_B6C3_E6B7B5B032D2__INCLUDED_)
复制代码


　　其次：定义和实现了二叉树

View Code 
// BinaryTree.h: interface for the BinaryTree class.
// 二叉树
// 2011-12-13 chen ang
//////////////////////////////////////////////////////////////////////

#if !defined(AFX_BINARYTREE_H__E94D44AE_ADCE_4F3E_A731_699E58A76F6C__INCLUDED_)
#define AFX_BINARYTREE_H__E94D44AE_ADCE_4F3E_A731_699E58A76F6C__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

#include <stack>
#include "BinaryTreeNode.h"

template<class T>
class BinaryTree  
{
private:
    BinaryTreeNode<T>*        m_root;            //二叉树的根节点
public:
    //默认的构造函数
    BinaryTree()
    {
        //默认为空树
        m_root = NULL;
    };    
    //传参的构造函数
    BinaryTree(const T& element)
    {
        //只有根节点一个节点的树
        m_root = new BinaryTreeNode<T>(element);
    };
    //析构函数
    virtual ~BinaryTree(){};
    //判断二叉树是否为空:空返回true; 非空返回false.
    bool IsEmpty() const
    {
        if (NULL == m_root)
        {
            return true;
        }
        else
        {
            return false;
        }
    };
    //返回二叉树的根节点
    BinaryTreeNode<T>* GetRoot() const
    {
        return m_root;
    };
    //返回current结点的父结点
    BinaryTreeNode<T>* GetParent(BinaryTreeNode<T>* current)
    {
        if ((NULL == current) || (m_root == current))
        {
            return NULL;
        }

        stack<BinaryTreeNode<T>*> s_t;
        BinaryTreeNode<T>* temp = m_root;
        while(!s_t.empty() || temp)
        {
            if (temp)
            {
                s_t.push(temp);
                if (temp->GetLeftChild() == current || temp->GetRightChild() == current)
                {
                    return temp;
                }
                temp = temp->GetLeftChild();
            }
            else
            {
                temp = s_t.top();
                s_t.pop();
                temp = temp->GetRightChild();
            }
        }
        
        return NULL;
    };
    //返回current结点的左兄弟结点
    BinaryTreeNode<T>* GetLeftSibling(BinaryTreeNode<T>* current)
    {
        if (current)
        {
            BinaryTreeNode<T>* temp = GetParent(current);
            if ((NULL == temp) || (current == temp->GetLeftChild()))
            {
                return NULL;
            }
            else
            {
                return temp->GetLeftChild();
            }
        }
        else
        {
            return NULL;
        }
    };
    //返回current结点的右兄弟结点
    BinaryTreeNode<T>* GetRightSibling(BinaryTreeNode<T>* current)
    {
        if (current)
        {
            BinaryTreeNode<T>* temp = GetParent(current);
            if ((NULL == temp) || (current == temp->GetRightChild()))
            {
                return NULL;
            }
            else
            {
                return temp->GetRightChild();
            }
        }
        else
        {
            return NULL;
        }
    };
    //打印节点数据
    void DisplayValue(BinaryTreeNode<T>* node)
    {
        if (node)
        {
            cout<<"值等于"<<node->GetValue()<<endl;
        }
        else
        {
            cout<<"该节点为NULL!"<<endl;
        }
    }
    //概念: “周游”--系统地访问数据结构中的结点。每个结点都正好被访问到一次
    //二叉树的遍历:前序周游二叉树或其子树
    //二叉树抽象为以下共性: 所有二叉树都由【根节点或者子树的根节点】、 【左子树】、 【右子树】组成
    void PreOrder(BinaryTreeNode<T>* root)
    {
        //方法一：深度优先周游二叉树 (使用递归)
        if (NULL != root)
        {
            root->DisplayValue();                    //访问【根节点或者子树的根节点】
            PreOrder(root->GetLeftChild());            //访问【根节点或者子树的根节点】的左节点
            PreOrder(root->GetRightChild());        //访问【根节点或者子树的根节点】的右节点
        }
    };
    void PreOrderInStack(BinaryTreeNode<T>* root)
    {
        //方法二：非递归深度优先周游二叉树
        //    栈是实现递归的最常用的结构
        //    利用一个栈来记下尚待周游的结点或子树，以备以后访问。 
        stack<BinaryTreeNode<T>*> s_t;
        BinaryTreeNode<T>* temp = root;
        while (!s_t.empty() || temp)
        {
            if (temp)
            {
                temp->DisplayValue();                //访问【根节点或者子树的根节点】
                s_t.push(temp);                        //      【根节点或者子树的根节点】入栈
                temp = temp->GetLeftChild();        //转到【根节点或者子树的根节点】的左节点
            }
            else
            {
                temp = s_t.top();                    //回到【根节点或者子树的根节点】
                s_t.pop();                            //      【根节点或者子树的根节点】弹出栈
                temp = temp->GetRightChild();        //转到【根节点或者子树的根节点】的右节点
            }
        }
    }
    void PreOrderInStack1(BinaryTreeNode<T>* root)
    {
        //方法二：非递归深度优先周游二叉树
        //    栈是实现递归的最常用的结构
        //    利用一个栈来记下尚待周游的结点或子树，以备以后访问。 
        stack<BinaryTreeNode<T>*> s_t;
        s_t.push(NULL);
        
        BinaryTreeNode<T>* temp = root;
        while(temp)
        {
            temp->DisplayValue();
            if (temp->GetRightChild())
            {
                s_t.push(temp->GetRightChild());
            }
            if (temp->GetLeftChild())
            {
                temp = temp->GetLeftChild();
            }
            else
            {
                temp = s_t.top();
                s_t.pop();
            }
        }    
    }

    //二叉树的遍历:中序周游二叉树或其子树
    void InOrder(BinaryTreeNode<T>* root)
    {
        //方法一：深度优先周游二叉树 (使用递归)
        if (NULL != root)
        {
            InOrder(root->GetLeftChild());            //访问【根节点或者子树的根节点】的左节点
            root->DisplayValue();                    //访问【根节点或者子树的根节点】
            InOrder(root->GetRightChild());            //访问【根节点或者子树的根节点】的右节点
        }
    };
    void InOrderInStack(BinaryTreeNode<T>* root)
    {
        //方法二：非递归深度优先周游二叉树
        //    栈是实现递归的最常用的结构
        //    利用一个栈来记下尚待周游的结点或子树，以备以后访问。 
        stack<BinaryTreeNode<T>*> s_t;
        BinaryTreeNode<T>* temp = root;
        while (!s_t.empty() || temp)
        {
            if (temp)
            {
                s_t.push(temp);                        //      【根节点或者子树的根节点】入栈
                temp = temp->GetLeftChild();        //转到【根节点或者子树的根节点】的左节点
            }
            else
            {
                temp = s_t.top();                    //回到【根节点或者子树的根节点】
                s_t.pop();                            //      【根节点或者子树的根节点】弹出栈
                temp->DisplayValue();                //访问【根节点或者子树的根节点】的左节点
                temp = temp->GetRightChild();        //转到【根节点或者子树的根节点】的右节点
            }
        }
    }

    //二叉树的遍历:后序周游二叉树或其子树
    void PostOrder(BinaryTreeNode<T>* root)
    {
        //方法一：深度优先周游二叉树 (使用递归)
        if (NULL != root)
        {
            PostOrder(root->GetLeftChild());        //访问【根节点或者子树的根节点】的左节点
            PostOrder(root->GetRightChild());        //访问【根节点或者子树的根节点】的右节点
            root->DisplayValue();                    //访问【根节点或者子树的根节点】
        }
    };
    void PostOrderInStack(BinaryTreeNode<T>* root)
    {
        //方法二：非递归深度优先周游二叉树
        //    栈是实现递归的最常用的结构
        //    利用一个栈来记下尚待周游的结点或子树，以备以后访问。 
        cout<<"NULL"<<endl;
    }

    //二叉树的遍历:按层次周游二叉树或其子树
    void LevelOrder(BinaryTreeNode<T>* root)
    {
        // 使用队列
        deque<BinaryTreeNode<T>*>    d_t;
        BinaryTreeNode<T>*            temp;

        if (NULL != root)
        {
            d_t.push_back(root);                    //      【根节点或者子树的根节点】入队列尾部
        }

        while(!d_t.empty())
        {
            temp = d_t.front();                        //      【根节点或者子树的根节点】
            d_t.pop_front();                        //      【根节点或者子树的根节点】出队列前端
            temp->DisplayValue();                    //访问【根节点或者子树的根节点】

            if (temp->GetLeftChild())
            {
                d_t.push_back(temp->GetLeftChild());//      【根节点或者子树的根节点】的左节点入队列
            }

            if (temp->GetRightChild())
            {
                d_t.push_back(temp->GetRightChild());//      【根节点或者子树的根节点】的右节点入队列
            }
        } // end while
    };

    //删除二叉树或其子树
    void DeleteBinaryTree(BinaryTreeNode<T>* root)
    {
        //后序周游二叉树或其子树
        if (root)
        {
            DeleteBinaryTree(root->GetLeftChild());        //递归删除二叉树的左子树    
            DeleteBinaryTree(root->GetRightChild());    //递归删除二叉树的右子树
            delete root;                                //删除根节点
            root = NULL;
        }
    };
};

#endif // !defined(AFX_BINARYTREE_H__E94D44AE_ADCE_4F3E_A731_699E58A76F6C__INCLUDED_)
复制代码


　　最后，就是对二叉树进行数据录入，测试。

// 二叉树.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>

#include "BinaryTree.h"

using namespace std;

int main(int argc, char* argv[])
{
    //创建一个二叉树
    BinaryTree<int> bTree(0);

    //判断是否为空
    if (bTree.IsEmpty())
    {
        cout<<"binary tree is empty"<<endl;        
    }
    else
    {
        cout<<"binary tree is not empty"<<endl;
    }

    //二叉树中插入节点
    BinaryTreeNode<int>* pNode;
    //新建节点
    pNode = new BinaryTreeNode<int>(1);
    bTree.GetRoot()->SetLeftChild(pNode);
    pNode = new BinaryTreeNode<int>(2);
    bTree.GetRoot()->SetRightChild(pNode);
    pNode = new BinaryTreeNode<int>(3);
    (bTree.GetRoot()->GetLeftChild())->SetLeftChild(pNode);
    pNode = new BinaryTreeNode<int>(4);
    (bTree.GetRoot()->GetLeftChild())->SetRightChild(pNode);
    pNode = new BinaryTreeNode<int>(5);
    (bTree.GetRoot()->GetRightChild())->SetLeftChild(pNode);
    pNode = new BinaryTreeNode<int>(6);
    (bTree.GetRoot()->GetRightChild())->SetRightChild(pNode);
    //先序遍历
    cout<<endl<<"先序遍历:";
    bTree.PreOrder(bTree.GetRoot());
    cout<<endl<<"先序遍历(栈):";
    bTree.PreOrderInStack(bTree.GetRoot());
    //中序遍历
    cout<<endl<<"中序遍历:";
    bTree.InOrder(bTree.GetRoot());
    cout<<endl<<"中序遍历(栈):";
    bTree.InOrderInStack(bTree.GetRoot());
    //后序遍历
    cout<<endl<<"后序遍历:";
    bTree.PostOrder(bTree.GetRoot());

    //层次遍历
    cout<<endl<<"层次遍历:";
    bTree.LevelOrder(bTree.GetRoot());
    //获取父节点
    cout<<endl<<"获取父节点:";
    bTree.DisplayValue(bTree.GetParent(pNode));
    cout<<"获取左节点:";
    bTree.DisplayValue(bTree.GetLeftSibling(pNode));
    cout<<"获取右节点:";
    bTree.DisplayValue(bTree.GetRightSibling(pNode));
    //删除二叉树
    bTree.DeleteBinaryTree(bTree.GetRoot());
    cout<<endl;
    return 0;
}
复制代码


　　总结：测试结果，输出数据，截图。

　　

原文地址：https://www.cnblogs.com/Leo_wl/p/2289462.html
  相关知识


W3CAPI 在线教程 | 菜鸟教程_LOGO
以API的视角诠释计算机技术
W3CAPI 在线教程 | 菜鸟教程 © 2018 版权所有 / 豫ICP备18043494号-2
W3CAPI 在线教程 | 菜鸟教程_微信公众号
扫一扫关注官方微信公众号