C++如何实现二叉树链表

目录C++二叉树链表C++二叉树转链表C++二叉树链表Node.h#ifndefNODE_H#defineNODE_H#includeiostreamusingnamespacestd;cl...

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();              http://www.cppcns.com //前序遍历
  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, Njavascriptode *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;
TreejavascriptNode(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);
TreeNodewww.cppcns.com 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++如何实现二叉树链表

目录

C++二叉树链表

C++二叉树转链表

C++动态规划中关于背包问题讲解

C++回溯算法中组合的相关问题分析

C++回溯算法中子集问题分析探讨

详解C/C++如何获取路径下所有文件及其子目录的文件名

基于C++编写一个简单的服务器

详解C/C++如何获取路径下所有文件及其子目录的文件名

C++实现文件逐行读取与字符匹配的示例详解

VS Code 中安装运行、编写C语言程序的详细教程

C++预处理连接的示例详解

C++实现将数据写入Excel工作表的示例代码

C++动态规划中关于背包问题讲解

C++回溯算法中组合的相关问题分析

C++回溯算法中子集问题分析探讨

详解C/C++如何获取路径下所有文件及其子目录的文件名

基于C++编写一个简单的服务器

详解C/C++如何获取路径下所有文件及其子目录的文件名

C++实现文件逐行读取与字符匹配的示例详解

VS Code 中安装运行、编写C语言程序的详细教程

C++预处理连接的示例详解

C++实现将数据写入Excel工作表的示例代码