-
搜索节点的函数应该为： Node* Node::searchNode(int index) { if(this->index==index)return this; if(this->pLNode!=NULL) { if(this->pLNode->index==index)return this->pLNode; Node *temp=this->pLNode->searchNode(index); if(temp!=NULL)return temp; /* 如果不加这个判断if(temp!=NULL)而是直接return temp则会导致即使在左子树中没有找到下标为index的节点也会直接返回NULL，而不再进行右子树中的搜索。 */ } if(this->pRNode!=NULL) { if(this->pRNode->index==index)return this->pRNode; Node *temp=this->pRNode->searchNode(index); if(temp!=NULL)return temp; } return NULL; }查看全部
-
二叉树的链表实现 删除结点时要把它的子节点也删除了，否则将会造成内存泄漏（删除了该节点之后指向该节点后面节点的结点指针就没了，该节点后面的内存就无法找到，从而无法释放造成内存泄漏）查看全部
-
#include<stdlib.h> #include"Tree.h" #include<iostream> using namespace std; /******************************************************************** 【数据结构探险---树篇】 ***************************************************/ int main(void) { int root=3; Tree *pTree=new Tree(); Node *node1= new Node(); node1->index=1; node1->data=5; Node *node2= new Node(); node2->index=2; node2->data=8; Node *node3= new Node(); node3->index=3; node3->data=2; Node *node4= new Node(); node4->index=4; node4->data=6; Node *node5= new Node(); node5->index=5; node5->data=9; Node *node6= new Node(); node6->index=6; node6->data=7; pTree->AddNode(0,0,node1); pTree->AddNode(0,1,node2); pTree->AddNode(1,0,node3); pTree->AddNode(1,1,node4); pTree->AddNode(2,0,node5); pTree->AddNode(2,1,node6); cout<<"前序遍历"<<endl; pTree->PreorderTravers(); cout<<"中序遍历"<<endl; pTree->InorderTravers(); cout<<"后序遍历"<<endl; pTree->PostorderTravers(); delete pTree; pTree=NULL; system("pause"); return 0; }查看全部
-
#include<stdlib.h> #include"Tree.h" #include<iostream> using namespace std; /******************************************************************** 【数据结构探险---树篇】 Tree(int size,int *pRoot); //创建树 ~Tree(); //销毁树 int * SearchNode(int nodeindex);//搜索结点 bool AddNode(int nodeindex,int direction,int *pNode);//添加结点 bool DeleteNode(int nodeindex,int * pNode);//删除结点 void PreorderTravers();//前序遍历 void InorderTravers(); //中序遍历 void PostorderTravers();//后序遍历 -------------------------------------------------------------------- 二叉树--链表实现 (0) 左孩子索引=父节点索引*2+1 5(1) 8(2) 右孩子索引=父节点索引*2+2 2(3) 6(4) 9(5) 7(6) 前序遍历：根左右0134256 中序遍历：左根右3140526 后序遍历：左右根 3415620 **********************************************************************/ int main(void) { int root=3; Tree *pTree=new Tree(10,&root); delete pTree; pTree=NULL; system("pause"); return 0; }查看全部
-
#include"Tree.h" #include<iostream> using namespace std; Tree::Tree(int size) { m_iSize=size; m_pTree=new int[size]; for(int i=0;i<m_iSize;i++) { m_pTree[i]=0; } } Tree::~Tree() { delete []m_pTree; m_pTree=NULL; } int *Tree:: SearchNode(int nodeindex) { if(nodeindex<0 || nodeindex>=m_iSize) { return NULL; } if(m_pTree[nodeindex]==0) { return NULL; } return &m_pTree[nodeindex]; } bool Tree::AddNode(int nodeindex,int direction,int *pNode) { if(nodeindex<0 || nodeindex>=m_iSize || m_pTree[nodeindex]==0) { return false; } switch(direction) { case 0: if( nodeindex*2+1>=m_iSize || m_pTree[nodeindex*2+1]!=0) { return false; } m_pTree[nodeindex*2+1]=*pNode; break; case 1: if( nodeindex*2+2>=m_iSize || m_pTree[nodeindex*2+2]!=0) { return false; } m_pTree[nodeindex*2+2]=*pNode; break; } return true; } bool Tree::DeleteNode(int nodeindex,int * pNode) { if(nodeindex<0 || nodeindex>=m_iSize || m_pTree[nodeindex]==0) {查看全部
-
main.cpp: #include <iostream> #include "Tree.h" #include <stdlib.h> using namespace std; /* 二叉树（用链表表达） 结点要素：索引 数据 左孩子指针 右孩子指针 父结点指针 （头节点的父结点指针为NULL，叶结点的左右孩子结点指针为NULL） 索引： 数组表达的二叉树中的索引指的就是数组的下标 链表表达时，索引必须也是当前结点的一部分，所以需要用一个数据成元来表示索引 int tree[n] 3 5 8 2 6 9 7 数据： 此处用int 左孩子指针、右孩子指针：拿到一个结点时，可以通过其左孩子指针、右孩子指针分别访问其左孩子结点、右。 （0） 5（1） 8（2） 2（3） 6（4） 9（5）7（6） 前序遍历：（下标）0 1 3 4 2 5 6 中序遍历： 3140526 后序遍历：3415620 如果要在孩子结点挂载孩子，需要通过搜索找到孩子结点的索引，所以，查找结点是一个基本操作，通过头结点找到结点，再进行其他操作。 如果要删除结点，不仅删除一个结点，需要把其所有子结点和子结点的子结点全部删除 销毁树时，也需要通过指针一级一级地找到头结点一下的所有结点一一进行消除，否则造成内存的泄漏 */ int main() { Node *node1 = new Node(); node1->index = 1; node1->data = 5; Node *node2 = new Node(); node2->index = 2; node2->data = 8; Node *node3 = new Node(); node3->index = 3; node3->data = 2; Node *node4 = new Node(); node4->index = 4; node4->data = 6; Node *node5 = new Node(); node5->index = 5; node5->data = 9; Node *node6 = new Node(); node6->index = 6; node6->data = 7; Tree *tree = new Tree(); 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->PreorderTraversal(); tree->InorderTraversal(); // tree->PostorderTraversal(); return 0; }Tree.cpp: #include "Tree.h" #include "Node.h" #include <iostream> #include <stdio.h> using namespace std; Tree::Tree(){ m_pRoot = new Node();//头节点不放有意义的值，index为0； } 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; } 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==NULL,意思就是不要这个结点，删了不需要 pNode->data = temp->data; } //删除结点在树这个层面不太容易操作，所以在Node级进行操作 //对于Node来说，删除自己需要： // 1.把自己的子结点删除 // 2.看自己是父结点的左孩子还是右孩子，把父结点对应指针置为NULL，然后再自杀; temp->DeleteNode(); return true; } void Tree::PreorderTraversal() {//前序遍历,在Node中比在Tree中更容易实现 m_pRoot->PreorderTraversal(); } void Tree::InorderTraversal() {//中序遍历 m_pRoot->InorderTraversal(); } void Tree::PostorderTraversal() {//后序遍历 m_pRoot->PreorderTraversal(); }Tree.h: #ifndef INC_0210_TREE_H #define INC_0210_TREE_H #include "Node.h" #include <stdio.h> class Tree{ 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();//后序遍历 private: Node *m_pRoot; }; #endif //INC_0210_TREE_HNode.h: #include <stdio.h> #ifndef INC_0210_NODE_H #define INC_0210_NODE_H class Node{ public: Node(); Node *SearchNode(int nodeIndex); void DeleteNode(); void PreorderTraversal();//前序遍历 void InorderTraversal();//中序遍历 void PostorderTraversal();//后序遍历 //需要注意，bool不需要，因为在树这个类中已经找到结点类，无所谓找得到与否，所以也不需要nodeIndex。 //第二个参数也不需要了，在Tree中的删除函数已经取到了 int index; int data; Node *pLChild; Node *pRChild; Node *pParent; }; #endif //INC_0210_NODE_HNode.cpp: #include "Node.h" #include "Tree.h" #include <stdio.h> #include <iostream> using namespace std; Node::Node() { index = 0; data = 0; pLChild = NULL; pRChild = NULL; pParent = NULL; } Node *Node::SearchNode(int nodeIndex){//一个是Tree下面的SearchNode，一个是Node下面的SearchNode，功能基本相同 //在Node下面实现这个功能，这个功能将来被Tree这个类调用 if(this->index == nodeIndex){ return this;//返回当前这个结点 } Node *temp = NULL; 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() {//前序遍历,在Node中比在Tree中更容易实现 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; }查看全部 -
【树】节点的有限集合
【度】有几个子节点
【叶子】终端节点
【无序树】同一节点的几个子节点可以随便换顺序而不影响逻辑
【深度】：节点深度（不同层不一样）、树的深度（所有层里节点的最大深度）
【二叉树】所有节点的度都≤2
遍历：前序遍历、中序、后序（前中后是相对于二叉树的根来说的）
前（先访问根，再访问节点），中（左节点、根、右节点）、后（最后访问根）
用途：压缩软件-赫夫曼树、搜索-人机对战
查看全部 -
在树中，一个双亲节点有几个孩子节点，那么这个双亲节点的度就是几。查看全部
-
根左右，左根右，左右根查看全部
-
遍历（？）查看全部
-
二叉树--链表实现 (0) 左孩子索引=父节点索引*2+1 5(1) 8(2) 右孩子索引=父节点索引*2+2 2(3) 6(4) 9(5) 7(6) 前序遍历：根左右0134256 中序遍历：左根右3140526 后序遍历：左右根 3415620查看全部
-
#include"stdlib.h" #include "Node.h" Node::Node() { index=0; data=0; pLchild=NULL; pRchild=NULL; pParent=NULL; } Node *Node::SearchNode(int nodeindex) { if(this->index==nodeindex) { return this; } if(this->pLchild!=NULL) { if(this->pLchild->index==nodeindex) { return this->pLchild; } if(this->pRchild!=NULL) { if(this->pRchild->index==nodeindex) { return this->pRchild; } return NULL; } }查看全部
-
前序遍历：根左右：根>根（左）>左>右（左）>根（右）>左（右）>右
中序遍历：左根右：左>根（左）>右（左）>根>左（右）>根（右）>右
后序遍历：左右根：左>右（左）>根（左）>左（右）>右>根（右）>根
查看全部 -
对于数组表示的二叉树：简单遍历，无前中后序
函数：
创造函数和析构函数——创建和销毁树
SearchNode（Tree *pTree，int nodeIndex）：搜索节点，要指定数组下标
AddNode（Tree *pTree，int nodeIndex，int direction，Node *pNode）：指定往哪一个下标的节点上去添加节点；指定方向：添加的是左孩子还是右孩子；指定要添加的节点：把要添加的节点挂在指定的位置上（相对于根节点而言）
查看全部 -
树的节点的搜索：指定当前节点的索引（下标）即可找到对应的数据
查看全部
举报
0/150
提交
取消