树形结构是一种重要的非线性数据结构。其中树和二叉树最为常用，直观看来树是以分支关系定义的层次结构。树形结构是我们平时比较熟悉的，比如文件夹目录、公司组织关系等。在计算机领域也得到广泛的应用，编译程序就是以树来表示源程序的语法结构。
二叉树是一种特殊的树形结构，他的特点是每个节点至多只有两颗子树，并且，子树有左右之分，顺序不能颠倒。
树形结构里边还有很多的知识点，我不在这里做文字上的解释，这里只是针对二叉树的相关特点，用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_
#include<iostream>
using 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|--