【365bet亚洲真人】[PHP] 数据结构-二叉树的始建PHP落成

  

voidPreOrder_Nonrecursive(BiTree T)//先序遍历的非递归

{

if(!T)

return;

stack s;

s.push(T);

while(!s.empty())

{

BiTree temp = s.top();

cout<data<<” “;

s.pop();

if(temp->rchild)

s.push(temp->rchild);

if(temp->lchild)

s.push(temp->lchild);

}

}

概念  

随便一棵树,它的结点的第四个孩子只要存在就是唯一的,它的右兄弟假设存在也是唯一的。由此,我们设置多少个指针,分别指向该结点的第二个儿女和此结点的右兄弟。

 

//按先序遍历创制二叉树

//BiTree *CreateBiTree()     //再次来到结点指针类型

//void CreateBiTree(BiTree &root)      //引用类型的参数

voidCreateBiTree(BiTNode **root)//二级指针作为函数参数

{

charch;//要插入的多少

scanf(“\n%c”, &ch);

//cin>>ch;

if(ch==’#’)

*root = NULL;

else

{

*root = (BiTNode *)malloc(sizeof(BiTNode));

(*root)->data = ch;

printf(“请输入%c的左孩子:”,ch);

CreateBiTree(&((*root)->lchild));

printf(“请输入%c的右孩子:”,ch);

CreateBiTree(&((*root)->rchild));

}

}

3. 示例

  

  设root是一根指针(即它的体系是BinTree),则调用CreateBinTree(&root)后root就对准了已协会好的二叉链表的根结点。

  二叉树建立过程见

  下边是有关二叉树的遍历、查找、删除、更新数据的代码(递归算法):

  #include <iostream>

  using namespace std;

  typedef int T;

  class bst{

  struct Node{

  T data;

  Node* L;

  Node* R;

  Node(const T& d, Node* lp=NULL, Node*
rp=NULL):data(d),L(lp),R(rp){}

  };

  Node* root;

  int num;

  public:

  bst():root(NULL),num(0){}

  void clear(Node* t){

  if(t==NULL) return;

  clear(t->L);

  clear(t->R);

  delete t;

  }

  ~bst(){clear(root);}

  void clear(){

  clear(root);

  num = 0;

  root = NULL;

  }

  bool empty(){return root==NULL;}

  int size(){return num;}

  T getRoot(){

  if(empty()) throw “empty tree”;

  return root->data;

  }

  void travel(Node* tree){

  if(tree==NULL) return;

  travel(tree->L);

  cout << tree->data << ‘ ‘;

  travel(tree->R);

  }

  void travel(){

  travel(root);

  cout << endl;

  }

  int height(Node* tree){

  if(tree==NULL) return 0;

  int lh = height(tree->L);

  int rh = height(tree->R);

  return 1+(lh>rh?lh:rh);

  }

  int height(){

  return height(root);

  }

  void insert(Node*& tree, const T& d){

  if(tree==NULL)

  tree = new Node(d);

  else if(ddata)

  insert(tree->L, d);

  else

  insert(tree->R, d);

  }

  void insert(const T& d){

  insert(root, d);

  num++;

  }

  Node*& find(Node*& tree, const T& d){

  if(tree==NULL) return tree;

  if(tree->data==d) return tree;

  if(ddata)

  return find(tree->L, d);

  else

  return find(tree->R, d);

  }

  bool find(const T& d){

  return find(root, d)!=NULL;

  }

  bool erase(const T& d){

  Node*& pt = find(root, d);

  if(pt==NULL) return false;

  combine(pt->L, pt->R);

  Node* p = pt;

  pt = pt->R;

  delete p;

  num–;

  return true;

  }

  void combine(Node* lc, Node*& rc){

  if(lc==NULL) return;

  if(rc==NULL) rc = lc;

  else combine(lc, rc->L);

  }

  bool update(const T& od, const T& nd){

  Node* p = find(root, od);

  if(p==NULL) return false;

  erase(od);

  insert(nd);

  return true;

  }

  };

  int main()

  {

  bst b;

  cout << “input some integers:”;

  for(;;){

  int n;

  cin >> n;

  b.insert(n);

  if(cin.peek()==’\n’) break;

  }

  b.travel();

  for(;;){

  cout << “input data pair:”;

  int od, nd;

  cin >> od >> nd;

  if(od==-1&&nd==-1) break;

  b.update(od, nd);

  b.travel();

  }

  }

把种种结点的子女结点排列起来,以单链表作存储结构,则n个结点有n个儿女链表,假设是纸牌结点则此单链表为空,然后n个头指针又构成一个线性表,拔取顺序存储结构,存放进一个一维数组中。

  

#include

二叉树的遍历搜索路径

 所谓遍历(Traversal)是指沿着某条搜索路线,依次对树中每个结点均做三回且仅做五遍访问。访问结点所做的操作看重于现实的利用难题。

  遍历是二叉树上最根本的运算之一,是二叉树上举行其余运算之基础。

[编写本段]

算法与完结

  

PostOrderTraverse(T->lchild); /*程序序遍历左子树*/

<?php
class BinTree{
        public $data;
        public $left;
        public $right;
}
//前序遍历生成二叉树
function createBinTree(){
        $handle=fopen("php://stdin","r");
        $e=trim(fgets($handle));
        if($e=="#"){
                $binTree=null;
        }else{
                $binTree=new BinTree();
                $binTree->data=$e;
                $binTree->left=createBinTree();
                $binTree->right=createBinTree();
        }   
        return $binTree;
}    

$tree=createBinTree();

var_dump($tree);

A
B
#
D
#
#
C
#
#
object(BinTree)#1 (3) {
  ["data"]=>
  string(1) "A"
  ["left"]=>
  object(BinTree)#2 (3) {
    ["data"]=>
    string(1) "B"
    ["left"]=>
    NULL
    ["right"]=>
    object(BinTree)#3 (3) {
      ["data"]=>
      string(1) "D"
      ["left"]=>
      NULL
      ["right"]=>
      NULL
    }
  }
  ["right"]=>
  object(BinTree)#4 (3) {
    ["data"]=>
    string(1) "C"
    ["left"]=>
    NULL
    ["right"]=>
    NULL
  }
}

//转发请标明出处,原文地址:

365bet亚洲真人 1

 

2.前序遍历:先访问根结点,前序遍历左子树,前序遍历右子树;中左右

voidPostOrder_Nonrecursive(BiTree T)// 后序遍历的非递归     双栈法

{

stack s1 , s2;

BiTree curr ;// 指向当前要检查的节点

s1.push(T);

while(!s1.empty())// 栈空时停止

{

curr = s1.top();

s1.pop();

s2.push(curr);

if(curr->lchild)

s1.push(curr->lchild);

if(curr->rchild)

s1.push(curr->rchild);

}

while(!s2.empty())

{

printf(“%c “, s2.top()->data);

s2.pop();

}

}

intvisit(BiTree T)

{

if(T)

{

printf(“%c “,T->data);

return1;

}

else

return0;

}

2. 布局算法

  

  借使虚结点输入时以空格字符表示,相应的社团算法为:

  void CreateBinTree (BinTree *T)

  {
//构造二叉链表。T是指向根指针的指针,故修改*T就修改了实参(根指针)本身

  char ch;

  if((ch=getchar())==”) *T=NULL; //读人空格,将相应指针置空

  else{ //读人非空格

  *T=(BinTNode *)malloc(sizeof(BinTNode)); //生成结点

  (*T)->data=ch;

  CreateBinTree(&(*T)->lchild); //构造左子树

  CreateBinTree(&(*T)->rchild); //构造右子树

  }

  }

  注意:

  调用该算法时,应将待建立的二叉链表的根指针的位置作为实参。

  

2.子女表示法:

3.将二叉树中各类结点的空指针引出一个虚结点,其值为特定值#,处理二叉树为原二叉树的扩张二叉树,扩大二叉树做到一个遍历系列确定一棵二叉树

//中序遍历的算法程序

voidInOrder(BiTNode *root)

{

if(root==NULL)

return;

InOrder(root->lchild);//递归调用,前序遍历左子树

printf(“%c “, root->data);//输出数据

InOrder(root->rchild);//递归调用,前序遍历右子树

}

遍历连串

  

  1.遍历二叉树的执行踪迹

  三种递归遍历算法的搜索路线相同(如下图虚线所示)。

  具体路线为:

  从根结点出发,逆时针沿着二叉树外缘移动,对各样结点均途径一遍,最后回来根结点。

  2.遍历种类

  A

  / \

  B C

  / / \

  D E F

  图

  (1) 中序连串(inorder traversal)

  中序遍历二叉树时,对结点的访问次序为中序种类

  【例】中序遍历上图所示的二叉树时,得到的中序种类为:

  D B A E C F

  (2) 先序序列(preorder traversal)

  先序遍历二叉树时,对结点的走访次序为先序种类

  【例】先序遍历上图所示的二叉树时,获得的先序种类为:

  A B D C E F

  (3) 后序体系(postorder traversal)

  后序遍历二叉树时,对结点的拜会次序为后序系列

  【例】后序遍历上图所示的二叉树时,得到的后序连串为:

  D B E F C A

  (4)层次遍历(level
traversal)二叉树的操作定义为:若二叉树为空,则脱离,否则,依据树的布局,从根发轫自上而下,自左而右访问每一个结点,从而完结对每一个结点的遍历

[编辑本段]

注意事项

  (1)在寻觅路线中,若访问结点均是首先次通过结点时开展的,则是前序遍历;若访问结点均是在其次次(或第四次)经过结点时进行的,则是中序遍历(或后序遍历)。只要将追寻路线上保有在率先次、第二次和第一次通过的结点分别列表,即可分别获得该二叉树的前序连串、中序连串和后序种类。

  (2)上述二种队列都是线性系列,有且仅有一个先河结点和一个极限结点,其他结点都有且仅有一个前趋结点和一个后继结点。为了分歧于树形结构中前趋(即双亲)结点和后继(即男女)结点的概念,对上述三种线性种类,要在某结点的前趋和后继以前冠以其遍历次序名称。

  【例】上图所示的二叉树中结点C,其前序前趋结点是D,前序后继结点是E;中序前趋结点是E,中序后继结点是F;后序前趋结点是F,后序后继结点是A。然而就该树的逻辑结构而言,C的前趋结点是A,后继结点是E和F。

[编写本段]

二叉链表的协会

  

在每个结点中,附设一个提示器提示其父母结点到链表中的地方。
结点结构为:data |
parent

365bet亚洲真人 2

voidLeverTraverse(BiTree T)//方法一、非递归层次遍历二叉树

{

queue  Q;

BiTree p;

p = T;

if(visit(p)==1)

Q.push(p);

while(!Q.empty())

{

p = Q.front();

Q.pop();

if(visit(p->lchild) == 1)

Q.push(p->lchild);

if(visit(p->rchild) == 1)

Q.push(p->rchild);

}

}

中序遍历的算法已毕

   

  用二叉链表做为存储结构,中序遍历算法可讲述为:

  void InOrder(BinTree T)

  { //算法里①~⑥是为着表达履行进度到场的标号

  ① if(T) { // 假设二叉树非空

  ② InOrder(T->lchild);

  ③ printf(“%c”,T->data); // 访问结点

  ④ InOrder(T->rchild);

  ⑤ }

  ⑥ } // InOrder

  

**当以二叉树做作树的贮存结构时,树的先根遍历和后跟遍历完全可以借用二叉树的前序遍历和中序遍历的算法来兑现。

1.行使递归的规律,只可是在原来打印结点的地点,改成了转变结点,给结点赋值的操作
if(ch==’#’){*T=NULL;}else{malloc();(*T)->data=ch;createFunc((*T)->lchild);createFunc((*T)->rchild);}

//后序遍历的算法程序

voidPostOrder(BiTNode *root)

{

if(root==NULL)

return;

PostOrder(root->lchild);//递归调用,前序遍历左子树

PostOrder(root->rchild);//递归调用,前序遍历右子树

printf(“%c “, root->data);//输出数据

}

/*

二叉树的非递归前序遍历,前序遍历思想:先让根进栈,只要栈不为空,就可以做弹出操作,

历次弹出一个结点,记得把它的左右结点都进栈,记得右子树先进栈,那样可以确保右子树在栈中总处于左子树的上边。

*/

遍历算法

  

  1.中序遍历的递归算法定义:

  若二叉树非空,则相继执行如下操作:

  (1)遍历左子树;

  (2)访问根结点;

  (3)遍历右子树。

  2.先序遍历的递归算法定义:

  若二叉树非空,则相继执行如下操作:

  (1) 访问根结点;

  (2) 遍历左子树;

  (3) 遍历右子树。

  3.后序遍历得递归算法定义:

  若二叉树非空,则相继执行如下操作:

  (1)遍历左子树;

  (2)遍历右子树;

  (3)访问根结点。

  4.层次遍历

  

                       树(一对多的数据结构)

voidPreOrder_Nonrecursive2(BiTree T)//先序遍历的非递归

{

if(!T)

return;

stack s;

while(T)// 左子树上的节点全部压入到栈中

{

s.push(T);

cout<data<<”  “;

T = T->lchild;

}

while(!s.empty())

{

BiTree temp = s.top()->rchild;// 栈顶元素的右子树

s.pop();// 弹出栈顶元素

while(temp)// 栈顶元素存在右子树,则对右子树同样遍历到最下方

{

cout<data<<”  “;

s.push(temp);

temp = temp->lchild;

}

}

}

voidInOrderTraverse1(BiTree T)// 中序遍历的非递归

{

if(!T)

return;

BiTree curr = T;// 指向当前要反省的节点

stack s;

while(curr != NULL || !s.empty())

{

while(curr != NULL)

{

s.push(curr);

curr = curr->lchild;

}//while

if(!s.empty())

{

curr = s.top();

s.pop();

cout<data<<”  “;

curr = curr->rchild;

}

}

}

遍历方案

  

  从二叉树的递归定义可见,一棵非空的二叉树由根结点及左、右子树那七个基本部分构成。由此,在任一给定结点上,可以按某种次序执行五个操作:

  (1)访问结点本身(N),

  (2)遍历该结点的左子树(L),

  (3)遍历该结点的右子树(R)。

  以上二种操作有八种实施顺序:

  NLR、LNR、LRN、NRL、RNL、RLN。

  注意:

  前三种次序与后二种次序对称,故只谈谈先左后右的前几种次序。

  

##二叉树的遍历:是指从根结点出发,按照某种次序依次走访二叉树中装有结点,使得种种结点呗访问一回且仅被访问四回。

voidPostOrder_Nonrecursive1(BiTree T)// 后序遍历的非递归

{

stack S;

BiTree curr = T ;// 指向当前要反省的节点

BiTree previsited = NULL;// 指向前一个被访问的节点

while(curr != NULL || !S.empty())// 栈空时停止

{

while(curr != NULL)// 一贯向左走直到为空

{

S.push(curr);

curr = curr->lchild;

}

curr = S.top();

// 当前节点的右孩子只要为空或者已经被访问,则做客当前节点

if(curr->rchild == NULL || curr->rchild == previsited)

{

cout<data<<”  “;

previsited = curr;

S.pop();

curr = NULL;

}

else

curr = curr->rchild;// 否则做客右孩子

}

}

1. 主导考虑

  

  基于先序遍历的结构,即以二叉树的先序连串为输入构造。

  注意:

  先序系列中务必进入虚结点以示空指针的任务。

  【例】

  建立上图所示二叉树,其输入的先序种类是:ABD∮∮∮CE∮∮F∮∮。

  

 

voidInOrderTraverse(BiTree T)// 中序遍历的非递归

{

if(!T)

return;

stack s;

BiTree curr = T->lchild;// 指向当前要反省的节点

s.push(T);

while(curr != NULL || !s.empty())

{

while(curr != NULL)// 一向向左走

{

s.push(curr);

curr = curr->lchild;

}

curr = s.top();

s.pop();

cout<data<<”  “;

curr = curr->rchild;

}

}

三种遍历的命名

  

  依据访问结点操作爆发地方命名:

  ① NLR:前序遍历(PreorderTraversal亦称(先序遍历))

  ——访问结点的操作暴发在遍历其左右子树往日。

  ② LNR:中序遍历(InorderTraversal)

  ——访问结点的操作发生在遍历其左右子树之中(间)。

  ③
LRN:后序遍历(PostorderTraversal)

  ——访问结点的操作暴发在遍历其左右子树之后。

  注意:

  由于被访问的结点必是某子树的根,所以N(Node)、L(Left
subtree)和R(Right
subtree)又可诠释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称之为先根遍历、中根遍历和后根遍历。

  

 

//前序遍历的算法程序

voidPreOrder(BiTNode *root)

{

if(root==NULL)

return;

printf(“%c “, root->data);//输出数据

PreOrder(root->lchild);//递归调用,前序遍历左子树

PreOrder(root->rchild);//递归调用,前序遍历右子树

}

3.根结点唯有左子树。

#include

二叉树的特征有:

#include

4.层序遍历:规则是若树为空,则空操作重回,否则从树的首先层,也就是根结点伊始走访,从上而下逐层遍历,在同一层中,按从左到右的相继对结点逐个访问。

//二叉树结点的叙述

typedefstructBiTNode

{

chardata;

structBiTNode *lchild, *rchild;//左右子女

}BiTNode,*BiTree;

##树、森林与二叉树的更换

voidLevelOrder(BiTree BT)//方法二、非递归层次遍历二叉树

{

BiTNode *queue[10];//定义队列有十个空中

if(BT==NULL)

return;

intfront,rear;

front=rear=0;

queue[rear++]=BT;

while(front!=rear)//如果队尾指针不对等对头指针时

{

cout<data<<”  “;//输出遍历结果

if(queue[front]->lchild!=NULL)//将队首结点的左孩子指针入队列

{

queue[rear]=queue[front]->lchild;

rear++;//队尾指针后移一位

}

if(queue[front]->rchild!=NULL)

{

queue[rear]=queue[front]->rchild;//将队首结点的右孩子指针入队列

rear++;//队尾指针后移一位

}

front++;//对头指针后移一位

}

}

intdepth(BiTNode *T)//树的深度

{

if(!T)

return0;

intd1,d2;

d1=depth(T->lchild);

d2=depth(T->rchild);

return(d1>d2?d1:d2)+1;

//return (depth(T->lchild)>depth(T->rchild)?depth(T->lchild):depth(T->rchild))+1;

}

intCountNode(BiTNode *T)

{

if(T == NULL)

return0;

return1+CountNode(T->lchild)+CountNode(T->rchild);

}

intmain(void)

{

BiTNode *root=NULL;//定义一个根结点

intflag=1,k;

printf(”                     本程序达成二叉树的基本操作。\n”);

printf(“可以拓展确立二叉树,递归先序、中序、后序遍历,非递归先序、中序遍历及非递归层序遍历等操作。\n”);

while(flag)

{

printf(“\n”);

printf(“|————————————————————–|\n”);

printf(“|                    二叉树的基本操作如下:                     |\n”);

printf(“|                        0.创办二叉树                          |\n”);

printf(“|                        1.递归先序遍历                        |\n”);

printf(“|                        2.递归中序遍历                        |\n”);

printf(“|                        3.递归后序遍历                        |\n”);

printf(“|                        4.非递归先序遍历                      |\n”);

printf(“|                        5.非递归中序遍历                      |\n”);

printf(“|                        6.非递归后序遍历                      |\n”);

printf(“|                        7.非递归层序遍历                      |\n”);

printf(“|                        8.二叉树的纵深                        |\n”);

printf(“|                        9.二叉树的结点个数                    |\n”);

printf(“|                        10.退出程序                            |\n”);

printf(“|————————————————————–|\n”);

printf(”                        请拔取功效:”);

scanf(“%d”,&k);

switch(k)

{

case0:

printf(“请建立二叉树并输入二叉树的根节点:”);

CreateBiTree(&root);

break;

case1:

if(root)

{

printf(“递归先序遍历二叉树的结果为:”);

PreOrder(root);

printf(“\n”);

}

else

printf(”          二叉树为空!\n”);

break;

case2:

if(root)

{

printf(“递归中序遍历二叉树的结果为:”);

InOrder(root);

printf(“\n”);

}

else

printf(”          二叉树为空!\n”);

break;

case3:

if(root)

{

printf(“递归后序遍历二叉树的结果为:”);

PostOrder(root);

printf(“\n”);

}

else

printf(”          二叉树为空!\n”);

break;

case4:

if(root)

{

printf(“非递归先序遍历二叉树:”);

PreOrder_Nonrecursive1(root);

printf(“\n”);

}

else

printf(”          二叉树为空!\n”);

break;

case5:

if(root)

{

printf(“非递归中序遍历二叉树:”);

InOrderTraverse1(root);

printf(“\n”);

}

else

printf(”          二叉树为空!\n”);

break;

case6:

if(root)

{

printf(“非递归后序遍历二叉树:”);

PostOrder_Nonrecursive(root);

printf(“\n”);

}

else

printf(”          二叉树为空!\n”);

break;

case7:

if(root)

{

printf(“非递归层序遍历二叉树:”);

//LeverTraverse(root);

LevelOrder(root);

printf(“\n”);

}

else

printf(”          二叉树为空!\n”);

break;

case8:

if(root)

printf(“那棵二叉树的纵深为:%d\n”,depth(root));

else

printf(”          二叉树为空!\n”);

break;

case9:

if(root)

printf(“那棵二叉树的结点个数为:%d\n”,CountNode(root));

else

printf(”          二叉树为空!\n”);

break;

default:

flag=0;

printf(“程序运行停止,按任意键退出!\n”);

}

}

system(“pause”);

return0;

}

 

usingnamespacestd;

树的存储结构:
养父母表示法、孩子表示法、孩子兄弟表示法。

voidPreOrder_Nonrecursive1(BiTree T)//先序遍历的非递归

{

if(!T)

return;

stack s;

BiTree curr = T;

while(curr != NULL || !s.empty())

{

while(curr != NULL)

{

cout<data<<”  “;

s.push(curr);

curr = curr->lchild;

}

if(!s.empty())

{

curr = s.top();

s.pop();

curr = curr->rchild;

}

}

}

#头脑二叉树结构已毕:
/*二叉树的二叉线索存储结构定义*/
typedef
enum(Link,Thread) PointerTag; /*Link==0代表针对左右儿女指针*/
/*Thread==1表示针对前驱或后继的端倪*/
typedef struct
BiThrNode /*二叉树线索存储结点结构*/
{
TElemType data;
/*结点数据*/
struct BiThrNode
*lchild, *rchild; /*反正孩子指针*/
PointerTag
LTag;
PointerTag RTag;
/*左右标明*/
}BiThrNode,
*BiThree;

二叉树遍历方法
1.前序遍历:规则是若二叉树为空,则空操作重返,否则先走访根结点,然后前序遍历左子树,再前序遍历右子树。

*线索二叉树的时刻复杂度为O(n).

 

exit(OVERFLOW);
(*T)->data=ch;
/*生成根结点*/

##二叉树的确立:建立二叉树,也是应用了递归的法则。只不过在原来应该是打印结点的地点,改成了变通结点,给结点赋值的操作而已。
**对二叉树举行拓展:将二叉树中各样结点的空指针引出一个虚节点,其值唯一特定值,比如”#“。

用前序遍历生成二叉树:
/*按前序输入二叉树中结点的值(一个字符)*/
/**
#意味着空树,构造二叉链表表示二叉树T。*/
void
CreateBiTree(BiTree *T)
{
TElemType ch;
scanf(“%c”,
&ch);
if(ch==’#’)
*T=NULL;
else
{

5.根结点既有左子树又有右子树。

 

二叉树每个结点最多有四个男女,所以为它设计一个数据域和五个指针域是比较自然的想法,大家称那样的链表叫做二叉链表。

二叉树的顺序存储结构就是用一维数组存储二叉树中的结点,并且结点的存储地方,也就是数组的下标要能突显结点之间的逻辑关系。

发表评论

电子邮件地址不会被公开。 必填项已用*标注