做游戏网站的目地,有没有在家做的手工活网站,玉树商城网站建设,千博企业网站系统一.什么是树#xff1a;
树形结构是一层次的嵌套结构。一个树形结构的外层和内层有相似的结构#xff0c;所以这种结构多可以递归的表示。经典数据结构中的各种树状图是一种典型的树形结构#xff1a;一棵树可以简单的表示为根#xff0c;左子树#xff0c;右子树。左子树…一.什么是树
树形结构是一层次的嵌套结构。一个树形结构的外层和内层有相似的结构所以这种结构多可以递归的表示。经典数据结构中的各种树状图是一种典型的树形结构一棵树可以简单的表示为根左子树右子树。左子树和右子树又有自己的子树。 树的一些属性
1、结点Node表示树中的数据元素由数据项和数据元素之间的关系组成。在图中共有10个结点。
2、结点的度Degree of Node结点所拥有的子树的个数在图中结点A的度为3。
3、树的度Degree of Tree树中各结点度的最大值。在图5.1中树的度为3。
4、叶子结点Leaf Node度为0的结点也叫终端结点。在图5.1中结点E、F、G、H、I、J都是叶子结点。
5、分支结点Branch Node度不为0的结点也叫非终端结点或内部结点。在图5.1中结点A、B、C、D是分支结点。
6、孩子Child结点子树的根。在图中结点B、C、D是结点A的孩子。
7、双亲Parent结点的上层结点叫该结点的双亲。在图中结点B、C、D的双亲是结点A。
8、祖先Ancestor从根到该结点所经分支上的所有结点。在图中结点E的祖先是A和B。
9、子孙Descendant以某结点为根的子树中的任一结点。在图中除A之外的所有结点都是A的子孙。
10、兄弟Brother同一双亲的孩子。在图5.1中结点B、C、D互为兄弟。
11、结点的层次Level of Node从根结点到树中某结点所经路径上的分支数称为该结点的层次。根结点的层次规定为1其余结点的层次等于其双亲结点的层次加1。 [1]
12、堂兄弟Sibling同一层的双亲不同的结点。在图中G和H互为堂兄弟。
13、树的深度Depth of Tree树中结点的最大层次数。在图5.1中树的深度为3。 [1]
14、无序树Unordered Tree树中任意一个结点的各孩子结点之间的次序构成无关紧要的树。通常树指无序树。 [1]
15、有序树Ordered Tree树中任意一个结点的各孩子结点有严格排列次序的树。二叉树是有序树因为二叉树中每个孩子结点都确切定义为是该结点的左孩子结点还是右孩子结点。 [1]
16、森林Forestmm≥0棵树的集合。自然界中的树和森林的概念差别很大但在数据结构中树和森林的概念差别很小。从定义可知一棵树由根结点和m个子树构成若把树的根结点删除则树变成了包含m棵树的森林。当然根据定义一棵树也可以称为森林。
一些特殊的树
树中最特殊最经典的就是二叉树二叉树顾名思义就是只有两个分叉的树也就是度为二的树。
二叉树中又有俩个最为经典的树分别为完全二叉树和满二叉树。
一棵深度为k且有个结点的二叉树称为满二叉树。
如果对满二叉树的结点进行编号, 约定编号从根结点起, 自上而下, 自左而右。则深度为k的, 有n个结点的二叉树, 当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时, 称之为完全二叉树。
二.用c语言实现一颗树
要实现一颗树我们首先要先定义一个树的结构体 然后要确定我们树的基本功能 接着就是写完这些函数 #includeBinaryTree.hBTNode* BinaryTreeCreate(BTDataType* a, int* pi)
{if (a[*pi] #){(*pi);return NULL;}BTNode* root (BTNode*)malloc(sizeof(BTNode));root-data a[(*pi)];root-left BinaryTreeCreate(a, pi);root-right BinaryTreeCreate(a, pi);return root;
}void BinaryTreeDestory(BTNode* root)
{assert(root);if (root NULL)return;BinaryTreeDestory(root-right);BinaryTreeDestory(root-left);free(root);root NULL;
}int BinaryTreeSize(BTNode* root)
{if (root NULL)return 0;return BinaryTreeSize(root-left) BinaryTreeSize(root-right) 1;
}int BinaryTreeLeafSize(BTNode* root)
{if (root NULL)return 0;if (root-left NULL root-right NULL)return 1;return BinaryTreeLeafSize(root-left) BinaryTreeLeafSize(root-right);
}int BinaryTreeLevelKSize(BTNode* root, int k)
{if (root NULL)return 0;if (k 1)return 1;k--;return BinaryTreeLevelKSize(root-left,k) BinaryTreeLevelKSize(root-right,k);
}BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root NULL)return NULL;if (root-data x)return root;BTNode* leftfind BinaryTreeFind(root-left, x);if (leftfind ! NULL)return leftfind;BTNode* rightfind BinaryTreeFind(root-right, x);if (rightfind ! NULL)return rightfind;return NULL;
}void BinaryTreePrevOrder(BTNode* root)
{if (root){printf(%c, root-data);BinaryTreePrevOrder(root-left);BinaryTreePrevOrder(root-right);}
}void BinaryTreeInOrder(BTNode* root)
{if (root){BinaryTreeInOrder(root-left);printf(%c, root-data);BinaryTreeInOrder(root-right); }
}void BinaryTreePostOrder(BTNode* root)
{if (root){BinaryTreePostOrder(root-left);BinaryTreePostOrder(root-right);printf(%c, root-data);}
}
