C++如何實(shí)現(xiàn)二叉樹(shù)鏈表
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è)參考,也希望大家多多支持腳本之家。
- C++使用遞歸和非遞歸算法實(shí)現(xiàn)的二叉樹(shù)葉子節(jié)點(diǎn)個(gè)數(shù)計(jì)算方法
- C++實(shí)現(xiàn)二叉樹(shù)非遞歸遍歷算法詳解
- C++二叉樹(shù)的前序中序后序非遞歸實(shí)現(xiàn)方法詳細(xì)講解
- C++二叉樹(shù)的創(chuàng)建及遍歷詳情
- C++鏈?zhǔn)蕉鏄?shù)深入分析
- C++簡(jiǎn)單又輕松建立鏈?zhǔn)蕉鏄?shù)流程
- C++超詳細(xì)講解樹(shù)與二叉樹(shù)
- C++實(shí)現(xiàn)二叉樹(shù)的堂兄弟節(jié)點(diǎn)查詢(xún)
相關(guān)文章
C語(yǔ)言實(shí)現(xiàn)單鏈表的快速排序算法
大家好,本篇文章主要講的是C語(yǔ)言實(shí)現(xiàn)單鏈表的快速排序算法,感興趣的同學(xué)趕快來(lái)看一看吧,對(duì)你有幫助的話記得收藏一下2022-01-01C++中的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-12Qt串口通信開(kāi)發(fā)之QSerialPort模塊簡(jiǎn)單使用方法與實(shí)例
這篇文章主要介紹了Qt串口通信開(kāi)發(fā)之QSerialPort模塊簡(jiǎn)單使用方法與實(shí)例,需要的朋友可以參考下2020-03-03有關(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-01C++通過(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