景宁建设局网站官网,基金网站开发,哪个网站教做公众号,网站建设国家标准排序二叉树 二叉树#xff1a;作为基本数据结构的一种#xff0c;是红黑树#xff0c;B树等树形结构的基础。而排序二叉树是按照二叉树的结构来组织的。在本文中采用链表结构来创建二叉树。排序二叉树的 基本原理#xff1a; 排序二叉树是将归并排序的基本思想构建二…排序二叉树 二叉树作为基本数据结构的一种是红黑树B树等树形结构的基础。而排序二叉树是按照二叉树的结构来组织的。在本文中采用链表结构来创建二叉树。排序二叉树的 基本原理 排序二叉树是将归并排序的基本思想构建二叉树结构再用中序遍历的规则来遍历树的各个节点输出的结果就是有序序列(本文是将一组无序的整型数值存储在二叉树中通过中序遍历二叉树将数值输入而得到一组按照由小到大排序的序列从而间接实现了排序。所以下文的解释和说明都以此为例)。 插入节点的过程 1.判断根节点是否为空如果为空,插入节点作为根节点,结束否则转2 2.将要插入的数值和比较节点的数值进行比较。如果插入插入数值大于等于节点数值转3否则转4 3.如果比较节点的右子树为空将比较节点的右指针指向插入节点结束否则将比较节点的右子树的根节点作为新的比较节点转2 4.如果比较节点的左子树为空将比较节点的左指针指向插入节点结束否则将比较节点的左子树的根节点作为新的比较节点转2 通过上述的插入过程实现的二叉树可以得出对于根节点它左边的所有节点的值都小于它而它右边的所有节点是数字都大于或等于它。中序遍历的过程是“左子节点-父节点-右子节点” 这样数值的输出便具有了一定的顺序这个规则的不断重复就是归并排序思想的体现。同时该插入过程符合递归的特性。 算法分析(时间复杂度) 查找过程二叉树查找过程的时间和二叉树的高度成正比。假设二叉树的高度为n,则查找最大值最小值前继结点后和后继节点的时间都可以在O(n)时间内实现。所以树的高度直接决定查找的效率。对于拥有n个节点的二叉树形成完全二叉树时树的高度是最小的即最小为lg(n); 删除和插入过程在二叉树删除和插入过程查找过程是必须的前奏所以插入和删除的最小为(lg(n)O(1)),其中O(1)为插入和删除的时间。 1 #include stdafx.h2 #include stdio.h3 #include stdlib.h4 5 //非递归方法插入节点6 void InsertBtree(node *root,int value)7 {8 9 node *t(node *)malloc(sizeof(node));10 t-leftt-rightNULL;11 t-numbervalue;12 13 node *tempNULL; 14 temproot;15 16 if(tempNULL)17 {18 roott;19 }20 else21 {22 while(temp!NULL)23 {24 if(t-numbertemp-number) 25 {26 if(temp-rightNULL)27 {28 temp-rightt;29 break;30 }31 else32 {33 temptemp-right;34 }35 36 }37 else38 {39 if(temp-leftNULL)40 {41 temp-leftt;42 break;43 }44 else45 {46 temptemp-left;47 }48 }49 }50 } 51 }52 53 //采用递归的方法插入节点54 void InsertBtreeRe(node *root,int value)55 {56 if(rootNULL)57 {58 59 root-numbervalue;60 return;61 }62 else63 {64 if(valueroot-number)65 {66 if(root-rightNULL)67 {68 node *roott(node *)malloc(sizeof(node));69 roott-leftroott-rightNULL;70 roott-numbervalue;71 root-rightroott;72 return;73 }74 else75 {76 InsertBtreeRe(root-right,value);77 }78 }79 else80 {81 if(root-rightNULL)82 {83 node *roott(node *)malloc(sizeof(node));84 roott-leftroott-rightNULL;85 roott-numbervalue;86 root-leftroott;87 return;88 }89 else90 {91 InsertBtreeRe(root-left,value);92 }93 }94 }95 }96 97 98 //将一个整数数组中的数字按照归并排序的原理进行存储99 void buildBtree(int *p, int n,node *root)
100 {
101 int i;
102 node *vpNULL;
103
104 root-numberp[0];
105 root-leftroot-rightNULL;
106
107 for(i1;in;i)
108 {
109
110 vproot;
111 node *temp(node *)malloc(sizeof(node));
112 temp-numberp[i];
113 temp-lefttemp-rightNULL;
114
115 while(vp!NULL)
116 {
117 if(temp-numbervp-number)
118 {
119 if(vp-rightNULL)
120 {
121 vp-righttemp;
122 break;
123 }
124 else
125 {
126 vpvp-right;
127 }
128 }
129 else
130 {
131 if(vp-leftNULL)
132 {
133 vp-lefttemp;
134 break;
135 }
136 else
137 {
138 vpvp-left;
139 }
140 }
141 }
142
143 }
144
145 }
146
147 //按照中序遍历二叉树
148 void midsearchBtree(node *proot)
149 {
150 if(proot!NULL)
151 {
152 midsearchBtree(proot-left);
153 printf(%d ,proot-number);
154 midsearchBtree(proot-right);
155 }
156 }
157
158 int main()
159 {
160 node *croot;
161 int input;
162 croot(node *)malloc(sizeof(node));
163
164 int a[]{7,5,3,2,4};
165 buildBtree(a,5,croot);
166 midsearchBtree(croot);
167 printf(\n);
168
169 while(scanf_s(%d,input) input!1)
170 {
171 InsertBtree(croot,input);
172 }
173 midsearchBtree(croot);
174 printf(\n);
175
176 InsertBtreeRe(croot,10);
177 midsearchBtree(croot);
178 printf(\n);
179 return 0;
180 } 转载于:https://www.cnblogs.com/zhengyou/p/3567759.html
