PHP实现的线索二叉树及二叉树遍历方法详解-华尔子博-奥夏网

PHP实现的线索二叉树及二叉树遍历方法。分享给大家供大家参考，具体如下：

<?php

require 'biTree.php';

$str = 'ko#be8#tr####acy#####';

$tree = new BiTree($str);

$tree->createThreadTree();

echo $tree->threadList() . "n";从第一个结点开始遍历线索二叉树

echo $tree->threadListReserv();从最后一个结点开始反向遍历

?>

biTree.php：

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

<?

/**

* PHP实现二叉树

*

* @author zhaojiangwei

* @since 2011/10/25 10:32

*/

//结点类

class Node{

private $data = NULL;

private $left = NULL;

private $right = NULL;

private $lTag = 0;

private $rTag = 0;

public function Node($data = false){

$this->data = $data;

}

//我不喜欢使用魔术方法

public function getData(){

return $this->data;

}

public function setData($data){

$this->data = $data;

}

public function getLeft(){

return $this->left;

}

public function setLeft($left){

$this->left = $left;

}

public function getRight(){

return $this->right;

}

public function setRight($right){

$this->right = $right;

}

public function getLTag(){

return $this->lTag;

}

public function setLTag($tag){

$this->lTag = $tag;

}

public function getRTag(){

return $this->rTag;

}

public function setRTag($tag){

$this->rTag = $tag;

}

//线索二叉树类

class BiTree{

private $datas = NULL;//要导入的字符串;

private $root = NULL; //根结点

private $leafCount = 0;//叶子结点个数

private $headNode = NULL; //线索二叉树的头结点

private $preNode = NULL;//遍历线索化二叉树时保存前一个遍历的结点

public function BiTree($datas){

is_array($datas) || $datas = str_split($datas);

$this->datas = $datas;

$this->backupData = $this->datas;

$this->createTree(TRUE);

}

//前序遍历创建树

//$root 判断是不是要创建根结点

public function createTree($root = FALSE){

if(emptyempty($this->datas)) return NULL;

$first = array_shift($this->datas);

if($first == '#'){

return NULL;

}else{

$node = new Node($first);

$root && $this->root = $node;

$node->setLeft($this->createTree());

$node->setRight($this->createTree());

return $node;

}

//返回二叉树叶子结点的个数

public function getLeafCount(){

$this->figureLeafCount($this->root);

return $this->leafCount;

}

private function figureLeafCount($node){

if($node == NULL)

return false;

if($this->checkEmpty($node)){

$this->leafCount ++;

}else{

$this->figureLeafCount($node->getLeft());

$this->figureLeafCount($node->getRight());

}

//判断结点是不是叶子结点

private function checkEmpty($node){

if($node->getLeft() == NULL && $node->getRight() == NULL){

return true;

}

return false;

}

//返回二叉树深度

public function getDepth(){

return $this->traversDepth($this->root);

}

//遍历求二叉树深度

public function traversDepth($node){

if($node == NULL){

return 0;

}

$u = $this->traversDepth($node->getLeft()) + 1;

$v = $this->traversDepth($node->getRight()) + 1;

return $u > $v ? $u : $v;

}

//返回遍历结果,以字符串的形式

//$order 按遍历形式返回,前中后

public function getList($order = 'front'){

if($this->root == NULL) return NULL;

$nodeList = array();

switch ($order){

case "front":

$this->frontList($this->root, $nodeList);

break;

case "middle":

$this->middleList($this->root, $nodeList);

break;

case "last":

$this->lastList($this->root, $nodeList);

break;

default:

$this->frontList($this->root, $nodeList);

break;

}

return implode($nodeList);

}

//创建线索二叉树

public function createThreadTree(){

$this->headNode = new Node();

$this->preNode = & $this->headNode;

$this->headNode->setLTag(0);

$this->headNode->setLeft($this->root);

$this->headNode->setRTag(1);

$this->threadTraverse($this->root);

$this->preNode->setRight($this->headNode);

$this->preNode->setRTag(1);

$this->headNode->setRight($this->preNode);

}

//线索化二叉树

private function threadTraverse($node){

if($node != NULL){

if($node->getLeft() == NULL){

$node->setLTag(1);

$node->setLeft($this->preNode);

}else{

$this->threadTraverse($node->getLeft());

}

if($this->preNode != $this->headNode && $this->preNode->getRight() == NULL){

$this->preNode->setRTag(1);

$this->preNode->setRight($node);

}

$this->preNode = & $node;//注意传引用

$this->threadTraverse($node->getRight());

}

//从第一个结点遍历中序线索二叉树

public function threadList(){

$arr = array();

for($node = $this->getFirstThreadNode($this->root); $node != $this->headNode; $node = $this->getNextNode($node)){

$arr[] = $node->getData();

}

return implode($arr);

}

//从尾结点反向遍历中序线索二叉树

public function threadListReserv(){

$arr = array();

for($node = $this->headNode->getRight(); $node != $this->headNode; $node = $this->getPreNode($node)){

$arr[] = $node->getData();

}

return implode($arr);

}

//返回某个结点的前驱

public function getPreNode($node){

if($node->getLTag() == 1){

return $node->getLeft();

}else{

return $this->getLastThreadNode($node->getLeft());

}

//返回某个结点的后继

public function getNextNode($node){

if($node->getRTag() == 1){

return $node->getRight();

}else{

return $this->getFirstThreadNode($node->getRight());

}

//返回中序线索二叉树的第一个结点

public function getFirstThreadNode($node){

while($node->getLTag() == 0){

$node = $node->getLeft();

}

return $node;

}

//返回中序线索二叉树的最后一个结点

public function getLastThreadNode($node){

while($node->getRTag() == 0){

$node = $node->getRight();

}

return $node;

}

//前序遍历

private function frontList($node, & $nodeList){

if($node !== NULL){

$nodeList[] = $node->getData();

$this->frontList($node->getLeft(), $nodeList);

$this->frontList($node->getRight(), $nodeList);

}

//中序遍历

private function middleList($node, & $nodeList){

if($node != NULL){

$this->middleList($node->getLeft(), $nodeList);

$nodeList[] = $node->getData();

$this->middleList($node->getRight(), $nodeList);

}

//后序遍历

private function lastList($node, & $nodeList){

if($node != NULL){

$this->lastList($node->getLeft(), $nodeList);

$this->lastList($node->getRight(), $nodeList);

$nodeList[] = $node->getData();

}

public function getData(){

return $this->data;

}

public function getRoot(){

return $this->root;

}

?>

本文刊载的所有内容，包括文字、图片、音频、视频、软件、程序、以及网页版式设计等部门来源于互联网，版权均归原作者所有！本网站提供的内容服务于个人学习、研究或欣赏，以及其他非商业性或非盈利性用途，但同时应遵守著作权法及其他相关法律的规定，不得侵犯本网站及相关权利人的合法权利。
联系信息：邮箱aoxolcom@163.com或见网站底部。

THE END