二叉树的实现c++资源-CSDN文库

共13个文件

pdb：2个

h：2个

dsp：1个

5星 · 超过95%的资源需积分: 3 179 浏览量 2008-12-14 22:11:01 上传评论收藏 367KB RAR 举报

二叉树是一种重要的数据结构，它在计算机科学中有着广泛的应用，如文件系统、编译器、图形算法等。在C++中实现二叉树，我们需要理解二叉树的基本概念和操作，包括如何创建节点、如何进行遍历以及如何进行插入和删除操作。让我们了解二叉树的基本定义。二叉树是由节点（或称为顶点）组成的有限集合，每个节点最多有两个子节点，通常称为左子节点和右子节点。根节点是没有任何父节点的节点，而叶节点是没有子节点的节点。非叶节点可以有零个、一个或两个子节点。在C++中，我们可以用类来表示二叉树的节点。一个简单的二叉树节点类可能包含三个属性：存储数据的`data`、指向左子节点的指针`left`和指向右子节点的指针`right`。例如： ```cpp class Node { public: int data; Node* left; Node* right; Node(int value) : data(value), left(nullptr), right(nullptr) {} }; ``` 接下来，我们来看如何实现二叉树的创建。通常，我们可以通过递归的方式插入节点来构建二叉树。插入操作基于特定的规则，比如按升序或降序插入。以下是一个简单的按值插入节点的例子： ```cpp Node* insert(Node* root, int value) { if (root == nullptr) { return new Node(value); } if (value < root->data) { root->left = insert(root->left, value); } else { root->right = insert(root->right, value); } return root; } ``` 对于二叉树的遍历，有三种主要方法：前序遍历、中序遍历和后序遍历。这些遍历方式用于访问树的所有节点。 - 前序遍历（根-左-右）：首先访问根节点，然后遍历左子树，最后遍历右子树。 - 中序遍历（左-根-右）：先遍历左子树，然后访问根节点，最后遍历右子树。 - 后序遍历（左-右-根）：先遍历左右子树，然后访问根节点。下面是一些示例函数，用于实现这三种遍历方式： ```cpp void preOrder(Node* node) { if (node != nullptr) { std::cout << node->data << " "; preOrder(node->left); preOrder(node->right); } } void inOrder(Node* node) { if (node != nullptr) { inOrder(node->left); std::cout << node->data << " "; inOrder(node->right); } } void postOrder(Node* node) { if (node != nullptr) { postOrder(node->left); postOrder(node->right); std::cout << node->data << " "; } } ``` 二叉树的删除操作是相对复杂的，因为删除节点可能影响到其子节点的链接。删除节点时要考虑多种情况，如删除的节点是否有子节点、只有一个子节点还是有两个子节点。以下是一个简化的删除操作示例，仅处理没有子节点或有一个子节点的情况： ```cpp Node* deleteNode(Node* root, int value) { if (root == nullptr) return root; if (value < root->data) { root->left = deleteNode(root->left, value); } else if (value > root->data) { root->right = deleteNode(root->right, value); } else { // Case 1: No child if (root->left == nullptr && root->right == nullptr) { delete root; root = nullptr; } // Case 2: One child else if (root->left == nullptr) { Node* temp = root; root = root->right; delete temp; } else if (root->right == nullptr) { Node* temp = root; root = root->left; delete temp; } // Case 3: Two children else { Node* temp = findMin(root->right); root->data = temp->data; root->right = deleteNode(root->right, temp->data); } } return root; } // Find the minimum value node in a subtree Node* findMin(Node* node) { while (node->left != nullptr) { node = node->left; } return node; } ``` 以上代码涵盖了二叉树的基本操作，包括创建、插入、遍历和删除。实际应用中，可能需要对这些基本操作进行扩展，以满足特定需求，例如平衡二叉树（如AVL树和红黑树）、搜索二叉树等。理解并熟练掌握二叉树的这些基本概念和操作是学习更复杂数据结构和算法的基础。通过实践和深入研究，你可以进一步提升在C++中设计和实现高效二叉树解决方案的能力。

资源推荐

资源详情

资源评论

收起资源包目录

.rar （13个子文件）

二叉树2

main.cpp 3KB

Binary_tree.dsp 4KB

Binary_tree.dsw 547B

Binary_tree.h 6KB

Debug

vc60.pdb 116KB

Binary_tree.exe 540KB

main.obj 272KB

Binary_tree.pdb 1.06MB

Binary_tree.ncb 73KB

Binary_tree.opt 48KB

Binary_tree.plg 256B

Node.h 488B

二叉树1.txt 4KB

#include <iostream> using namespace std; //树结点类的实现 template<class Elem> class bintree { public: bintree(Elem dataVal,bintree* leftVal=NULL,bintree* rightVal=NULL) { data=dataVal; left=leftVal; right=rightVal; } bintree(bintree* leftVal=NULL,bintree* rightVal=NULL) { left=leftVal; right=rightVal; } bintree* GetLeft() { return left; } bintree* GetRight() { return right; } Elem GetVal() { return data; } void SetVal(Elem it) { data=it; } void SetLeft(bintree<Elem>* l) { left=l; } void SetRight(bintree<Elem>* r) { right=r; } bintree* left; bintree* right; Elem data; }; //树的类型实现。 template<class Elem> class SearchTree { public: SearchTree(Elem it) { init(it); } ~SearchTree() { DeleteTree(root); } void init(Elem); void DeleteTree(bintree<Elem>*); void InsertNode(bintree<Elem>*,Elem item); void PreOrder(bintree<Elem>*); bool Find(bintree<Elem>*,Elem); bintree<Elem>* GetRoot() { return root; } void InOrder(bintree<Elem>* T); void PostOrder(bintree<Elem>* T); private: bintree<Elem>* root; }; template<class Elem> void SearchTree<Elem>::init(Elem item) { root=new bintree<Elem>(item,NULL,NULL); } template<class Elem> void SearchTree<Elem>::DeleteTree(bintree<Elem>* T) { if(T!=NULL) { DeleteTree(T->GetLeft()); DeleteTree(T->GetRight()); delete T; } } //插入结点。 template<class Elem> void SearchTree<Elem>::InsertNode(bintree<Elem>* T,Elem item) { bintree<Elem>* pointer=NULL; if(T==NULL) { init(item); return; } else pointer=T; while(1) { if(pointer->GetVal()==item) return; else if(pointer->GetVal()>item) { if(pointer->GetLeft()==NULL) { pointer->left=new bintree<Elem>(item,NULL,NULL); return; } else pointer=pointer->left; } else { if(pointer->GetRight()==NULL) { pointer->right=new bintree<Elem>(item,NULL,NULL); return; } else pointer=pointer->right; } } } //前序递归遍历。 template<class Elem> void SearchTree<Elem>::PreOrder(bintree<Elem>*T) { if(T!=NULL) { cout<<T->GetVal()<<" "; PreOrder(T->GetLeft()); PreOrder(T->GetRight()); } } //二叉递归查找 template<class Elem> bool SearchTree<Elem>::Find(bintree<Elem>* T,Elem item) { if(T==NULL) return false; else if(T->GetVal()>item) return Find(T->left,item); else if(T->GetVal()<item) return Find(T->right,item); else { item=T->GetVal(); return true; } } //中序递归遍历。 template<class Elem> void SearchTree<Elem>::InOrder(bintree<Elem>*T) { if(T!=NULL) { InOrder(T->left); cout<<T->data<<" "; InOrder(T->right); } } //后序递归遍历。 template<class Elem> void SearchTree<Elem>::PostOrder(bintree<Elem>* T) { if(T!=NULL) { PostOrder(T->left); PostOrder(T->right); cout<<T->data<<" "; } } int main() { SearchTree<char> A('h');//先创建一个根结点。 char it; char item; bintree<char>* b; b=A.GetRoot(); cout<<"insert any number in the tree"<<endl; cout<<"when you enter '* 'is end!"<<endl; cin>>item; while(item!='*') { A.InsertNode(b,item); //连续插入结点。 cin>>item; } cout<<"PreOrder print all the number:"; A.PreOrder(b); cout<<endl; cout<<"inorder print:"; A.InOrder(b); cout<<endl; cout<<" PostOrder print:"; A.PostOrder(b); cout<<endl; cin>>it; if(A.Find(b,it)) cout<<"there is the same number!"; else cout<<"there isn't the number!"; return 0; }

评论收藏

内容反馈