首页 ›互联网技术资讯›内容详情

C++怎么实现二叉树链表

蜗牛互联网技术资讯2022-07-271420

这篇文章主要介绍“C++怎么实现二叉树链表”，在日常操作中，相信很多人在C++怎么实现二叉树链表问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”C++怎么实现二叉树链表”的疑惑有所帮助！接下来，请跟着小编一起来学习吧！

C++二叉树链表

Node.h

#ifndef NODE_H
#define NODE_H
#include <iostream>
using namespace std;
class Node
{
public:
    Node();
    ~Node();
    Node *SearchNode(int nodeIndex);
    void DeleteNode();
    void PreordeTraverse();
    void InorderTraverse();
    void PostorderTraverse();
    int index;
    int data;
    Node *pLChild;
    Node *pRChild;
    Node *pParent;
private:
};
Node::Node()
{
    index = 0;
    data = 0;
    pLChild = NULL;
    pRChild = NULL;
    pParent = NULL;
}
Node::~Node()
{
}
Node *Node::SearchNode(int nodeIndex)
{
    Node *temp = NULL;
        if (this->index == nodeIndex)
        {
            return this;
        }
        if (this->pLChild != NULL)
        {
            if (this->pLChild->index == nodeIndex)
            {
                return this->pLChild;
            }
            else
            {
                temp = this->pLChild->SearchNode(nodeIndex);
                if (temp != NULL)
                {
                    return temp;
                }
            }
        }
        if (this->pRChild != NULL)
        {
            if (this->pRChild->index == nodeIndex)
            {
                return this->pRChild;
            }
            else
            {
                this->pRChild->SearchNode(nodeIndex);
                if (temp != NULL)
                {
                    return temp;
                }
            }
        }
    return NULL;
}
void Node::DeleteNode()
{
    if (this->pLChild != NULL)
    {
        this->pLChild->DeleteNode();
    }
    if (this->pRChild != NULL)
    {
        this->pRChild->DeleteNode();
    }
    if (this->pParent != NULL)
    {
        if (this->pParent->pLChild == this)
        {
            this->pParent->pLChild = NULL;
        }
        if (this->pParent->pRChild == this)
        {
            this->pParent->pRChild = NULL;
        }
    }
    delete this;
}
void Node::PreordeTraverse()
{
    cout << this->index << " " << this->data << endl;
    if (this->pLChild != NULL)
    {
        this->pLChild->PreordeTraverse();
    }
    if (this->pRChild != NULL)
    {
        this->pRChild->PreordeTraverse();
    }
}
void Node::InorderTraverse()
{
    if (this->pLChild != NULL)
    {
        this->pLChild->InorderTraverse();
    }
    cout << this->index << " " << this->data << endl;
    if (this->pRChild != NULL)
    {
        this->pRChild->InorderTraverse();
    }
}
void Node::PostorderTraverse()
{
    if (this->pLChild != NULL)
    {
        this->pLChild->PostorderTraverse();
    }
    if (this->pRChild != NULL)
    {
        this->pRChild->PostorderTraverse();
    }
    cout << this->index << " " << this->data << endl;
}
#endif // !NODE_H

Tree.h

#ifndef TREE_H
#define TREE_H
#include "Node.h"
#include <iostream>
using namespace std;
class Tree
{
public:
    Tree();                         //创建树
    ~Tree();                                           //销毁树
    Node *SearchNode(int nodeIndex);                        //根据索引寻找节点
    bool AddNode(int nodeIndex, int direction, Node *pNode);            //添加节点
    bool DeleteNode(int nodeIndex, Node *pNode);            //删除节点
    void PreordeTraverse();                             //前序遍历
    void InorderTraverse();                             //中序遍历
    void PostorderTraverse();                           //后序遍历
private:
    Node *m_pRoot;
};
Tree::Tree()
{
    m_pRoot = new Node();
}
Tree::~Tree()
{
    m_pRoot->DeleteNode();
}
Node *Tree::SearchNode(int nodeIndex)
{
    return m_pRoot->SearchNode(nodeIndex);
}
bool Tree::AddNode(int nodeIndex, int direction, Node *pNode)
{
    Node *temp = SearchNode(nodeIndex);
    if (temp != NULL)
    {
        Node *currentNode = new Node;
        if (currentNode == NULL)
        {
            return false;
        }
        currentNode->index = pNode->index;
        currentNode->data = pNode->data;
        currentNode->pParent = temp;
        if (direction == 0)
        {
            temp->pLChild = currentNode;
        }
        if (direction == 1)
        {
            temp->pRChild = currentNode;
        }
        return true;
    }
    return false;
}
bool Tree::DeleteNode(int nodeIndex, Node *pNode)
{
    Node *temp = SearchNode(nodeIndex);
    if (temp == NULL)
    {
        return false;
    }
    if (pNode != NULL)
    {
        pNode->data = temp->data;
    }
    temp->DeleteNode();
    return true;
}
void Tree::PreordeTraverse()
{
    m_pRoot->PreordeTraverse();
}
void Tree::InorderTraverse()
{
    m_pRoot->InorderTraverse();
}
void Tree::PostorderTraverse()
{
    m_pRoot->PostorderTraverse();
}
#endif

main.cpp

#include "Tree.h"
#include "Node.h"
int main()
{
    Tree *pTree = new Tree;
    Node *e1 = new Node;
    e1->index = 1;
    e1->data = 1;
    Node *e2 = new Node;
    e2->index = 2;
    e2->data = 2;
    Node *e3 = new Node;
    e3->index = 3;
    e3->data = 3;
    Node *e4 = new Node;
    e4->index = 4;
    e4->data = 4;
    Node *e5 = new Node;
    e5->index = 5;
    e5->data = 5;
    Node *e6 = new Node;
    e6->index = 6;
    e6->data = 6;
    Node *e7 = new Node;
    e7->index = 7;
    e7->data = 7;
    Node *e8 = new Node;
    e8->index = 8;
    e8->data = 8;
    pTree->AddNode(0, 0, e1);
    pTree->AddNode(0, 1, e2);
    pTree->AddNode(1, 0, e3);
    pTree->AddNode(1, 1, e4);
    pTree->AddNode(2, 0, e5);
    pTree->AddNode(2, 1, e6);
    pTree->AddNode(3, 0, e7);
    pTree->AddNode(4, 1, e8);
    //pTree->DeleteNode(2, NULL);
    pTree->PreordeTraverse();
    cout << endl;
    pTree->InorderTraverse();
    cout << endl;
    pTree->PostorderTraverse();
    delete pTree;
    system("pause");
    return 0;
}

C++二叉树转链表

给定一个二叉树，将该二叉树就地(in-place)转换为单链表。单链表中节点顺序为二叉树前序遍历顺序。

如果不要求就地转链表，可以借助于一个vector将二叉树转为链表。

代码如下：

#include<vector>
struct TreeNode
{
 int val;
 TreeNode* left;
 TreeNode* right;
 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution
{
public:
 Solution() {};
 ~Solution() {};
 void flatten(TreeNode * root)
 {
  std::vector<TreeNode*> node_vec;
  preorder(root,node_vec);
  for (int i = 1; i < node_vec.size(); i++)
  {
   node_vec[i - 1]->left = NULL;
   node_vec[i - 1]->right = node_vec[i];
  }
 }
private:
 void preorder(TreeNode* node, std::vector<TreeNode*>& node_vec)
 {
  if (!node)
  {
   return;
  }
  node_vec.push_back(node);
  preorder(node->left, node_vec);
  preorder(node->right, node_vec);
 }
};
int main()
{
 TreeNode a(1);
 TreeNode b(2);
 TreeNode c(5);
 TreeNode d(3);
 TreeNode e(4);
 TreeNode f(6);
 a.left = &b;
 a.right = &c;
 b.left = &d;
 b.right = &e;
 c.right = &f;
 Solution solve;
 solve.flatten(&a);
 TreeNode* head = &a;
 while (head)
 {
  if (head->left)
  {
   printf("Error\n");
  }
  printf("[%d]", head->val);
  head = head->right;
 }
 printf("\n");
 return 0;
}

运行结果：

[1][2][3][4][5][6]

因为要求就地将二叉树转为链表，因此不能借助于vector。

#include<vector>
struct TreeNode
{
 int val;
 TreeNode* left;
 TreeNode* right;
 TreeNode(int x) :val(x), left(NULL), right(NULL) {}
};
class Solution
{
public:
 Solution() {};
 ~Solution() {};
 void flatten(TreeNode* root)
 {
  TreeNode* last = NULL;
  preorder(root,last);
 }
private:
 void preorder(TreeNode* node, TreeNode* & last)
 {
  if (!node)
  {
   return;
  }
  if (!node->left&&!node->right)
  {
   last = node;
   return;
  }
  TreeNode* left = node->left;
  TreeNode* right = node->right;
  TreeNode* left_last =NULL;
  TreeNode* right_last = NULL;
  if (left)
  {
   preorder(left, left_last);
   node->left = NULL;
   node->right = left;
   last = left_last;
  }
  if (right)
  {
   preorder(right, right_last);
   if (left)
   {
    left_last->right = right;
   }
   last = right_last;
  }
 }
};
int main()
{
 TreeNode a(1);
 TreeNode b(2);
 TreeNode c(5);
 TreeNode d(3);
 TreeNode e(4);
 TreeNode f(6);
 a.left = &b;
 a.right = &c;
 b.left = &d;
 b.right = &e;
 c.right = &f;
 Solution solve;
 solve.flatten(&a);
 TreeNode* head = &a;
 while (head)
 {
  if (head->left)
  {
   printf("Error\n");
  }
  printf("[%d]", head->val);
  head = head->right;
 }
 printf("\n");
 return 0;
}

运行结果为：

[1][2][3][4][5][6]

到此，关于“C++怎么实现二叉树链表”的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注蜗牛博客网站，小编会继续努力为大家带来更多实用的文章！

免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：niceseo99@gmail.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
#c++
本文地址：http://www.vps90.com/vps/19570.html
版权声明：如无特殊标注，文章均为本站原创，转载时请以链接形式注明文章出处。

相关文章

评论

关于蜗牛120vps博客

蜗牛120博客

感谢大家的支持，欢迎交流讨论！
『蜗牛120博客』

  • 11591135阅读数
  • 143279评论数

最近发表

  • Python集合是什么及怎么创建
  • SpringBoot表单提交全局日期格式转换器如何实现
  • Go反向代理ReverseProxy解析的方法是什么
  • 日本服务器租用 站群服务器 onevps：新增（支付宝+中文网站）
  • 怎样才能挑选到适合的vps服务器
  • NLTK安装错误怎么解决
  • 香港云服务器仅10元一年？小成本实现企业级应用的最佳选择！
  • Vue中代码传送怎么实现
  • golang中怎么保证精度
  • 日本服务器租用 站群服务器 kvmla：日本/香港/新加坡，VPS直接8折优惠（+充值多送20%），独立服务器一律7.5折优惠（首月反300元）

    • 标签列表

    有免费节点资源，我们会通知你！加入纸飞机订阅群

    ×
    天气预报查看日历分享网页手机扫码留言评论Telegram