欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C++如何實(shí)現(xiàn)二叉樹(shù)鏈表

 更新時(shí)間:2022年07月26日 08:46:16   作者:develbai  
這篇文章主要介紹了C++如何實(shí)現(xiàn)二叉樹(shù)鏈表,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教

C++二叉樹(shù)鏈表

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(); ? ? ? ? ? ? ? ? ? ? ? ? //創(chuàng)建樹(shù)
? ? ~Tree(); ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //銷(xiāo)毀樹(shù)
? ? Node *SearchNode(int nodeIndex); ? ? ? ? ? ? ? ? ? ? ? ?//根據(jù)索引尋找節(jié)點(diǎn)
? ? bool AddNode(int nodeIndex, int direction, Node *pNode); ? ? ? ? ? ?//添加節(jié)點(diǎn)
? ? bool DeleteNode(int nodeIndex, Node *pNode); ? ? ? ? ? ?//刪除節(jié)點(diǎn)
? ? 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++二叉樹(shù)轉(zhuǎn)鏈表

給定一個(gè)二叉樹(shù),將該二叉樹(shù)就地(in-place)轉(zhuǎn)換為單鏈表。單鏈表中節(jié)點(diǎn)順序?yàn)槎鏄?shù)前序遍歷順序。

如果不要求就地轉(zhuǎn)鏈表,可以借助于一個(gè)vector將二叉樹(shù)轉(zhuǎn)為鏈表。

代碼如下:

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

運(yùn)行結(jié)果:

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

因?yàn)橐缶偷貙⒍鏄?shù)轉(zhuǎn)為鏈表,因此不能借助于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;
}

運(yùn)行結(jié)果為:

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

以上為個(gè)人經(jīng)驗(yàn),希望能給大家一個(gè)參考,也希望大家多多支持腳本之家。

相關(guān)文章

  • 簡(jiǎn)單解讀C++中的虛函數(shù)

    簡(jiǎn)單解讀C++中的虛函數(shù)

    這篇文章主要介紹了C++中的虛函數(shù),在C++中,虛函數(shù)聯(lián)系到多態(tài)、多態(tài)聯(lián)系到繼承,因而虛函數(shù)是C++中的一大重要特性,需要的朋友可以參考下
    2016-04-04
  • C語(yǔ)言實(shí)現(xiàn)單鏈表的快速排序算法

    C語(yǔ)言實(shí)現(xiàn)單鏈表的快速排序算法

    大家好,本篇文章主要講的是C語(yǔ)言實(shí)現(xiàn)單鏈表的快速排序算法,感興趣的同學(xué)趕快來(lái)看一看吧,對(duì)你有幫助的話記得收藏一下
    2022-01-01
  • C++中的Lambda表達(dá)式及表達(dá)式語(yǔ)句

    C++中的Lambda表達(dá)式及表達(dá)式語(yǔ)句

    這篇文章主要介紹了C++中的Lambda表達(dá)式及表達(dá)式語(yǔ)句,表達(dá)式這個(gè)概念在C++中屬于比較細(xì)節(jié)的知識(shí)了,很多時(shí)候我們只用知道怎么用,對(duì)于編譯器內(nèi)部怎么處理我們并不關(guān)心;并且關(guān)于左值和右值這個(gè)概念,也是C++比較深的一個(gè)小知識(shí)點(diǎn),需要的朋友可以參考一下
    2021-12-12
  • 淺析C語(yǔ)言中的sizeof

    淺析C語(yǔ)言中的sizeof

    sizeof是C/C++中的一個(gè)操作符(operator),作用就是返回一個(gè)對(duì)象或者類(lèi)型所占的內(nèi)存字節(jié)數(shù)。返回值類(lèi)型為size_t,在頭文件stddef.h中定義
    2013-07-07
  • Qt串口通信開(kāi)發(fā)之QSerialPort模塊簡(jiǎn)單使用方法與實(shí)例

    Qt串口通信開(kāi)發(fā)之QSerialPort模塊簡(jiǎn)單使用方法與實(shí)例

    這篇文章主要介紹了Qt串口通信開(kāi)發(fā)之QSerialPort模塊簡(jiǎn)單使用方法與實(shí)例,需要的朋友可以參考下
    2020-03-03
  • 算法之排列算法與組合算法詳解

    算法之排列算法與組合算法詳解

    這篇文章主要介紹了算法之排列算法與組合算法詳解,本文以字典序法、遞歸法為例講解了排列算法、全組合算法等,需要的朋友可以參考下
    2014-08-08
  • 有關(guān)C++繼承與友元、繼承與類(lèi)型轉(zhuǎn)換詳解

    有關(guān)C++繼承與友元、繼承與類(lèi)型轉(zhuǎn)換詳解

    下面小編就為大家?guī)?lái)一篇有關(guān)C++繼承與友元、繼承與類(lèi)型轉(zhuǎn)換詳解。小編覺(jué)得挺不錯(cuò)的,現(xiàn)在就分享給大家,也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧
    2017-01-01
  • C++通過(guò)CryptoPP計(jì)算Hash值的過(guò)程詳解

    C++通過(guò)CryptoPP計(jì)算Hash值的過(guò)程詳解

    Crypto++ (CryptoPP) 是一個(gè)用于密碼學(xué)和加密的C++庫(kù),它是一個(gè)開(kāi)源項(xiàng)目,提供了大量的密碼學(xué)算法和功能,本文小編給大家介紹了C++通過(guò)CryptoPP計(jì)算Hash值的過(guò)程,文中通過(guò)代碼示例給大家介紹的非常詳細(xì),需要的朋友可以參考下
    2023-11-11
  • 一篇文章教你3分鐘如何發(fā)布Qt程序

    一篇文章教你3分鐘如何發(fā)布Qt程序

    這篇文章主要給大家介紹了關(guān)于教你3分鐘如何發(fā)布Qt程序的相關(guān)資料,文中通過(guò)實(shí)例代碼結(jié)束的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
    2020-08-08
  • C語(yǔ)言詳解如何實(shí)現(xiàn)順序棧

    C語(yǔ)言詳解如何實(shí)現(xiàn)順序棧

    順序棧,就是用一組地址連續(xù)的存儲(chǔ)單元來(lái)存放棧元素,然后用一個(gè)棧結(jié)構(gòu)去維護(hù)一個(gè)棧。在C中,可用動(dòng)態(tài)開(kāi)辟的數(shù)組去表示,維護(hù)的棧結(jié)構(gòu)需要有一個(gè)棧底和一個(gè)棧頂指針
    2022-04-04

最新評(píng)論