链表实现二叉树的原理其实和数组实现的原理大同小异，但是因为是链表的缘故，所以操作的灵活性要比数组更加好，难度也比数组更高。链表实现二叉树，多了一个很关键的东西，那就是遍历的方法：前序遍历、中序遍历和后序遍历。
课程要求：完成树的基本操作 1、树的创建和销毁 2、树中结点的搜索 3、树中结点的添加和删除 4、树中结点的遍历 Tree(); //创建树 ~Tree(); //销毁树 Node* SearchNode(int nodeindex); //根据索引寻找结点 bool AddNode(int nodeindex, int direction, Node* pNode); //添加结点 bool DeleteNode(int nodeindex, Node* pNode); //删除结点 void PreorderTraversal(); //前序遍历 void InorderTraversal(); //中序遍历 void PostorderTraversal(); //后序遍历 结点要素：索引 数据 左孩子指针 右孩子指针 父结点指针 前序遍历：0 1 3 4 2 5 6 (上到下) a e b c h q 中序遍历：3 1 4 0 5 2 6 (左到右) e a b h c q 后序遍历：3 4 1 5 6 2 0 (左右根) e b a h q c (0) a(1) c(2) e(3) b(4) h(5) q(6)
程序实现：
node.h
[cpp] view plain copy #ifndef _NODE_H #define _NODE_H class Node { public: Node(); Node* SearchNode(int nodeindex); void DeleteNode(); void PreorderTraversal(); //前序遍历 void InorderTraversal(); //中序遍历 void PostorderTraversal(); //后序遍历 int index; char data; Node* pLChild; Node* pRChild; Node* pParent; }; #endif node.cpp
[cpp] view plain copy #include "node.h" #include <iostream> using namespace std; Node::Node() { index = 0; data = ' '; pLChild = NULL; pRChild = NULL; pParent = NULL; } Node* Node::SearchNode(int nodeindex) { if(this->index == nodeindex) { return this; } Node *temp; 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 { temp = 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::PreorderTraversal() { cout<<this->index<<" "<<this->data<<endl; if(this->pLChild != NULL) { this->pLChild->PreorderTraversal(); } if(this->pRChild != NULL) { this->pRChild->PreorderTraversal(); } } void Node::InorderTraversal() { if(this->pLChild != NULL) { this->pLChild->InorderTraversal(); } cout<<this->index<<" "<<this->data<<endl; if(this->pRChild != NULL) { this->pRChild->InorderTraversal(); } } void Node::PostorderTraversal() { if(this->pLChild != NULL) { this->pLChild->PostorderTraversal(); } if(this->pRChild != NULL) { this->pRChild->PostorderTraversal(); } cout<<this->index<<" "<<this->data<<endl; } linktree.h
[cpp] view plain copy /*****************链表实现二叉树*********************/ #ifndef _LINKTREE_H #define _LINKTREE_H #include "node.h" class Tree { Node* m_pRoot; public: Tree(); //创建树 ~Tree(); //销毁树 Node* SearchNode(int nodeindex); //根据索引寻找结点 bool AddNode(int nodeindex, int direction, Node* pNode); //添加结点 bool DeleteNode(int nodeindex, Node* pNode); //删除结点 void PreorderTraversal(); //前序遍历 void InorderTraversal(); //中序遍历 void PostorderTraversal(); //后序遍历 }; #endif linktree.cpp
[cpp] view plain copy /*****************链表实现二叉树*********************/ #include "linktree.h" #include <iostream> using namespace std; Tree::Tree() //初始化这棵树 { m_pRoot = new Node(); } Tree::~Tree() { //DeleteNode(0, NULL); 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) { return false; } Node* node = new Node(); if(node == NULL) { return false; } node->index = pNode->index; node->data = pNode->data; node->pParent = temp; if(direction == 0) { temp->pLChild = node; } else if(direction == 1) { temp->pRChild = node; } return true; } 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::PreorderTraversal() { m_pRoot->PreorderTraversal(); } void Tree::InorderTraversal() { m_pRoot->InorderTraversal(); } void Tree::PostorderTraversal() { m_pRoot->PostorderTraversal(); }
main.cpp
[cpp] view plain copy #include "linktree.h" #include <iostream> using namespace std; int main() { Tree *tree = new Tree(); Node* node1 = new Node; node1->index = 1; node1->data = 'a'; Node* node2 = new Node; node2->index = 2; node2->data = 'c'; Node* node3 = new Node; node3->index = 3; node3->data = 'e'; Node* node4 = new Node; node4->index = 4; node4->data = 'b'; Node* node5 = new Node; node5->index = 5; node5->data = 'h'; Node* node6 = new Node; node6->index = 6; node6->data = 'q'; tree->AddNode(0, 0, node1); tree->AddNode(0, 1, node2); tree->AddNode(1, 0, node3); tree->AddNode(1, 1, node4); tree->AddNode(2, 0, node5); tree->AddNode(2, 1, node6); tree->DeleteNode(2, NULL); //tree->PreorderTraversal(); //tree->InorderTraversal(); tree->PostorderTraversal(); delete tree; return 0; }
