怎么做网站账号注册机,wordpress 防分析,电子商务网站开发的基本流程包括,深圳市房屋管理局官方网站目录 一. 树的概念
二. 访问树的方法
1. 左孩子右兄弟法
2. 双亲表示法
3. 顺序表存孩子的指针#xff08;孩子表示法#xff09; 三. 二叉树
1. 二叉树的定义
2. 特殊二叉树
3. 二叉树的性质
4. 存储方式
四. 二叉树的前中后序遍历
1. 前序遍历
2. 中序遍历
3. …目录 一. 树的概念
二. 访问树的方法
1. 左孩子右兄弟法
2. 双亲表示法
3. 顺序表存孩子的指针孩子表示法 三. 二叉树
1. 二叉树的定义
2. 特殊二叉树
3. 二叉树的性质
4. 存储方式
四. 二叉树的前中后序遍历
1. 前序遍历
2. 中序遍历
3. 后序遍历
4.完整代码 一. 树的概念 树是一种非线性的数据结构它是由n(n0)个有限节点组成的一个具有层次关系的集合。将其称为树是因为其看起来像一颗翻转的树(根朝上叶朝下)。最上面的节点是一个特殊的节点称之为根节点。根节点没有前驱结点除根节点外其余节点被分成M(M0)个互不相交的集合T1、T2、T3……、Tm。其中每一个集合Ti(1im)又是一颗结构与树类似的字数。每棵子树的根节点有且只有一个前驱可以有0个或多个后继因此树是递归定义的 不能出现多个节点指向同一节点的情况(如上图) 1. 节点的度一个节点链接了多少子节点度就为多少2.叶结点或终端节点度为0的节点不为0就为分支节点和非终端节点如上图E、F、G、C、H等 3. 双亲节点或父节点 若一个节点含有子节点称此节点为其子节点的父节点如上图A为B\C\D的父节点4. 孩子节点或子节点一个节点含有的子树的根节点称为该节点的子节点B\C\D为A的子节点5. 兄弟节点具有相同父节点的节点互相称为兄弟节点如上图B\C\D互为兄弟节点6. 树的度一棵树中最大节点的度称为树的度如上图树的度为3 7. 节点的层次 从根开始定义起根为第一层根的子结点为第二层以此类推8. 树的高度书中节点的最大层次如上图树的高度为39.堂兄弟节点双亲在同一层的节点互为堂兄弟如上图E和H互为堂兄弟节点10. 节点的祖先从根到该节点所经分支上的所有节点上图中AB是E\F\G的祖先11. 子孙以某节点为根的子树中任意一个节点都称为该节点的子孙。上图中所有节点都是A的子孙 12. 森林 由m(m0)棵互不相交的树的集合称为森林
二. 访问树的方法 用一下方法来表示上图中的树
1. 左孩子右兄弟法 链接方式如下图所示 2. 双亲表示法
让每个节点记住其父节点的位置。存储数据元素的节点由两部分组成1.存储数据元素 2. 存储父节点位置的字段
数组下标节点名称双亲的下标0A-1(根节点特殊处理)1B02C03D14E15F16G27H48I4
3. 顺序表存孩子的指针孩子表示法
由链表和顺序表混合实现
节点定义1.每个节点包含两部分数据域来存储数据另一部分为孩子链表指针指向一个链表
2. 定义一个顺序表用来定义存储所有节点的一个数组
3. 定义孩子链表包含 数据data和指向下一个孩子链表节点的指针next
结果图如下 三. 二叉树
1. 二叉树的定义
二叉树每个节点最多有两个子节点被称为左子树和右子树。所有的二叉树都分为三部分根左子树右子树
2. 特殊二叉树
1 满二叉树一个二叉树每层的节点数都达到最大值如果有k层节点树为2的k次方-1就是满二叉树,如下图所示 即为满二叉树
2完全二叉树树的高度是h前h-1层都是满的最后一层不满在最后一层从左往右都是连续的满二叉树是特殊的完全二叉树缺0个节点如下图所示
、
即为完全二叉树
3. 二叉树的性质
1 若规定根节点层数为1一颗非空二叉树最多有2的h-1次方个节点h为深度
2根节点层数为1深度为h的二叉树最大节点个数为2的n次方-1(满二叉树)
3任何一个二叉树度为0其叶节点个数为N0度为2的分支节点个数为N2则有N0N21
4若规定根节点层数为1具有n个节点的满二叉树的深度hlogN1底数为2
4. 存储方式
分别为用链表存储和用数组存储
用数组存储的话可以通过双亲节点与子节点下标间的映射关系来存储二叉树
我们这里用链表来实现
typedef int TreeType;
typedef struct Tree
{TreeType a;struct Tree* left;struct Tree* right;
}Tree;
四. 二叉树的前中后序遍历
1. 前序遍历
先输出根节点再输出左子树再输出右子树
递归实现
void PrevOrder(Tree* root)
{if (root NULL){printf(NULL );return;}printf(%d , root-a);//根PrevOrder(root-left);//左子树PrevOrder(root-right);//柚子树
}
非递归方法实现前序遍历需要用到栈以及栈的插入删除初始化判空等功能中序后序遍历同上
void PrevOrder2(Tree* root)
{assert(root);ST s;StackInit(s);Tree* p root;while (p||!StackEmpty(s)){if (p ! NULL){printf(%d , p-a);//输出根StackPush(s,p);//将根存进去p p-left;//往左子树走}else//左子树走到头{p StackTop(s);StackPop(s);p p-right;//若此节点还有右子树就执行上面的输出操作若还是空就来继续pop节点}}
}
2. 中序遍历
先打印输出左子树再输出根节点再输出右子树
递归实现
void InOrder(Tree* root)//中序遍历
{if (root NULL){printf(NULL );return;}InOrder(root-left);//左子树printf(%d , root-a);//根InOrder(root-right);//柚子树
}
非递归实现
void InOrder2(Tree* root)
{assert(root);ST s;StackInit(s);Tree* p root;while (p || !StackEmpty(s)){if (p ! NULL){StackPush(s, p);//先存节点先进去的后出来p p-left;//找最左边的节点}else//到最左边了{p StackTop(s);printf(%d , p-a);//输出最左边值StackPop(s);p p-right;//往右走看有没有节点}}
}
3. 后序遍历
先打印输出左子树再右子树再输出根节点
递归代码
void PostOrder(Tree* root)
{if (root NULL){printf(NULL );return;}PostOrder(root-left);//左子树PostOrder(root-right);//柚子树printf(%d , root-a);//根
}
非递归代码
void PostOrder2(Tree* root)
{assert(root);ST s;StackInit(s);Tree* p root;Tree* k root;while (p || !StackEmpty(s)){while (p ! NULL){StackPush(s, p);p p-left;//直接走到最左边}p StackTop(s);//if (p-rightp-right!k)//看是否有右子树{p p-right;//往右走循环开始后又会走到此节点的最左边}else{printf(%d , p-a);k p;//将右子树记录下来否则会死循环p NULL;//将p置为空否则循环开始会再次走到最左边StackPop(s);}}
}
4.完整代码
typedef int TreeType;typedef struct Tree
{TreeType a;struct Tree* left;struct Tree* right;
}Tree;typedef Tree* StackType;typedef struct Stack
{StackType* a;int Top;int capacity;
}ST,*pS;void StackInit(pS pst)
{assert(pst);pst-a NULL;pst-capacity 0;pst-Top 0;
}
void BuyNode(pS pst)
{int newcapacity pst-capacity 0 ? 4 : pst-capacity * 2;StackType* tmp (StackType*)realloc(pst-a, sizeof(StackType) * newcapacity);if (tmp NULL){perror(relloc fail);return;}pst-a tmp;pst-capacity newcapacity;
}
void StackPush(pS pst, StackType data)
{assert(pst);if (pst-Top pst-capacity){BuyNode(pst);}pst-a[pst-Top] data;pst-Top;
}void StackPop(pS pst)
{assert(pst);pst-Top--;//数组里的值不用改再添加数据会覆盖掉
}StackType StackTop(pS pst)
{assert(pst);return pst-a[pst-Top - 1];
}bool StackEmpty(pS pst)
{assert(pst);return pst-Top 0;
}void PrevOrder(Tree* root)
{if (root NULL){printf(NULL );return;}printf(%d , root-a);//根PrevOrder(root-left);//左子树PrevOrder(root-right);//柚子树
}
void PrevOrder2(Tree* root)
{assert(root);ST s;StackInit(s);Tree* p root;while (p||!StackEmpty(s)){if (p ! NULL){printf(%d , p-a);//输出根StackPush(s,p);//将根存进去p p-left;//往左子树走}else//左子树走到头{p StackTop(s);StackPop(s);p p-right;//若此节点还有右子树就执行上面的输出操作若还是空就来继续pop节点}}
}
void InOrder(Tree* root)//中序遍历
{if (root NULL){printf(NULL );return;}InOrder(root-left);//左子树printf(%d , root-a);//根InOrder(root-right);//柚子树
}
void InOrder2(Tree* root)
{assert(root);ST s;StackInit(s);Tree* p root;while (p || !StackEmpty(s)){if (p ! NULL){StackPush(s, p);//先存节点先进去的后出来p p-left;//找最左边的节点}else//到最左边了{p StackTop(s);printf(%d , p-a);//输出最左边值StackPop(s);p p-right;//往右走看有没有节点}}
}
void PostOrder(Tree* root)
{if (root NULL){printf(NULL );return;}PostOrder(root-left);//左子树PostOrder(root-right);//柚子树printf(%d , root-a);//根
}
void PostOrder2(Tree* root)
{assert(root);ST s;StackInit(s);Tree* p root;Tree* k root;while (p || !StackEmpty(s)){while (p ! NULL){StackPush(s, p);p p-left;//直接走到最左边}p StackTop(s);//if (p-rightp-right!k)//看是否有右子树{p p-right;//往右走循环开始后又会走到此节点的最左边}else{printf(%d , p-a);k p;//将右子树记录下来否则会死循环p NULL;//将p置为空否则循环开始会再次走到最左边StackPop(s);}}
}int main()
{Tree* a (Tree*)malloc(sizeof(Tree));a-a 2;a-left NULL;a-right NULL;Tree* b (Tree*)malloc(sizeof(Tree));b-a 3;b-left NULL;b-right NULL;Tree* c (Tree*)malloc(sizeof(Tree));c-a 1;c-left NULL;c-right NULL;Tree* d (Tree*)malloc(sizeof(Tree));d-a 5;d-left NULL;d-right NULL;Tree* e (Tree*)malloc(sizeof(Tree));e-a 6;e-left NULL;e-right NULL;Tree* f (Tree*)malloc(sizeof(Tree));f-a 8;f-left NULL;f-right NULL;a-left b;a-right c;b-left d;b-right e;d-right f;//PrevOrder2(a);//InOrder(a);//InOrder2(a);//PostOrder(a);PostOrder2(a);//int size 0;//printf(%d , size);//printf(\n%d \n, TreeSize(a));//printf(\n%d \n, TreeLeafSize(c));return 0;
} 这篇就到这里啦~
希望能给你带来一些帮助 (๑′ᴗ‵๑) Lᵒᵛᵉᵧₒᵤ❤
