菜单

二叉树遍历

2019年1月31日 - 金沙编程资讯

图片 1

//后序遍历的算法程序

voidPostOrder(BiTNode *root)

{

if(root==NULL)

return;

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

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

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

}

/*

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

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

*/

概念  

 

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

//前序遍历的算法程序

voidPreOrder(BiTNode *root)

{

if(root==NULL)

return;

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

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

PreOrder(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。

[编辑本段]

二叉链表的协会

  

#赫夫曼编码
*若要设计长度不等的编码,则必须是任一字符的编码都不是另一个字符的编码的前缀,那种编码称作前缀编码。

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

//二叉树结点的叙说

typedefstructBiTNode

{

chardata;

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

}BiTNode,*BiTree;

二叉树的遍历搜索路径

 所谓遍历(Traversal)是指沿着某条搜索路线,依次对树中每个结点均做三回且仅做一回访问。访问结点所做的操作信赖于实际的选择问题。

  遍历是二叉树上最重大的演算之一,是二叉树上举办任何运算之基础。

[编制本段]

算法与落到实处

  

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

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

#include

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); //构造右子树

  }

  }

  注意:

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

  

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

 

//中序遍历的算法程序

voidInOrder(BiTNode *root)

{

if(root==NULL)

return;

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

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

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

}

中序遍历的算法完成

   

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

  void InOrder(BinTree T)

  { //算法里①~⑥是为了印证履行进度参预的标注

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

  ② InOrder(T->lchild);

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

  ④ InOrder(T->rchild);

  ⑤ }

  ⑥ } // InOrder

  

*尽管树中某结点唯有一棵子树,也要差别它是左子树还是右子树。

<?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
  }
}

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;

}

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();

  }

  }

3.后序遍历:规则是若树为空,则空操作再次来到,否则从左到右先叶子后结点的章程遍历访问左右子树,最终是访问根结点。

  

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

1. 中央思维

  

  基于先序遍历的社团,即以二叉树的先序系列为输入构造。

  注意:

  先序连串中务必投入虚结点以示空指针的岗位。

  【例】

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

  

##二叉树的建立:建立二叉树,也是选取了递归的法则。只但是在原来应该是打印结点的地方,改成了扭转结点,给结点赋值的操作而已。
**对二叉树举办举行:将二叉树中种种结点的空指针引出一个虚节点,其值唯一特定值,比如”#“。

  

#include

两种遍历的命名

  

  根据访问结点操作发生地方命名:

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

  ——访问结点的操作发生在遍历其左右子树从前。

  ② LNR:中序遍历(InorderTraversal)

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

  ③
LRN:后序遍历(PostorderTraversal)

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

  注意:

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

  

PreOrderTraverse(T->lchild); /*再先序遍历左子树*/

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;

}

}

}

图片 2

#二叉树转换为森林
1.从根结点先河,若右孩子存在,则把与右孩子结点的连线删除,在翻看分离后的二叉树,若右孩子存在,则连线删除……,直到所有右孩子连线都剔除截至,获得分离的二叉树。
2.再将每棵分离后的二叉树转换为树即可。

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);

}

}

遍历方案

  

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

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

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

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

  以上两种操作有多种实施顺序:

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

  注意:

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

  

3.男女兄弟表示法:

#include

遍历算法

  

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

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

  (1)遍历左子树;

  (2)访问根结点;

  (3)遍历右子树。

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

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

  (1) 访问根结点;

  (2) 遍历左子树;

  (3) 遍历右子树。

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

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

  (1)遍历左子树;

  (2)遍历右子树;

  (3)访问根结点。

  4.层次遍历

  

3.根结点唯有左子树。

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;

}

}

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);

}

}

二叉树的品质
1.性质1:在二叉树的第i层上至多有2∧i-1个结点(i>=1)。
2.性质2:深度为k的二叉树至多有2∧k
-1个结点(k>=1)。
3.性质3:对其余一棵二叉树T,借使其终端结点数为n0,度为2的结点数为n2,则n0=n2+1。
4.性质4:具有n个结点的通通二叉树的吃水为[log2n]+1
([x]意味着不大于x的最大整数。
5.性质5:假设对一棵有n个结点的完全二叉树(其深度为[log2n]+1)
的结点按层序编号(从第1层到[log2n]+1层,每层从左到右),对任一节点i(1≦i≦n)有:
*.即使i=1,则结点i是二叉树的根,无大人;假设i>1,
则其家长是结点[i/2]。
*.即使2i>n,
则结点i无左孩子(结点i为叶子结点);否则其左孩子是结点2i。
*.假若2i+1>n,
则结点i无右孩子;否则其右孩子是结点2i+1。

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;

}

}

}

树与丛林的遍历
树的遍历分为三种方法
1.一种是先根遍历树,即先访问树的根结点,然后逐一先根遍历根的每棵子树。、
2.另一种是后跟遍历,即先逐一后根遍历每棵子树,然后再拜访根结点。

usingnamespacestd;

二叉树的表征有:

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;// 否则做客右孩子

}

}

4.根结点唯有右子树。

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

//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));

}

}

InOrderTraverse(T->lchild); /*中序遍历左子树*/
printf(“%c”,
T->data); /*来得结点数据,可以更改为别的对结点操作*/

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;

}

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

 

2.子女表示法:

*诚如地,设必要编码的字符集为{d1,d2,…,dn},各类字符在电文中出现的次数或频率集合为{w1,w2,…,wn},以d1,d2,…,dn作为叶子结点,以w1,w2,…,wn作为相应叶子结点的权值来布局一棵赫夫曼树。规定赫夫曼树的左分支代表0,右分支代表1,则从根结点到叶子结点所通过的不二法门分支组成的0和1的队列便为该结点对应字符的编码,那就是赫夫曼编码。

头脑二叉树:指向后驱和后继的指针称为线索,加上线索的二叉链表称为线索链表,相应的二叉树就称为线索二叉树。

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

*顺序存储结构相似只用于完全二叉树。

丛林的遍历也分为三种艺术:
1.前序遍历:先走访森林中第一棵树的根结点,然后再依次县根遍历根的每棵子树,再相继用同一格局遍历除去第一棵树的剩余树构成的树林。
2.后序遍历:是先走访森林中首先棵树,后跟遍历的主意遍历每棵子树,然后再拜访根结点,再逐一同样措施遍历除去第一棵树的剩余树构成的林子。

 

树的此外连锁概念:
结点的层次从根早先定义起,根为第一层,根的儿女为第二层。若某结点在第I层,则其子树的根就在第I+1层。其家长在一如既往层的结点互为堂兄弟。
树中结点的最大层次称为树的纵深或可观。
借使将树种结点的各子树看成从左至右是有程序的,不可以调换的,则称该树为有序树,否则称为无序树。
密林是m(m>=0)课互不相交的树的聚集。

2.满二叉树:在一棵二叉树中。即使持有支行结点都存在左子树和右子树,并且拥有叶子都在平等层上,那样的二叉树称为满二叉树。
满二叉树的表征有:
*叶子只好出现在嘴下一层。出现在此外层就无法高达平衡。
*非叶子结点的度一定是2。
*在同等深度的二叉树中,满二叉树的结点个数最多,叶子数最多。

相关文章

发表评论

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

网站地图xml地图