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

C++二叉树链表
C++二叉树转链表

C++二叉树链表 【C++如何实现二叉树链表】Node.h

#ifndef NODE_H#define NODE_H#include 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 = https://www.it610.com/article/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 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 = https://www.it610.com/article/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 = https://www.it610.com/article/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 = https://www.it610.com/article/1; Node *e2 = new Node; e2->index = 2; e2->data = https://www.it610.com/article/2; Node *e3 = new Node; e3->index = 3; e3->data = https://www.it610.com/article/3; Node *e4 = new Node; e4->index = 4; e4->data = https://www.it610.com/article/4; Node *e5 = new Node; e5->index = 5; e5->data = https://www.it610.com/article/5; Node *e6 = new Node; e6->index = 6; e6->data = https://www.it610.com/article/6; Node *e7 = new Node; e7->index = 7; e7->data = https://www.it610.com/article/7; Node *e8 = new Node; e8->index = 8; e8->data = https://www.it610.com/article/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将二叉树转为链表。
代码如下：

#includestruct 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 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& 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。

#includestruct 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; }

运行结果为：