企业网站asp源代码,大学生网站开发文档,dede个人网站,南昌有做网站的吗目录
1. 树概念及结构
1.1树概念
1.2树的表示
2. 二叉树概念及结构
2.1概念
2.2数据结构中的二叉树
2.3特殊的二叉树
2.4二叉树的存储结构
2.4.1顺序存储
2.4.2链式存储
2.5二叉树的性质
3. 二叉树顺序结构及概念
3.1二叉树的顺序结构
3.2堆的概念及结构
3.3堆的…目录
1. 树概念及结构
1.1树概念
1.2树的表示
2. 二叉树概念及结构
2.1概念
2.2数据结构中的二叉树
2.3特殊的二叉树
2.4二叉树的存储结构
2.4.1顺序存储
2.4.2链式存储
2.5二叉树的性质
3. 二叉树顺序结构及概念
3.1二叉树的顺序结构
3.2堆的概念及结构
3.3堆的实现
4. 二叉树链式结构及实现
4.1二叉树链式结构的遍历
4.2二叉树的链式实现 1. 树概念及结构
1.1树概念
树是一种非线性的数据结构它是由nn0个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树也就是说它是根朝上而叶朝下的。 节点的度一个节点含有的子树的个数称为该节点的度 如二叉树的图100节点的度为2叶节点度为0的节点称为叶节点 如二叉树的图2,7,3,25,1节点非终端节点或分支节点度不为0的节点 如二叉树的图100,19,36,17节点为分支节点双亲节点或父节点若一个节点含有子节点则这个节点称为其子节点的父节点 如二叉树的图100是19的父节点
我解释为什么有的地方叫双亲节点因为在实际世界中父亲节点有人会说它是男权为了避免纠纷就叫双亲节点但是我们一定要注意双亲节点不是指两个节点而是指一个。我们一般说父亲节点会便于我们理解孩子节点或子节点一个节点含有的子树的根节点称为该节点的子节点 如二叉树的图19是100的孩子节点兄弟节点具有相同父节点的节点互称为兄弟节点 如上图19、36是兄弟节点树的度一棵树中最大的节点的度称为树的度 如多叉树图树的度为5节点的层次从根开始定义起根为第1层根的子节点为第2层以此类推 树的高度或深度树中节点的最大层次 如上图树的高度为4堂兄弟节点深度相同父亲不同。如二叉树的图17的堂兄弟节点包括25,1不包括3节点的祖先从根到该节点所经分支上的所有节点包括父亲节点子孙以某节点为根的子树中任一节点都称为该节点的子孙。如二叉树图所有节点都是100的子孙森林由m棵互不相交的树的集合称为森林
1.2树的表示
多叉树的表示
typedef int DataType;
typedef struct TreeNode
{struct Node* firstChild1; //第一个孩子struct Node* pNextBrother; //兄弟节点DataType data;
}TNode;因为不知道节点的度是多少这种结构巧妙的解决结构体定义几个指针的问题 。 让4这个节点的brother指针指向它的兄弟5节点这样可以找到5节点然后5节点的bother指针指向6节点....依次下去可以把一层的节点都链接上 二叉树的表示
typedef int BTDataType
typedef struct BinaryTreeNode
{BTDataType data;//存储数据struct BinaryTreeNode* left;//指向它的左孩子struct BinaryTreeNode* right;//指向它的右孩子
}BTNode; 2. 二叉树概念及结构 2.1概念
一棵二叉树是结点的一个有限集合该集合或者为空或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。 二叉树的特点
每个结点最多有两棵子树即二叉树不存在度大于2的结点。二叉树的子树有左右之分其子树的次序不能颠倒。
2.2数据结构中的二叉树
包括五种树形结构1.空树 2.只有一个根节点 3.只有左树 4.只有右树 5.左右子树都存在 2.3特殊的二叉树
1.完全二叉树除了最后一层之外的其他层都是满的最后一层有数据的节点要从左到右连续的。当出现空节点之后右边不能有其他右数据的节点。 2.满二叉树 除了叶子节点其他节点的度都为2没有度为1的节点每一层都是满的 2.4二叉树的存储结构 2.4.1顺序存储连续的
用数组的形式来存储
会产生以下特性
leftchildparent*21(左孩子存储父亲节点的下标*21)
rightchildleftchild1parent*22;(右孩子存储父亲节点的下标*22
parentchild1/2 不管左右孩子都是这一条公式你可以自己看看存储在数组中的下标右孩子都是存储偶数的下标左孩子都是存储在奇数的下标。1再/2不会改变整数的部分。 2.4.2链式存储不连续的
二叉树的链式存储结构是指用链表来表示一棵二叉树即用链来指示元素的逻辑关系。
一般分为二叉链和三叉链 二叉链两个指针指向它的左右孩子。
三叉链不仅有两个指针指向它的孩子还多一个指针用来指向它的父亲节点。 // 二叉链struct BinaryTreeNode{struct BinTreeNode* Left; // 指向当前节点左孩子struct BinTreeNode* Right; // 指向当前节点右孩子BTDataType data; // 当前节点存储的值}// 三叉链struct BinaryTreeNode{struct BinTreeNode* Parent; // 指向当前节点的双亲struct BinTreeNode* Left; // 指向当前节点左孩子struct BinTreeNode* Right; // 指向当前节点右孩子BTDataType data; // 当前节点存储的值}2.5二叉树的性质 2.5.1 性质一
度为0的节点个数一定比度为2的节点个数多1在一些选择题会用到
如题 设Ni表示度为i的节点个数则节点总数 N N0 N1 N2 节点个数于节点边的关系 N个节点的树有N-1个边 边与度的关系N - 1 N1 2 * N2 故N0 N1 N2 - 1 N1 2 * N2 因此得N0 N2 1 回到原题N0 3N1 8可得N2 2。 因此答案是 3 8 2 13。 2.5.2 性质二
若规定根节点的层数为1具有n个结点的满二叉树的深度h log2(N1) (解析 是log以2 为底n1为对数)
2.5.3 性质三
若规定根节点的层数为1则一棵非空二叉树的第 i 层上最多有 2^i-1个 结点.
2.5.4 性质四
若规定根节点的层数为1则深度为h的二叉树的最大结点数是 n2^h -1个
2.5.5 性质五 对任何一棵二叉树, 如果度为0其叶结点个数为 , 度为2的分支结点个数为 ,则有 n0 n21注n0n21的意思就是在所有二叉树中度为0的节点个数永远比度为2的节点个数多一个。 3. 二叉树顺序结构及概念 3.1二叉树的顺序结构
普通的二叉树是不适合用数组来存储的因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事一个是数据结构一个是操作系统中管理内存的一块区域分段。 同名字但是性质完全不同 3.2堆的概念结构实现
里面包括堆的概念和用堆来实现的排序。
http://t.csdnimg.cn/n0qur 4. 二叉树链式结构
对于二叉树这个章节我们不学二叉树的增删查改 因为二叉树不是用来单纯的存储数据而是用来查找的
我们需要学二叉树的查找相关的知识
我们要学二叉树的前序遍历中序遍历后序遍历层序遍历个数高度第k层的节点个数查找x所在节点的指针查找二叉树中有没有x二叉树的销毁判断二叉树是否是完全二叉树。
1.前序遍历 先遍历根节点再左节点最后右节点
2.中序遍历 先遍历左节点再根节点最后右节点
3.后序遍历 先遍历左节点再右节点最后根节点
遍历我们需要用到递归先去到最深层然后遍历return到上一层重复下去。 A-B-D-H-NULL-NULL-D-I-NULL-NULL-D-B-E-J-NULL-NULL-C-F-K-NULL-NULL-G-NULL-NULL, 然后回到第一层出去。
中序后序同理。
我们需要想象出NULL节点才能便于理解。 if(rootNULL) { return; }//递归的返回条件 在这里我只找到了后序遍历的动态图。
前中后序都大同小异。 三种遍历的代码
//前序遍历
void PreOrder(BT* root)
{if (root NULL){printf(NULL );return;//在viod类型的函数进行递归想要返回上一层可以用 return; 用来终止函数的执行}printf(%d , root-val);PreOrder(root-left);PreOrder(root-right);
}//中序遍历
void InOrder(BT* root)
{if (root NULL){printf(NULL );return;}InOrder(root-left);printf(%d , root-val);InOrder(root-right);
}//后序遍历
void PostOrder(BT* root)
{if (root NULL){printf(NULL );return;}PostOrder(root-left);PostOrder(root-right);printf(%d , root-val);
} 查找二叉树的节点个数 递归左边返回左边的个数递归右边返回右边的个数11表示当前节点 int TreeSize(BT* root)
{if (root NULL){return 0;//如果是NULL返回0递归的返回条件}return TreeSize(root-left) TreeSize(root-right) 1;
}
二叉树的高度 int TreeHight(BT* root)
{if (root NULL){return 0;}int leftsize TreeHight(root-left);int rightsize TreeHight(root-right);return leftsize rightsize ? leftsize 1 : rightsize 1;
} 第k层的节点个数: 遍历的过程k--当k1时说明到达那一层如果有节点就返回1如果出现NULL就返回0了。 int TreeKsize(BT* root,int k)
{assert(k 0); if (root NULL) return 0;if (k 1) return 1;int tleft TreeKsize(root-left, k - 1);int tright TreeKsize(root-right, k - 1);return tlefttright;
}查找x所在的位置并且返回节点的地址 因为返回的时候是返回到上一层所以需要用变量保存指针判断返回出来的是否为空如果不为空就会一直回到上一层。直到出去。 //查找x所在节点的指针
BT* TreeNodeFind(BT* root, int x)
{if (root NULL) return NULL;if (root-val x){return root;}BT* ret1TreeNodeFind(root-left, x);if (ret1){return ret1;}BT* ret2TreeNodeFind(root-right, x);if (ret2){return ret2;}return NULL;
}查找二叉树中有没有x 如果找到了就返回true然后因为是或||一个为真就返回true //查找二叉树中有没有x
bool TreeSearch(BT* root, int x)
{if(rootNULL) return fasle;if(root-valx) return true;return TreeSearch(root-left,x)||TreeSearch(root-right,x);
} 判断二叉树是否是完全二叉树 插入到队列中完全二叉树的特性是前面都是有数据的节点后面都是NULL。 不满足的话就不是完全二叉树。 所以写代码的时候可以利用这一点特性把数据存储到队列中利用层序遍历来判断。 bool BinaryTreeComplete(BT* root)
{// 层序遍历QueueNode pq;QueueInit(pq);if (root)//不是空树的时候{QueuePush(pq, root);//插入当前节点的值到队列中}while (!QueueEmpty(pq)){BT* tmp QueueFront(pq);QueuePop(pq);if(tmp NULL) break;//一层一层的出和进所以不可能遇到空的时候非空还没有进QueuePush(pq, tmp-left);QueuePush(pq, tmp-right);}while (!QueueEmpty(pq)){if (QueueFront(pq) NULL){QueuePop(pq);}if (QueueFront(pq)){QueueDestry(pq);return false;}}return true;QueueDestry(pq);
}
二叉树链式结构全部的代码
Binary_tree.h(二叉树的头文件) #includestdlib.h
#includestdio.h
#includeassert.h
#includestdbool.h
#includemath.h
typedef struct Binary_tree
{struct Binary_tree* left;struct Binary_tree* right;int val;
}BT;BT* BTCreate(int val);//前序中序后序个数高度第k层的节点个数
void PreOrder(BT* root);
void InOrder(BT* root);
void PostOrder(BT* root);
int TreeSize(BT* root);
int TreeHight(BT* root);
int TreeKsize(BT* root,int k);//查找x所在节点的指针
BT* TreeNodeFind(BT* root, int x);//查找二叉树中有没有x
bool TreeSearch(BT* root, int x);//二叉树的销毁
void BTDestory(BT* root);// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BT* root);// 层序遍历
void BinaryTreeLevelOrder(BT* root); Binary_tree.c二叉树的源文件
#define _CRT_SECURE_NO_WARNINGS 1
#includeBinary_tree.h
#includeQueue.h
BT* BTCreate(int val)
{BT* NewNode (BT*)malloc(sizeof(BT));if (NewNode NULL){perror(malloc error);exit(-1);}NewNode-left NULL;NewNode-right NULL;NewNode-val val;return NewNode;
}void PreOrder(BT* root)
{if (root NULL){printf(NULL );return; //在viod类型的函数进行递归想要返回上一层可以用 return; 用来终止函数的执行}printf(%d , root-val);PreOrder(root-left);PreOrder(root-right);
}
void InOrder(BT* root)
{if (root NULL){printf(NULL );return;}InOrder(root-left);printf(%d , root-val);InOrder(root-right);
}
void PostOrder(BT* root)
{if (root NULL){printf(NULL );return;}PostOrder(root-left);PostOrder(root-right);printf(%d , root-val);
}
int TreeSize(BT* root)
{if (root NULL){return 0;}return TreeSize(root-left) TreeSize(root-right) 1;
}
int TreeHight(BT* root)
{if (root NULL){return 0;}int leftsize TreeHight(root-left);int rightsize TreeHight(root-right);return leftsize rightsize ? leftsize 1 : rightsize 1;
}int TreeKsize(BT* root,int k)
{assert(k 0); if (root NULL) return 0;if (k 1) return 1;int tleft TreeKsize(root-left, k - 1);int tright TreeKsize(root-right, k - 1);return tlefttright;
}//查找x所在节点的指针
BT* TreeNodeFind(BT* root, int x)
{if (root NULL) return NULL;if (root-val x){return root;}BT* ret1TreeNodeFind(root-left, x);if (ret1){return ret1;}BT* ret2TreeNodeFind(root-right, x);if (ret2){return ret2;}return NULL;
}//查找节点在不在
bool TreeSearch(BT* root, int x)
{if (root NULL) return false;if (root-val x) return true;return TreeSearch(root-left, x) TreeSearch(root-right, x);// 这个符号是判断是真还是假
}void BTDestory(BT* root)
{if (root NULL){return;}BTDestory(root-left);BTDestory(root-right);free(root);
}// 判断二叉树是否是完全二叉树包括满二叉树完全二叉树
//完全二叉树特征非空 空
//普通的二叉树非空 空 非空...
bool BinaryTreeComplete(BT* root)
{// 层序遍历QueueNode pq;QueueInit(pq);if (root)//不是空树的时候{QueuePush(pq, root);//插入当前节点的值到队列中}while (!QueueEmpty(pq)){BT* tmp QueueFront(pq);QueuePop(pq);if(tmp NULL) break;//一层一层的出和进所以不可能遇到空的时候非空还没有进QueuePush(pq, tmp-left);QueuePush(pq, tmp-right);}while (!QueueEmpty(pq)){if (QueueFront(pq) NULL){QueuePop(pq);}if (QueueFront(pq)){QueueDestry(pq);return false;}}return true;QueueDestry(pq);
}// 层序遍历
void BinaryTreeLevelOrder(BT* root)//循环
{QueueNode pq;QueueInit(pq);if (root){QueuePush(pq, root);//插入当前节点的值到队列中}while (!QueueEmpty(pq)){BT* tmp QueueFront(pq);QueuePop(pq);printf(%d ,tmp-val);if (tmp-left ! NULL){QueuePush(pq, tmp-left);}if (tmp-right ! NULL){QueuePush(pq, tmp-right);}}printf(\n);QueueDestry(pq);} 队列的头文件
#pragma once
#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.h
typedef struct Binary_tree* QDataType;//节点的指针
typedef struct QueueNode
{QDataType data;struct Queue* next;
}QueueNode;typedef struct Queue
{QueueNode* head;QueueNode* tial;
}Queue;//初始化和销毁
void QueueInit(Queue* pq);
void QueueDestry(Queue* pq);//插入
void QueuePush(Queue* pq,QDataType x);//删除
void QueuePop(Queue* pq);//读取队头的数据
QDataType QueueFront(Queue* pq);//读取队尾的数据
QDataType QueueBreak(Queue* pq);//读取队列的数据个数
int QueueSize(Queue* pq);//判断队列是否为空
bool QueueEmpty(Queue* pq);
队列的源文件
#define _CRT_SECURE_NO_WARNINGS 1
#includeQueue.h
//初始化和销毁
void QueueInit(Queue* pq)
{assert(pq);pq-head pq-tial NULL;
}
void QueueDestry(Queue* pq)
{assert(pq);QueueNode* cur pq-head;while (cur){QueueNode* next cur-next;free(cur);cur next;}pq-head pq-tial NULL;
}//插入
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QueueNode* tmp(QueueNode*)malloc(sizeof(QueueNode));if (tmp NULL){perror(malloc error);exit(-1);}tmp-data x;tmp-next NULL;if (pq-head NULL){pq-head pq-tial tmp;}else{pq-tial-next tmp;pq-tial tmp;}
}//删除
void QueuePop(Queue* pq)
{assert(pq);assert(pq-head);if (pq-head pq-tial){pq-head pq-tial NULL;}else{QueueNode* tmp pq-head-next;free(pq-head);pq-head tmp;}
}//读取队头的数据
QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq-head);return pq-head-data;
}//读取队尾的数据
QDataType QueueBreak(Queue* pq)
{assert(pq);assert(pq-head);return pq-tial-data;
}//读取队列的数据个数
int QueueSize(Queue* pq)
{assert(pq);int count 0;QueueNode* cur pq-head;while (cur){cur cur-next;count;}return count;
}//判断队列是否为空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq-head NULL;
}
