做网站网上接单,石家庄发布最新消息,建设一个网站的技术可行性研究,网络系统管理比赛以下内容源于慕课网的学习整理#xff0c;如有侵权#xff0c;请告知删除。 树存在概念中#xff0c;是对数组或者链表的一种操作方式的概念。 一、与树有关的一些基础概念
#xff08;1#xff09;树 有限节点的集合#xff1b; #xff08;2#xff09;度 某个节点的…以下内容源于慕课网的学习整理如有侵权请告知删除。 树存在概念中是对数组或者链表的一种操作方式的概念。 一、与树有关的一些基础概念
1树 有限节点的集合 2度 某个节点的直接孩子数目 3叶节点 终端节点 4祖先 所有在它之上的节点 5深度 节点的深度节点所处的位置树的深度整棵树的深度 6二叉树 所有节点的度都小于等于2 7二叉树的遍历 前中后是针对“根”来说的。 8作用实例 人机对战 二、二叉树的数组实现
1、换算公式 父节点下标*21得到父节点的左孩子节点的下标父节点下标*22得到父节点的右孩子节点的下标 2、示意图 括号里面表示的是索引或者说节点序号外面的是数据。慕课网中只是按照这个图来进行查找遍历查找、插入已经确定在哪个位置上出入了、删除删除后赋值为0等操作。 三、二叉树的链表实现
1、节点要素 数据左孩子指针右孩子指针父指针索引这里用来表征节点的序号 2、删除元素 要求把对应的子节点也删除掉也可能要求只删除该点然后该点的孩子节点指向该点的父节点 3、前序遍历根左右 4、中序遍历左根右
首先是左526然后是根0接着是右897
然后对526进行同样的操作即左是2根是5右是6则排序结果是256
同理对897进行同样的操作即左是9根是8右是7则排序结果是987
最后合成为256 0 987。 5、后序遍历左右根 首先是左526然后是右897接着是根0
然后对526进行同样的操作即左是2右是6根是5则排序结果是265
同理对897进行同样的操作即左是9右是7根是8则排序结果是978
最后合成为265 978 0。 6、编码实现
树类、节点类节点类包含五要素数据左孩子指针右孩子指针父指针索引这里用来表征节点的序号前序遍历中序遍历、后序遍历就调换相应的位置即可。对树的遍历操作落实在根节点调用遍历函数。
node.h #ifndef NODE_H
#define NODE_H
class Node{
public :Node();int index;int data;Node *pLNOde;Node *pRNode;Node *pParent;Node *SerchNode(int index);void deleteNode();void Preorder();void Midorder();void Postorder();
};
#endifnode.cpp#include Node.h
#include iostream
using namespace std;Node::Node()
{index0;data0;pLNOdeNULL;pRNodeNULL;pParentNULL;
};Node* Node::SerchNode(int index)
{Node *tempNULL;if (this-indexindex)return this;if (this-pLNOde!NULL){ tempthis-pLNOde-SerchNode(index);if (temp!NULL){return temp;}}if (this-pRNode!NULL){tempthis-pRNode-SerchNode(index);if (temp!NULL){return temp;}}return NULL;
};void Node::deleteNode()
{if(this-pLNOde!NULL) {this-pLNOde-deleteNode();}if (this-pRNode!NULL){this-pRNode-deleteNode();}if (this-pParent!NULL){if (this-pParent-pLNOdethis){this-pParent-pLNOdeNULL;}if (this-pParent-pRNodethis){this-pParent-pRNodeNULL;}}delete this;
};void Node::Preorder()
{coutthis-data this-indexendl;if (this-pLNOde!NULL){this-pLNOde-Preorder();}if (this-pRNode!NULL){this-pRNode-Preorder();}
};void Node::Midorder()
{if (this-pLNOde!NULL){this-pLNOde-Midorder();}coutthis-data this-indexendl;if (this-pRNode!NULL){this-pRNode-Midorder();}
};void Node::Postorder()
{if (this-pLNOde!NULL){this-pLNOde-Postorder();}if (this-pRNode!NULL){this-pRNode-Postorder();}coutthis-data this-indexendl;
};tree.h #ifndef Tree_H
#define Tree_H
#include Node.hclass Tree
{
public:Tree();~Tree();Node *SerchNode(int index);//查找索引为index的那个节点并返回指向该节点的指针bool addNode(int index,int direction,Node *node);//添加在索引为index的节点上添加一个节点node//左右方向由direction决定bool deleteNode(int index,Node *node);//删除void Preorder();//前序void Midorder();//中序void Postorder();//后序
private:Node *p_node;};#endiftree.cpp#include Tree.h
#include Node.h
#include iostream
using namespace std;Tree::Tree()
{p_nodenew Node();
};Tree::~Tree()
{deleteNode(0,NULL);//这里调用的是tree中的删除节点函数从根节点0开始
};Node *Tree::SerchNode(int index)
{return p_node-SerchNode(index);};bool Tree::deleteNode(int index,Node *node)
{Node *tempSerchNode(index);if (temp!NULL){if (node!NULL)//传入的Node可以为null。是null时表明不需要把要删除的节点的数据保存。{node-indextemp-index;node-datatemp-data;}temp-deleteNode();return true;}elsereturn false;
};bool Tree::addNode(int index,int direction,Node *node)
{Node *tempSerchNode(index);if (temp){Node *NewNodenew Node();if (NewNodeNULL){return false;}NewNode-datanode-data;NewNode-indexnode-index;if (direction0){temp-pLNOdeNewNode;NewNode-pParenttemp;}if (direction1){NewNode-pParenttemp;temp-pRNodeNewNode;}return true;}return false;
};void Tree::Preorder()
{p_node-Preorder();
}void Tree::Midorder()
{p_node-Midorder();
}void Tree::Postorder()
{p_node-Postorder();
}test.cpp#include Node.h
#include Tree.h
#include iostreamusing namespace std;
/*0(0)1(1) 2(2)5(3) 7(4) 6(5) 9(6)*/
int main()
{Tree *pnew Tree;//这里的p是指向根节点的指针Node *n2new Node;n2-data1;n2-index1;Node *n3new Node;n3-data2;n3-index2;Node *n4new Node;n4-data3;n4-index3;Node *n5new Node;n5-data4;n5-index4;Node *n6new Node;n6-data5;n6-index5;Node *n7new Node;n7-data6;n7-index6;Node *n8new Node;n8-data8;n8-index8;Node *n9new Node;n9-data9;n9-index9; Node *n10new Node;n10-data10;n10-index10;Node *n11new Node;n11-data11;n11-index11;p-addNode(0,0,n2);p-addNode(0,1,n3);p-addNode(1,0,n4);p-addNode(1,1,n5);p-addNode(2,0,n6);p-addNode(2,1,n7);
// p-addNode(4,0,n8);
// p-addNode(4,1,n9);
// p-addNode(6,0,n10);
// p-addNode(6,1,n11);Node *n18new Node;n18p-SerchNode(10);if (n18!NULL){coutindex:n18-indexendl;}//Node *n12new Node;//p-deleteNode(6,n12);p-Preorder();coutendl;p-Postorder();coutendl;p-Midorder();delete p;pNULL;system(pause);return 0;
}
