数据结构-树（树基本实现C++）
本文共 9008 字，大约阅读时间需要 30 分钟。
树形结构是一种重要的非线性数据结构。其中树和二叉树最为常用，直观看来树是以分支关系定义的层次结构。树形结构是我们平时比较熟悉的，比如文件夹目录、公司组织关系等。在计算机领域也得到广泛的应用，编译程序就是以树来表示源程序的语法结构。
二叉树是一种特殊的树形结构，他的特点是每个节点至多只有两颗子树，并且，子树有左右之分，顺序不能颠倒。
树形结构里边还有很多的知识点，我不在这里做文字上的解释，这里只是针对二叉树的相关特点，用C++分别实现基于数组和基于链表两种方式的二叉树，以及实现二叉树的三种遍历方式。
基于数组的二叉树基本实现：
class Tree{public: explicit Tree(int size, int* pRoot){ m_iSize = size; m_pTree = new int[m_iSize]; memset(m_pTree, 0, sizeof(int)*m_iSize); m_pTree[0] = *pRoot; } ~Tree() { delete[]m_pTree; m_pTree = NULL; } int* SearchNode(int index){ if (index<0 && index>m_iSize) { return NULL; } return &m_pTree[index]; } //direction 1:left 2:right bool AddNode(int index, int direction, int* pNode){ if (index<0 && index>m_iSize) { return false; } if (m_pTree[index] == 0) { return false; } if (index * 2 + direction > m_iSize) { return false; } m_pTree[index * 2 + direction] = *pNode; return true; } bool DeleteNode(int index, int* pNode){ if (index<0 && index>m_iSize) { return false; } *pNode = m_pTree[index]; m_pTree[index] = 0; return true; } void Traverse(){ for (int i = 0; i < m_iSize; i++) { cout << m_pTree[i] << " "; } cout << endl; }private: int* m_pTree; int m_iSize;}; 基于链表的二叉树实现：
#ifndef _CTREE_H_#define _CTREE_H_#includeusing namespace std;class TreeNode{public: int index; //坐标 char data; //数据 TreeNode *pLChild; //左节点 TreeNode *pRChild; //右节点 TreeNode *pParent; //父节点public: TreeNode() : index(0), data('0'), pLChild(NULL), pRChild(NULL), pParent(NULL) {} TreeNode(int iNodeIndex, char val) : index(iNodeIndex), data(val), pLChild(NULL), pRChild(NULL), pParent(NULL) {} ~TreeNode() { //if (pLChild) //{ // delete pLChild; // pLChild = NULL; //} //if (pRChild) //{ // delete pRChild; // pRChild = NULL; //} //if (pParent) //{ // delete pParent; // pParent = NULL; //} } //TreeNode(const TreeNode& node) //{ // index = node.index; // data = node.data; // delete pLChild; // if (node.pLChild) // { // pLChild = new TreeNode(node.pLChild->data, node.pLChild->index); // } // delete pRChild; // if (node.pRChild) // { // pRChild = new TreeNode(node.pRChild->data, node.pRChild->index); // } // delete pParent; // if (node.pParent) // { // pParent = new TreeNode(node.pParent->data, node.pParent->index); // } //} //TreeNode& operator=(const TreeNode& node) //{ // if (this == &node) // { // return *this; // } // index = node.index; // data = node.data; // delete pLChild; // if (node.pLChild) // { // pLChild = new TreeNode(node.pLChild->data, node.pLChild->index); // } // // delete pRChild; // if (node.pRChild) // { // pRChild = new TreeNode(node.pRChild->data, node.pRChild->index); // } // delete pParent; // if (node.pParent) // { // pParent = new TreeNode(node.pParent->data, node.pParent->index); // } // return *this; //} TreeNode* SearchNode(int iNodeIndex){ if (index == iNodeIndex) { return this; } TreeNode *temp = NULL; if (pLChild) { if (pLChild->index == iNodeIndex) { return pLChild; } else { temp = pLChild->SearchNode(iNodeIndex); if (temp) { return temp; } } } if (pRChild) { if (pRChild->index == iNodeIndex) { return pRChild; } else { temp = pRChild->SearchNode(iNodeIndex); if (temp) { return temp; } } } return NULL; } void DeleteNode(){ if (pLChild != NULL) { pLChild->DeleteNode(); } if (pRChild != NULL) { pRChild->DeleteNode(); } if (pParent != NULL) { if (this == pParent->pLChild) pParent->pLChild = NULL; if (this == pParent->pRChild) pParent->pRChild = NULL; } delete this; } //先序遍历 根左右 void PreOrderTraversal(){ cout << data << " "; if (pLChild) { pLChild->PreOrderTraversal(); } if (pRChild) { pRChild->PreOrderTraversal(); } } //中序遍历 左根右 void InOrderTraversal(){ if (pLChild) { pLChild->InOrderTraversal(); } cout << data << " "; if (pRChild) { pRChild->InOrderTraversal(); } } //后序遍历 左右根 void PostOrderTraversal(){ if (pLChild) { pLChild->PostOrderTraversal(); } if (pRChild) { pRChild->PostOrderTraversal(); } cout << data << " "; } //禁止拷贝、赋值private: TreeNode(const TreeNode& node); TreeNode& operator=(const TreeNode& node);};//基于链表的二叉树基本实现和遍历class CTree{public: CTree(TreeNode *pNode = NULL) { //创建树默认先创建根节点 m_pRoot = new TreeNode(); if (!m_pRoot) { throw "根节点申请内存失败"; return; } if (pNode) { m_pRoot->index = 0; m_pRoot->data = pNode->data; } else { m_pRoot->index = 0; m_pRoot->data = '0'; } } ~CTree() { m_pRoot->DeleteNode(); } TreeNode* SearchNode(int index){ return m_pRoot->SearchNode(index); } bool AddNode(int index, int direction, TreeNode *pNode){ if (!pNode) { cout << "插入失败！新增的节点值为空。" << endl; return false; } TreeNode *temp = SearchNode(index); if (!temp) { cout << pNode->data << "插入失败！找不到传入下标对应的父节点。" << endl; return false; } TreeNode *node = new TreeNode(); if (!node) { cout << pNode->data << "插入失败！新的节点申请内存失败。" << endl; return false; } node->index = pNode->index; node->data = pNode->data; node->pParent = temp; if (1 == direction) { temp->pLChild = node; } else if (2 == direction) { temp->pRChild = node; } else { cout << pNode->data << "插入失败！。direction参数错误：1为左节点，2为右节点" << endl; } return true; } bool DeleteNode(int index, TreeNode *pNode){ TreeNode *temp = SearchNode(index); if (!temp) { cout << "删除失败！找不到传入下标对应的节点。" << endl; return false; } if (pNode) { pNode->index = temp->index; pNode->data = temp->data; } temp->DeleteNode(); return true; } //先序遍历-递归 void Recursive_PreOrderTraversal(){ m_pRoot->PreOrderTraversal(); } //中序遍历-递归 void Recursive_InOrderTraversal(){ m_pRoot->InOrderTraversal(); } //后序遍历-递归 void Recursive_PostOrderTraversal(){ m_pRoot->PostOrderTraversal(); } //先序遍历-非递归 void PreOrderTraversal(){ int stackTop = -1; TreeNode* nodeStack[10]; TreeNode *pMove = /*new TreeNode(m_pRoot->index, m_pRoot->data)*/m_pRoot; while (stackTop != -1 || pMove) { while (pMove) { cout << pMove->data << " "; nodeStack[++stackTop] = pMove; pMove = pMove->pLChild; } if (stackTop != -1) { pMove = nodeStack[stackTop]; stackTop--; pMove = pMove->pRChild; } } } //中序遍历-非递归 void InOrderTraversal(){ int stackTop = -1; TreeNode* nodeStack[10]; TreeNode *pMove = /*new TreeNode(m_pRoot->index, m_pRoot->data)*/m_pRoot; while (stackTop != -1 || pMove) { // while (pMove) { nodeStack[++stackTop] = pMove; pMove = pMove->pLChild; } if (stackTop != -1) { pMove = nodeStack[stackTop--]; cout << pMove->data << " "; pMove = pMove->pRChild; } } } //后序遍历-非递归 void PostOrderTraversal(){ int stackTop = -1; TreeNode* nodeStack[10]; TreeNode* pMove = /*new TreeNode(m_pRoot->index, m_pRoot->data)*/m_pRoot; TreeNode* pLastVisit = NULL; while (pMove) { nodeStack[++stackTop] = pMove; pMove = pMove->pLChild; } while (stackTop != -1) { pMove = nodeStack[stackTop--]; if (pMove->pRChild == NULL || pMove->pRChild == pLastVisit) { cout << pMove->data << " "; pLastVisit = pMove; } else { nodeStack[++stackTop] = pMove; pMove = pMove->pRChild; while (pMove) { nodeStack[++stackTop] = pMove; pMove = pMove->pLChild; } } } }private: TreeNode *m_pRoot; //根节点};#endif // !_CTREE_H_
测试二叉树结构图：
测试主函数main.cpp实现：
int main(int argc, char**argv){ TreeNode nodeA(0, 'A'); TreeNode nodeB(1, 'B'); TreeNode nodeC(2, 'C'); TreeNode nodeD(3, 'D'); TreeNode nodeE(4, 'E'); TreeNode nodeF(6, 'F'); TreeNode nodeG(9, 'G'); CTree *tree = new CTree(&nodeA); tree->AddNode(0, 1, &nodeB); tree->AddNode(0, 2, &nodeC); tree->AddNode(1, 1, &nodeD); tree->AddNode(1, 2, &nodeE); tree->AddNode(2, 2, &nodeF); tree->AddNode(4, 1, &nodeG); cout << "递归遍历: " << endl; tree->Recursive_PreOrderTraversal(); cout << endl; tree->Recursive_InOrderTraversal(); cout << endl; tree->Recursive_PostOrderTraversal(); cout << endl; cout << "非递归遍历: " << endl; tree->PreOrderTraversal(); cout << endl; tree->InOrderTraversal(); cout << endl; tree->PostOrderTraversal(); cout << endl; delete tree; system("pause"); return 0;}
测试结果：
--|END|--
转载地址：http://peiii.baihongyu.com/
你可能感兴趣的文章
Vue中hasOwnProperty方法失效的解决方法
查看>>
JS中判断一个元素是否在数组中的方法
查看>>
Java四种整数数据类型的取值范围分别是多少
查看>>
Mysql日期相关函数date_sub()、date_add()、date_format()、str_to_date()、to_days()介绍
查看>>
Java基本数据类型与包装类型的区别
查看>>
Java读取本地json文件并将json文件中的内容转成json字符串
查看>>
Springboot项目去除自动配置的方法
查看>>
Java中Calendar类的介绍及使用
查看>>
Java中String类型与Date日期类型互相转换的方法
查看>>
JS获取7天后日期的方法
查看>>
Java中ArrayList初始化的4种方法
查看>>
Vue中格式化对比json串插件
查看>>
Java将Object类型对象转换为指定的实体类对象
查看>>
Mysql中不同字段类型对应的Java类型
查看>>
使用Gson判断两个Json字符串是否相等
查看>>
Mybatis中获取新添加记录的主键id且不受并发影响的方法
查看>>
Mybatis中使用selectKey标签得到新增数据的主键
查看>>
Java中ArrayList的删除元素方法总结
查看>>
Java判断集合中是否存在某个元素的方法
查看>>
Java中split()用法
查看>>