数据结构探险之树篇_技术笔记

董瘦瘦 2020-02-16

Node.cpp中的SearchNode(int nodeIndex)函数可以很简化，如下：
Node* Node::SearchNode(int nodeIndex)
{
if (this->index == nodeIndex)
return this;
if (this->pLChild != NULL)
if (this->pLChild->SearchNode(nodeIndex) != NULL)
return this->pLChild->SearchNode(nodeIndex);
if (this->pRChild != NULL)
return this->pRChild->SearchNode(nodeIndex);
return NULL;
}

0赞 · 0采集

孙三三 2020-02-13

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_H

Node.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_H

Node.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;
}

1赞 · 0采集

梦游病者 2019-10-23

NULL包含在stdio.h中

0赞 · 0采集
慕雪908267 2019-01-25

不会啊，我就是按老师的代码敲的 /************************************************************二叉树（链表表示）课程要求：完成二叉树的基本操作 1，树的创建和销毁 2，树中结点的搜索 3，树中结点的添加与删除 4，树中结点的遍历 Tree(); //创建树 ~Tree(); //销毁树 Node *SearchNode(Tree *pTree,int nodeindex); //根据索引寻找结点 bool AddNode(Tree *pTree,int nodeindex,int direction,Node *pNode); //添加结点 bool DeleteNode(Tree *pTree,int nodeindex,Node *pNode); //删除结点 void preorderTraverse(); //先序遍历二叉树 void InorderTraverse(); //中序遍历二叉树 void PosorderTraverse(); //后序遍历二叉树 结点要素：索引、数据、左孩子指针、右孩子指针、父结点指针 3(0) 5(1) 8(2) 2(3) 6(4) 9(5) 7(6) 那个direction是“0”时表示插入到左孩子，是“1”时表示插入到右孩子 先序遍历结果（根----左----右）0 1 3 4 2 5 6 中序遍历结果（左----根----右）3 1 4 0 5 2 6 后序遍历结果（左----右----根）3 4 1 5 6 2 0 *************************************************************/ #include<iostream>#include<stdio.h> using namespace std; class Node{public: Node();//构造函数 Node *SearchNode(int nodeindex); void DeleteNode(); void preorderTraverse(); //先序遍历二叉树 void InorderTraverse(); //中序遍历二叉树 void PosorderTraverse(); //后序遍历二叉树 int index; int data; Node *pLChild; Node *pRChild; Node *pParent; }; class Tree{public: Tree(); //创建树 ~Tree(); //销毁树 Node *SearchNode(int nodeindex); //搜索结点 bool AddNode(int nodeindex,int direction,Node *pNode); //添加结点 bool DeleteNode(int nodeindex,Node *pNode); //删除结点 void preorderTraverse(); //先序遍历二叉树 void InorderTraverse(); //中序遍历二叉树 void PosorderTraverse(); //后序遍历二叉树private: Node *m_pRoot; }; Node::Node(){ index=0; data=0; pLChild=NULL; pRChild=NULL; pParent=NULL; } Tree::Tree(){ m_pRoot=new Node();} Tree::~Tree(){ //DeleteNode(0,NULL);//方法一 m_pRoot->DeleteNode();//方法二 } Node *Node::SearchNode(int nodeindex){ 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(this->pRChild!=NULL) { if(this->pRChild->index==nodeindex) return this->pRChild; else temp=this->pRChild->SearchNode(nodeindex); if(temp!=NULL) return temp; } return NULL;} 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->data=temp->data; } temp->DeleteNode(); return true;} 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::preorderTraverse(){ cout << this->index << " " << this->data << endl; if(this->pLChild!=NULL) this->pLChild->preorderTraverse(); if(this->pRChild!=NULL) this->pRChild->preorderTraverse();} void Node::InorderTraverse(){ if(this->pLChild!=NULL) this->pLChild->InorderTraverse(); cout << this->index << " " << this->data << endl; if(this->pRChild!=NULL) this->pRChild->InorderTraverse();}void Node::PosorderTraverse(){ if(this->pLChild!=NULL) this->pLChild->PosorderTraverse(); if(this->pRChild!=NULL) this->pRChild->PosorderTraverse(); cout << this->index << " " << this->data << endl;} void Tree::preorderTraverse(){ m_pRoot->preorderTraverse();} void Tree::InorderTraverse(){ m_pRoot->InorderTraverse();} void Tree::PosorderTraverse(){ m_pRoot->PosorderTraverse();} 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); //printf("删除最后一个结点：\n"); //tree->DeleteNode(6,NULL); printf("删除中间某个结点：\n"); tree->DeleteNode(2,NULL);// printf("前序遍历的结果：\n");// tree->preorderTraverse(); // printf("中序遍历的结果：\n");// tree->InorderTraverse(); printf("后序遍历的结果：\n"); tree->PosorderTraverse(); delete tree; return 0;}

0赞 · 0采集
uanitz 2018-08-08

NULL定义在头文件stdio.h中

0赞 · 1采集
鹿鸣在深草 2018-03-15

删除失败：1.没添加好添加结点时，不仅要给要添加的位置添加左或右结点，也要指定被添加结点的父结点，不然可能会找不到该结点 2.搜索不到结点，递归调用继续往下搜索

0赞 · 0采集
骑鹤的猫 2017-08-27

搜索节点的函数应该为： 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; }

2赞 · 0采集
慕妹2098627 2017-08-24

可以将DeleteNode中的第二个实参定位NULL；省的定义；

截图
0赞 · 0采集
精慕门4947531 2016-11-04

#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; }

2赞 · 2采集

数据加载中...