树(数据结构篇)

2024/10/24 8:19:19 来源：https://blog.csdn.net/hellmorning/article/details/139766192 浏览: 次关键词：树(数据结构篇)

数据结构之树

树

本篇讲的树也就是多叉树

普通树(多叉树)

概念：

树就是由根节点(父亲)分出多个分支节点(儿子)，然后分支又分出多个分支，我们将这种结构称为树,树也可以这么定义：一棵树由称作根的节点r以及0个或多个非空的(子)树T1，T2，T3…Tk组成，这些子树每一棵的根都被来自根r的一条有向的边所连接。
从递归定义中我们发现，一颗树是N个节点和N-1条边的集合，其中的一个节点叫做根。每条边都将某个节点连接到它的父亲，而除去根接待你外每一个节点都有一个父亲。没有子节点的节点叫做树叶(叶节点)，具有相同父节点称为兄弟节点。节点深度就是该节点到根节点的长度是多少，节点高度就是该节点到最近叶节点的长度。

代码:

//通过链表的形式，表头就是根节点，通过找到第一个子节点，就能找到其他的子节点。
struct treeNode{int data;treeNode* firstchild;    //用于指向该节点的第一个子节点treeNode* nextsibling;   //用于指向该节点的下一个兄弟节点
};treeNode* createNode(int data){auto p=new treeNode;p->data=data;p->firstchild=NULL;p->nextsibling=NULL;return p;
}//插入节点
void addChild(treeNode* &root,int data){treeNode* add=createNode(data);if(root==NULL){root=add;}else{if(root->firstchild==NULL){root->firstchild=add;}else{treeNode* p=root->firstchild;while(p->nextsibling!=NULL){p=p->nextsibling;}p->nextsibling=add;}}
}//先序查找
treeNode* preorderSearch(treeNode* root,int data){if(root==NULL){return NULL;}if(root->data==data){return root;}treeNode* res;res=preorderSearch(root->firstchild,data);if(res!=NULL){return res;}res=preorderSearch(root->nextsibling,data);if(res!=NULL){return res;}return NULL;
}//后序查找
treeNode* postorderSearch(treeNode* root,int data){if(root==NULL){return NULL;}treeNode* res;res=postorderSearch(root->firstchild,data);if(res!=NULL){return res;}res=postorderSearch(root->nextsibling,data);if(res!=NULL){return res;}if(root->data==data){return root;}return NULL;
}//删除节点
void del(treeNode* &root,int data){if(root==NULL){return NULL;}treeNode* p=NULL;treeNode* tail=root->firstchild;while(tail!=NULL){if(tail->data==data){if(p==NULL){root->firstchild=tail->nextsibling;}else{p->nextsibling=tail->nextsibling;}delete tail;return;}del(tail,data);p=tail;tail=tail->nextsibling;}return NULL;
}//先序遍历
void preorderprint(treeNode *root){if(root==NULL){return;}cout<<root->data<<" ";preorderprint(root->firstchild);preorderprint(root->nextsibling);
}//后序遍历
void postorderprint(treeNode* root){if(root==NULL){return;}postorderprint(root->firstchild);postorderprint(root->nextsibling);cout<<root->data<<" ";
}//清空树
void destroy(treeNode* root){if(root==NULL){return;}destroy(root->firstchild);destroy(root->nextsibling);delete root;
}