当前位置: 编程技术>php
本页文章导读:
▪基于PHP+Ajax实现表单验证的详解
一,利用键盘响应,在不刷新本页面的情况下验证表单输入是否合法用户通过onkeydown和onkeyup事件来触发响应事件。使用方法和onclick事件类似。onkeydown表示当键盘上的键被按下时触发,onkeyup.........
▪PHP Class&Object -- 解析PHP实现二叉树
二叉树及其变体是数据结构家族里的重要组成部分。最为链表的一种变体,二叉树最适合处理需要一特定次序快速组织和检索的数据。 代码如下:<?php// Define a class to implement a binary treeclass .........
▪PHP Class&Object -- PHP 自排序二叉树的深入解析
在节点之间再应用一些排序逻辑,二叉树就能提供出色的组织方式。对于每个节点,都让满足所有特定条件的元素都位于左节点及其子节点。在插入新元素时,我们需要从树的第一个节 点(.........
[1]基于PHP+Ajax实现表单验证的详解
来源: 互联网 发布时间: 2013-11-30
一,利用键盘响应,在不刷新本页面的情况下验证表单输入是否合法
用户通过onkeydown和onkeyup事件来触发响应事件。使用方法和onclick事件类似。onkeydown表示当键盘上的键被按下时触发,onkeyup和它正好相反,当键盘上的键被按下又抬起时触发。
两种常用调用方法:
(1)将事件添加到页面元素中,当用户输入完信息后,单击任意键,onkeydown事件被触发,并调用refer()函数。
这种方法最简单,最直接,格式如下:
<script type="text/javascript">
...
function refer(){
...
}
</script>
<input type="text" onkeydown="refer()"/>
(2)通过window.onload加载,当页面被载入时,事件被载入。当用户输入信息时,每输入一个字母,都将触发该事件,在该事件调用的函数中,对用户输入信息进行判断。
window.onload = function(){
$('regname').onkeydown = function (){
name = $('regname').value;
}
}
使用onkeydown事件还可以实现对特定键的控制,包括<Enter>键(event.keyCode==13)、空格键(event.keyCode==32)、<Ctrl>键、<Alt>键等所有的按键,这是通过在onkeydown事件中使用keyCode属性来实现的。KeyCode属性能够知道用户按下的是哪个键。
二,注册信息验证
通用函数,返回被触发的id元素对象
function $(id){
return document.getElementById(id);
}
window.onload事件,表示当前窗口被载入时触发。function(){...}表示当前页面被载入时所要进行的操作。
window.onload = function(){
...
}
function()函数解析;
首先将焦点定位到用户名文本框,方便用户操作。接下来声明了5个变量,这5个变量代表了5个要检测的数据的结果。当检测数据为合格时,将变量值设为"yes".
$('regname').focus();
var cname1,cname2,cpwd1,cpwd2; //声明了5个变量,表示要检测的5项数据chkreg()函数是每一次触发键盘事件后都要调用的,该函数判断5个变量的值,只有当所有变量都为"yes"时,注册按钮才会被激活。
function chkreg(){
if((cname1 == 'yes') && (cname2 == 'yes') && (cpwd1 == 'yes') && (cpwd2 == 'yes')){
$('regbtn').disabled = false;
}else{
$('regbtn').disabled = true;
}
}
下面验证用户名,当用户输入注册名称时,该函数会把用户的每次输入都做一下正则判断,并根据结果设置不同的cname1的值。
$('regname').onkeyup = function (){
name = $('regname').value; //获取注册名称
cname2 = '';
if(name.match(/^[a-zA-Z_]*/) == ''){
$('namediv').innerHTML = '<font color=red>必须以字母或下划线开头</font>';
cname1 = '';
}else if(name.length <= 3){
$('namediv').innerHTML = '<font color=red>注册名称必须大于3位</font>';
cname1 = '';
}else{
$('namediv').innerHTML = '<font color=green>注册名称符合标准</font>';
cname1 = 'yes';
}
chkreg(); //调用chkreg()函数,判断5个变量是否正确
}
当用户名文本框失去焦点时,即用户输入完毕转到页面中其他元素的时候,将检测用户名是否重复。用户名判断使用Ajax技术调用了chkname.php(该页面用户名验证代码稍后贴出)并根据chkname.php的返回值在div标签中显示判断结果。
$('regname').onblur = function(){
name = $('regname').value; //获取注册名称
if(cname1 == 'yes'){ //当用户名称的格式输入合格后才进行这一步
xmlhttp.open('get','chkname.php?name='+name,true); //open()创建XMLHttpRequest初始化连接,Ajax创建新的请求
xmlhttp.onreadystatechange = function(){ //当指定XMLHttpRequest为异步传输时(false),发生任何状态的变化,该对象都会调用onreadystatechange所指定的函数
if(xmlhttp.readyState == 4){ //XMLHttpRequest处理状态,4表示处理完毕
if(xmlhttp.status == 200){ //服务器响应的HTTP代码,200表示正常
var msg = xmlhttp.responseText; //获取响应页的内容
if(msg == '1'){ //chkname.php页面查找数据库,数据库没有该用户返回1
$('namediv').innerHTML="<font color=green>恭喜您,该用户名可以使用!</font>";
cname2 = 'yes';
}else if(msg == '2'){ //数据库存在该用户返回0
$('namediv').innerHTML="<font color=red>用户名被占用!</font>";
cname2 = '';
}else{
$('namediv').innerHTML="<font color=red>"+msg+"</font>";
cname2 = '';
}
}
}
}
xmlhttp.send(null);
chkreg(); //检测是否激活注册按钮
}
}
验证密码,验证密码时,除了可以限制密码的长度外,还可以判断密码的强度。
$('regpwd1').onkeyup = function(){
pwd = $('regpwd1').value;
pwd2 = $('regpwd2').value;
if(pwd.length < 6){
$('pwddiv1').innerHTML = '<font color=red>密码长度最少需要6位</font>';
cpwd1 = '';
}else if(pwd.length >= 6 && pwd.length < 12){
$('pwddiv1').innerHTML = '<font color=green>密码符合要求。密码强度:弱</font>';
cpwd1 = 'yes';
}else if((pwd.match(/^[0-9]*$/)!=null) || (pwd.match(/^[a-zA-Z]*$/) != null )){
$('pwddiv1').innerHTML = '<font color=green>密码符合要求。密码强度:中</font>';
cpwd1 = 'yes';
}else{
$('pwddiv1').innerHTML = '<font color=green>密码符合要求。密码强度:高</font>';
cpwd1 = 'yes';
}
if(pwd2 != '' && pwd != pwd2){
$('pwddiv2').innerHTML = '<font color=red>两次密码不一致!</font>';
cpwd2 = '';
}else if(pwd2 != '' && pwd == pwd2){
$('pwddiv2').innerHTML = '<font color=green>密码输入正确</font>';
cpwd2 = 'yes';
}
chkreg();
}
二次密码判断比较简单,只要判断第二次输入密码是否和第一次输入相等。
$('regpwd2').onkeyup = function(){
pwd1 = $('regpwd1').value;
pwd2 = $('regpwd2').value;
if(pwd1 != pwd2){
$('pwddiv2').innerHTML = '<font color=red>两次密码不一致!</font>';
cpwd2 = '';
}else{
$('pwddiv2').innerHTML = '<font color=green>密码输入正确</font>';
cpwd2 = 'yes';
}
chkreg();
}
上面是必须填写信息,如果用户希望填写更详细的资料,可单击"详细资料按钮"
$('morebtn').onclick = function(){
if($('morediv').style.display == ''){
$('morediv').style.display = 'none';
}else{
$('morediv').style.display = '';
}
}
E-mail格式验证,输入字符串中必须包含@和.,同时这两个字符串的位置既不能在首尾也不能连在一起
$('email').onkeyup = function(){
emailreg = /^\w+([-+.]\w+)*@\w+([-.]\w+)*\.\w+([-.]\w+)*$/;
$('email').value.match(emailreg);
if($('email').value.match(emailreg) == null){
$('emaildiv').innerHTML = '<font color=red>错误的email格式</font>';
cemail = '';
}else{
$('emaildiv').innerHTML = '<font color=green>输入正确</font>';
cemail = 'yes';
}
chkreg();
}
三,检测用户名(chkname.php)
<?php
session_start();
include_once "conn/conn.php";
$reback = '0';
$sql = "select * from tb_member where name='".$_GET['name']."'";
$num = $conne->getRowsNum($sql);
if($num == 1){
$reback = '2';
}else if($num == 0){
$reback = '1';
}else{
$reback = $conne->msg_error();
}
echo $reback;
?>
四,XMLHttpRequest函数初始化
// JavaScript Document
var xmlhttp = false;
if (window.XMLHttpRequest) { //Mozilla、Safari等浏览器
xmlhttp = new XMLHttpRequest();
}
else if (window.ActiveXObject) { //IE浏览器
try {
xmlhttp = new ActiveXObject("Msxml2.XMLHTTP");
} catch (e) {
try {
xmlhttp = new ActiveXObject("Microsoft.XMLHTTP");
} catch (e) {}
}
}
用户通过onkeydown和onkeyup事件来触发响应事件。使用方法和onclick事件类似。onkeydown表示当键盘上的键被按下时触发,onkeyup和它正好相反,当键盘上的键被按下又抬起时触发。
两种常用调用方法:
(1)将事件添加到页面元素中,当用户输入完信息后,单击任意键,onkeydown事件被触发,并调用refer()函数。
这种方法最简单,最直接,格式如下:
代码如下:
<script type="text/javascript">
...
function refer(){
...
}
</script>
<input type="text" onkeydown="refer()"/>
(2)通过window.onload加载,当页面被载入时,事件被载入。当用户输入信息时,每输入一个字母,都将触发该事件,在该事件调用的函数中,对用户输入信息进行判断。
代码如下:
window.onload = function(){
$('regname').onkeydown = function (){
name = $('regname').value;
}
}
使用onkeydown事件还可以实现对特定键的控制,包括<Enter>键(event.keyCode==13)、空格键(event.keyCode==32)、<Ctrl>键、<Alt>键等所有的按键,这是通过在onkeydown事件中使用keyCode属性来实现的。KeyCode属性能够知道用户按下的是哪个键。
二,注册信息验证
通用函数,返回被触发的id元素对象
代码如下:
function $(id){
return document.getElementById(id);
}
window.onload事件,表示当前窗口被载入时触发。function(){...}表示当前页面被载入时所要进行的操作。
window.onload = function(){
...
}
function()函数解析;
首先将焦点定位到用户名文本框,方便用户操作。接下来声明了5个变量,这5个变量代表了5个要检测的数据的结果。当检测数据为合格时,将变量值设为"yes".
代码如下:
$('regname').focus();
var cname1,cname2,cpwd1,cpwd2; //声明了5个变量,表示要检测的5项数据chkreg()函数是每一次触发键盘事件后都要调用的,该函数判断5个变量的值,只有当所有变量都为"yes"时,注册按钮才会被激活。
function chkreg(){
if((cname1 == 'yes') && (cname2 == 'yes') && (cpwd1 == 'yes') && (cpwd2 == 'yes')){
$('regbtn').disabled = false;
}else{
$('regbtn').disabled = true;
}
}
下面验证用户名,当用户输入注册名称时,该函数会把用户的每次输入都做一下正则判断,并根据结果设置不同的cname1的值。
代码如下:
$('regname').onkeyup = function (){
name = $('regname').value; //获取注册名称
cname2 = '';
if(name.match(/^[a-zA-Z_]*/) == ''){
$('namediv').innerHTML = '<font color=red>必须以字母或下划线开头</font>';
cname1 = '';
}else if(name.length <= 3){
$('namediv').innerHTML = '<font color=red>注册名称必须大于3位</font>';
cname1 = '';
}else{
$('namediv').innerHTML = '<font color=green>注册名称符合标准</font>';
cname1 = 'yes';
}
chkreg(); //调用chkreg()函数,判断5个变量是否正确
}
当用户名文本框失去焦点时,即用户输入完毕转到页面中其他元素的时候,将检测用户名是否重复。用户名判断使用Ajax技术调用了chkname.php(该页面用户名验证代码稍后贴出)并根据chkname.php的返回值在div标签中显示判断结果。
代码如下:
$('regname').onblur = function(){
name = $('regname').value; //获取注册名称
if(cname1 == 'yes'){ //当用户名称的格式输入合格后才进行这一步
xmlhttp.open('get','chkname.php?name='+name,true); //open()创建XMLHttpRequest初始化连接,Ajax创建新的请求
xmlhttp.onreadystatechange = function(){ //当指定XMLHttpRequest为异步传输时(false),发生任何状态的变化,该对象都会调用onreadystatechange所指定的函数
if(xmlhttp.readyState == 4){ //XMLHttpRequest处理状态,4表示处理完毕
if(xmlhttp.status == 200){ //服务器响应的HTTP代码,200表示正常
var msg = xmlhttp.responseText; //获取响应页的内容
if(msg == '1'){ //chkname.php页面查找数据库,数据库没有该用户返回1
$('namediv').innerHTML="<font color=green>恭喜您,该用户名可以使用!</font>";
cname2 = 'yes';
}else if(msg == '2'){ //数据库存在该用户返回0
$('namediv').innerHTML="<font color=red>用户名被占用!</font>";
cname2 = '';
}else{
$('namediv').innerHTML="<font color=red>"+msg+"</font>";
cname2 = '';
}
}
}
}
xmlhttp.send(null);
chkreg(); //检测是否激活注册按钮
}
}
验证密码,验证密码时,除了可以限制密码的长度外,还可以判断密码的强度。
代码如下:
$('regpwd1').onkeyup = function(){
pwd = $('regpwd1').value;
pwd2 = $('regpwd2').value;
if(pwd.length < 6){
$('pwddiv1').innerHTML = '<font color=red>密码长度最少需要6位</font>';
cpwd1 = '';
}else if(pwd.length >= 6 && pwd.length < 12){
$('pwddiv1').innerHTML = '<font color=green>密码符合要求。密码强度:弱</font>';
cpwd1 = 'yes';
}else if((pwd.match(/^[0-9]*$/)!=null) || (pwd.match(/^[a-zA-Z]*$/) != null )){
$('pwddiv1').innerHTML = '<font color=green>密码符合要求。密码强度:中</font>';
cpwd1 = 'yes';
}else{
$('pwddiv1').innerHTML = '<font color=green>密码符合要求。密码强度:高</font>';
cpwd1 = 'yes';
}
if(pwd2 != '' && pwd != pwd2){
$('pwddiv2').innerHTML = '<font color=red>两次密码不一致!</font>';
cpwd2 = '';
}else if(pwd2 != '' && pwd == pwd2){
$('pwddiv2').innerHTML = '<font color=green>密码输入正确</font>';
cpwd2 = 'yes';
}
chkreg();
}
二次密码判断比较简单,只要判断第二次输入密码是否和第一次输入相等。
代码如下:
$('regpwd2').onkeyup = function(){
pwd1 = $('regpwd1').value;
pwd2 = $('regpwd2').value;
if(pwd1 != pwd2){
$('pwddiv2').innerHTML = '<font color=red>两次密码不一致!</font>';
cpwd2 = '';
}else{
$('pwddiv2').innerHTML = '<font color=green>密码输入正确</font>';
cpwd2 = 'yes';
}
chkreg();
}
上面是必须填写信息,如果用户希望填写更详细的资料,可单击"详细资料按钮"
代码如下:
$('morebtn').onclick = function(){
if($('morediv').style.display == ''){
$('morediv').style.display = 'none';
}else{
$('morediv').style.display = '';
}
}
E-mail格式验证,输入字符串中必须包含@和.,同时这两个字符串的位置既不能在首尾也不能连在一起
代码如下:
$('email').onkeyup = function(){
emailreg = /^\w+([-+.]\w+)*@\w+([-.]\w+)*\.\w+([-.]\w+)*$/;
$('email').value.match(emailreg);
if($('email').value.match(emailreg) == null){
$('emaildiv').innerHTML = '<font color=red>错误的email格式</font>';
cemail = '';
}else{
$('emaildiv').innerHTML = '<font color=green>输入正确</font>';
cemail = 'yes';
}
chkreg();
}
三,检测用户名(chkname.php)
代码如下:
<?php
session_start();
include_once "conn/conn.php";
$reback = '0';
$sql = "select * from tb_member where name='".$_GET['name']."'";
$num = $conne->getRowsNum($sql);
if($num == 1){
$reback = '2';
}else if($num == 0){
$reback = '1';
}else{
$reback = $conne->msg_error();
}
echo $reback;
?>
四,XMLHttpRequest函数初始化
代码如下:
// JavaScript Document
var xmlhttp = false;
if (window.XMLHttpRequest) { //Mozilla、Safari等浏览器
xmlhttp = new XMLHttpRequest();
}
else if (window.ActiveXObject) { //IE浏览器
try {
xmlhttp = new ActiveXObject("Msxml2.XMLHTTP");
} catch (e) {
try {
xmlhttp = new ActiveXObject("Microsoft.XMLHTTP");
} catch (e) {}
}
}
[2]PHP Class&Object -- 解析PHP实现二叉树
来源: 互联网 发布时间: 2013-11-30
二叉树及其变体是数据结构家族里的重要组成部分。最为链表的一种变体,二叉树最适合处理需要一特定次序快速组织和检索的数据。
<?php
// Define a class to implement a binary tree
class Binary_Tree_Node {
// Define the variable to hold our data:
public $data;
// And a variable to hold the left and right objects:
public $left;
public $right;
// A constructor method that allows for data to be passed in
public function __construct($d = NULL) {
$this->data = $d;
}
// Traverse the tree, left to right, in pre-order, returning an array
// Preorder means that each node's value preceeds its children.
public function traversePreorder() {
// Prep some variables.
$l = array();
$r = array();
// Read in the left and right children appropriately traversed:
if ($this->left) { $l = $this->left->traversePreorder(); }
if ($this->right) { $r = $this->right->traversePreorder(); }
// Return a merged array of the current value, left, and right:
return array_merge(array($this->data), $l, $r);
}
// Traverse the tree, left to right, in postorder, returning an array
// Postorder means that each node's value follows its children.
public function traversePostorder() {
// Prep some variables.
$l = array();
$r = array();
// Read in the left and right children appropriately traversed:
if ($this->left) { $l = $this->left->traversePostorder(); }
if ($this->right) { $r = $this->right->traversePostorder(); }
// Return a merged array of the current value, left, and right:
return array_merge($l, $r, array($this->data));
}
// Traverse the tree, left to right, in-order, returning an array.
// In-order means that values are ordered as left children, then the
// node value, then the right children.
public function traverseInorder() {
// Prep some variables.
$l = array();
$r = array();
// Read in the left and right children appropriately traversed:
if ($this->left) { $l = $this->left->traverseInorder(); }
if ($this->right) { $r = $this->right->traverseInorder(); }
// Return a merged array of the current value, left, and right:
return array_merge($l, array($this->data), $r);
}
}
// Let's create a binary tree that will equal the following: 3
// / /
// h 9
// / /
// Create the tree: 6 a
$tree = new Binary_Tree_Node(3);
$tree->left = new Binary_Tree_Node('h');
$tree->right = new Binary_Tree_Node(9);
$tree->right->left = new Binary_Tree_Node(6);
$tree->right->right = new Binary_Tree_Node('a');
// Now traverse this tree in all possible orders and display the results:
// Pre-order: 3, h, 9, 6, a
echo '<p>', implode(', ', $tree->traversePreorder()), '</p>';
// Post-order: h, 9, 6, a, 3
echo '<p>', implode(', ', $tree->traversePostorder()), '</p>';
// In-order: h, 3, 6, 9, a
echo '<p>', implode(', ', $tree->traverseInorder()), '</p>';
?>
代码如下:
<?php
// Define a class to implement a binary tree
class Binary_Tree_Node {
// Define the variable to hold our data:
public $data;
// And a variable to hold the left and right objects:
public $left;
public $right;
// A constructor method that allows for data to be passed in
public function __construct($d = NULL) {
$this->data = $d;
}
// Traverse the tree, left to right, in pre-order, returning an array
// Preorder means that each node's value preceeds its children.
public function traversePreorder() {
// Prep some variables.
$l = array();
$r = array();
// Read in the left and right children appropriately traversed:
if ($this->left) { $l = $this->left->traversePreorder(); }
if ($this->right) { $r = $this->right->traversePreorder(); }
// Return a merged array of the current value, left, and right:
return array_merge(array($this->data), $l, $r);
}
// Traverse the tree, left to right, in postorder, returning an array
// Postorder means that each node's value follows its children.
public function traversePostorder() {
// Prep some variables.
$l = array();
$r = array();
// Read in the left and right children appropriately traversed:
if ($this->left) { $l = $this->left->traversePostorder(); }
if ($this->right) { $r = $this->right->traversePostorder(); }
// Return a merged array of the current value, left, and right:
return array_merge($l, $r, array($this->data));
}
// Traverse the tree, left to right, in-order, returning an array.
// In-order means that values are ordered as left children, then the
// node value, then the right children.
public function traverseInorder() {
// Prep some variables.
$l = array();
$r = array();
// Read in the left and right children appropriately traversed:
if ($this->left) { $l = $this->left->traverseInorder(); }
if ($this->right) { $r = $this->right->traverseInorder(); }
// Return a merged array of the current value, left, and right:
return array_merge($l, array($this->data), $r);
}
}
// Let's create a binary tree that will equal the following: 3
// / /
// h 9
// / /
// Create the tree: 6 a
$tree = new Binary_Tree_Node(3);
$tree->left = new Binary_Tree_Node('h');
$tree->right = new Binary_Tree_Node(9);
$tree->right->left = new Binary_Tree_Node(6);
$tree->right->right = new Binary_Tree_Node('a');
// Now traverse this tree in all possible orders and display the results:
// Pre-order: 3, h, 9, 6, a
echo '<p>', implode(', ', $tree->traversePreorder()), '</p>';
// Post-order: h, 9, 6, a, 3
echo '<p>', implode(', ', $tree->traversePostorder()), '</p>';
// In-order: h, 3, 6, 9, a
echo '<p>', implode(', ', $tree->traverseInorder()), '</p>';
?>
[3]PHP Class&Object -- PHP 自排序二叉树的深入解析
来源: 互联网 发布时间: 2013-11-30
在节点之间再应用一些排序逻辑,二叉树就能提供出色的组织方式。对于每个节点,都让满足所有特定条件的元素都位于左节点及其子节点。在插入新元素时,我们需要从树的第一个节 点(根节点)开始,判断它属于哪一侧的节点,然后沿着这一侧找到恰当的位置,类似地,在读取数据时,只需要使用按序遍历方法来遍历二叉树。
<?php
ob_start();
// Here we need to include the binary tree class
Class Binary_Tree_Node() {
// You can find the details at
}
ob_end_clean();
// Define a class to implement self sorting binary tree
class Sorting_Tree {
// Define the variable to hold our tree:
public $tree;
// We need a method that will allow for inserts that automatically place
// themselves in the proper order in the tree
public function insert($val) {
// Handle the first case:
if (!(isset($this->tree))) {
$this->tree = new Binary_Tree_Node($val);
} else {
// In all other cases:
// Start a pointer that looks at the current tree top:
$pointer = $this->tree;
// Iteratively search the tree for the right place:
for(;;) {
// If this value is less than, or equal to the current data:
if ($val <= $pointer->data) {
// We are looking to the left ... If the child exists:
if ($pointer->left) {
// Traverse deeper:
$pointer = $pointer->left;
} else {
// Found the new spot: insert the new element here:
$pointer->left = new Binary_Tree_Node($val);
break;
}
} else {
// We are looking to the right ... If the child exists:
if ($pointer->right) {
// Traverse deeper:
$pointer = $pointer->right;
} else {
// Found the new spot: insert the new element here:
$pointer->right = new Binary_Tree_Node($val);
break;
}
}
}
}
}
// Now create a method to return the sorted values of this tree.
// All it entails is using the in-order traversal, which will now
// give us the proper sorted order.
public function returnSorted() {
return $this->tree->traverseInorder();
}
}
// Declare a new sorting tree:
$sort_as_you_go = new Sorting_Tree();
// Let's randomly create 20 numbers, inserting them as we go:
for ($i = 0; $i < 20; $i++) {
$sort_as_you_go->insert(rand(1,100));
}
// Now echo the tree out, using in-order traversal, and it will be sorted:
// Example: 1, 2, 11, 18, 22, 26, 32, 32, 34, 43, 46, 47, 47, 53, 60, 71,
// 75, 84, 86, 90
echo '<p>', implode(', ', $sort_as_you_go->returnSorted()), '</p>';
?>
代码如下:
<?php
ob_start();
// Here we need to include the binary tree class
Class Binary_Tree_Node() {
// You can find the details at
}
ob_end_clean();
// Define a class to implement self sorting binary tree
class Sorting_Tree {
// Define the variable to hold our tree:
public $tree;
// We need a method that will allow for inserts that automatically place
// themselves in the proper order in the tree
public function insert($val) {
// Handle the first case:
if (!(isset($this->tree))) {
$this->tree = new Binary_Tree_Node($val);
} else {
// In all other cases:
// Start a pointer that looks at the current tree top:
$pointer = $this->tree;
// Iteratively search the tree for the right place:
for(;;) {
// If this value is less than, or equal to the current data:
if ($val <= $pointer->data) {
// We are looking to the left ... If the child exists:
if ($pointer->left) {
// Traverse deeper:
$pointer = $pointer->left;
} else {
// Found the new spot: insert the new element here:
$pointer->left = new Binary_Tree_Node($val);
break;
}
} else {
// We are looking to the right ... If the child exists:
if ($pointer->right) {
// Traverse deeper:
$pointer = $pointer->right;
} else {
// Found the new spot: insert the new element here:
$pointer->right = new Binary_Tree_Node($val);
break;
}
}
}
}
}
// Now create a method to return the sorted values of this tree.
// All it entails is using the in-order traversal, which will now
// give us the proper sorted order.
public function returnSorted() {
return $this->tree->traverseInorder();
}
}
// Declare a new sorting tree:
$sort_as_you_go = new Sorting_Tree();
// Let's randomly create 20 numbers, inserting them as we go:
for ($i = 0; $i < 20; $i++) {
$sort_as_you_go->insert(rand(1,100));
}
// Now echo the tree out, using in-order traversal, and it will be sorted:
// Example: 1, 2, 11, 18, 22, 26, 32, 32, 34, 43, 46, 47, 47, 53, 60, 71,
// 75, 84, 86, 90
echo '<p>', implode(', ', $sort_as_you_go->returnSorted()), '</p>';
?>
最新技术文章: