【www.5929.com】数据结构学习笔记,二叉树遍历

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

//转发请标明出处,原文地址:【www.5929.com】数据结构学习笔记,二叉树遍历。

概念  

                       树(一对多的数据结构)

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

#include

www.5929.com 1

树(Tree)是n(n>=0)个结点的有限集。n=0时称之为空树。在随心所欲一颗非空树种:

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

#include

二叉树的遍历搜索路径

 所谓遍历(Traversal)是指沿着某条搜索路线,依次对树中各种结点均做两次且仅做五遍访问。访问结点所做的操作信赖于现实的选取难题。

  遍历是二叉树上最重点的运算之一,是二叉树上举办其余运算之基础。

[编辑本段]

算法与已毕

  

(1)有且仅有一个一定的名为根(Root)的结点;

www.5929.com 2

#include

遍历方案

  

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

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

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

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

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

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

  注意:

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

www.5929.com,  

(2)当n>1时,其余结点可分为m(m>0)个互不相交的点滴集T1、T2、……、Tn,其中每一个汇合本身又是一棵树,并且称为根的子树。

 

usingnamespacestd;

二种遍历的命名

  

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

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

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

  ② LNR:中序遍历(InorderTraversal)

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

  ③
LRN:后序遍历(PostorderTraversal)

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

  注意:

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

  

对于树的定义还亟需强调两点:
1.n>0时根结点是唯一的,不容许存在七个根结点,数据结构中的树只好有一个根结点。
2.m>0时,子树的个数没有界定,但它们必然是互不相交的。

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

//二叉树结点的描述

typedefstructBiTNode

{

chardata;

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

}BiTNode,*BiTree;

遍历算法

  

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

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

  (1)遍历左子树;

  (2)访问根结点;

  (3)遍历右子树。

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

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

  (1) 访问根结点;

  (2) 遍历左子树;

  (3) 遍历右子树。

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

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

  (1)遍历左子树;

  (2)遍历右子树;

  (3)访问根结点。

  4.层次遍历

  

结点分类:
结点拥有的子树数称为结点的度。度为0的结点称为叶结点或极端结点;度不为0的结点称为非终端结点或分段结点。除根结点之外,分支结点也叫做内部结点。树的度是树内各结点的度的最大值。

  

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

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

【www.5929.com】数据结构学习笔记,二叉树遍历。//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));

}

}

中序遍历的算法达成

   

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

  void InOrder(BinTree T)

  { //算法里①~⑥是为着验证履行进度插手的标号

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

  ② InOrder(T->lchild);

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

  ④ InOrder(T->rchild);

  ⑤ }

  ⑥ } // InOrder

  

结点间关系:
结点的子树的跟称为该结点的孩子,相应地,该结点称为孩子的老人家。
同一个老人家的孩子之间互称兄弟,结点的上代是从根到该结点所经分支上的拥有结点。

  

//前序遍历的算法程序

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。

[编制本段]

二叉链表的结构

  

树的其他连锁概念:
结点的层次从根开始定义起,根为第一层,根的男女为第二层。若某结点在第I层,则其子树的根就在第I+1层。其家长在同等层的结点互为堂兄弟。
树中结点的最大层次称为树的深浅或可观。
设若将树种结点的各子树看成从左至右是条理清楚的,不可以沟通的,则称该树为平稳树,否则称为无序树。
丛林是m(m>=0)课互不相交的树的聚众。

//中序遍历的算法程序

voidInOrder(BiTNode *root)

{

if(root==NULL)

return;

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

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

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

}

1. 中坚思想

  

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

  注意:

  先序种类中必须进入虚结点以示空指针的职位。

  【例】

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

  

 

//后序遍历的算法程序

voidPostOrder(BiTNode *root)

{

if(root==NULL)

return;

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

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

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

}

/*

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

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

*/

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

  }

  }

  注意:

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

  

树的仓储结构:
老人表示法、孩子表示法、孩子兄弟表示法。

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

}

}

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

  }

  }

1.老人家表示法(时间复杂度为O(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;

}

}

}

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

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;

}

}

}

内部data是数据域,存储结点的数据信息。而parent是指针域,存储该结点的父三姑在数组中的下标。

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;

}

}

是因为根结点是绝非家长的,所以大家约定根结点的位置域设置为-1.

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

}

}

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;

}

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

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

}

}

为此,设计三种结点结构:

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;

}

一个是孩子链表的子女结点, child | next
中间child是数据域,用来存储某个结点在表头数组中的下标。next是指针域,用来储存指向某结点的下一个男女结点的指针。

另一个是表头数组的表头结点, data | firstchild
其间data是数据域,存储某结点的数码信息。firstchild是头指针域,存储该结点的男女链表的头指针。

3.儿女兄弟表示法:

自由一棵树,它的结点的第三个孩子只要存在就是绝无仅有的,它的右兄弟如果存在也是绝无仅有的。因而,大家设置五个指针,分别指向该结点的率先个男女和此结点的右兄弟。

结点结构如表所示:
data | firstchild |
rightsib
个中data是数据域,first
child为指针域,存储该结点的率先个孩子结点的贮存地方,rightsib是指针域,存储该结点的右兄弟结点的积存地方。

 

                              二叉树

二叉树的定义:二叉树是n(n>=0)个结点的星星集合,该集合或者为空集(称为空二叉树),或者由一个根结点和两棵互不相交的、分别名叫根结点的左子树和右子树组成。(在某个阶段都是二种结果的境况)

二叉树的特点有:

*各类结点最多有两颗子树,所以二叉树中不存在度大于2的结点。

*左子树和右子树是有各类的,次序无法轻易颠倒。

*固然树中某结点唯有一棵子树,也要分别它是左子树如故右子树。

二叉树具有各类基本造型:
1.空二叉树。

2.只有一个根结点。

3.根结点只有左子树。

4.根结点唯有右子树。

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

 

卓越二叉树:
1.斜树:所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。那二者统称为斜树。

2.满二叉树:在一棵二叉树中。即使具有支行结点都设有左子树和右子树,并且有所叶子都在平等层上,那样的二叉树称为满二叉树。
满二叉树的风味有:
*叶子只好出现在嘴下一层。出现在别的层就不容许落成平衡。
*非叶子结点的度自然是2。
*在同一深度的二叉树中,满二叉树的结点个数最多,叶子数最多。

3.截然二叉树:对一颗具有n个结点的二叉树按层编号,如果编号为i(1<=i<=n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中地方完全相同,则那棵二叉树称为完全二叉树。
完全二叉树的风味:
*满二叉树一定是一棵完全二叉树,但完全二叉树不必然是满的。

*叶子结点只可以出现在最下两层。
*最下层的叶子一定集中在左部屡次三番地点。
*尾数二层,若有叶子结点,一定都在右部接二连三地方。
*比方结点度为1,则该结点唯有左孩子,即不设有唯有右子树的图景。
*一律结点的二叉树,完全二叉树的吃水最小。

**判断某二叉树是不是是完全二叉树:

给种种结点根据二叉树的布局逐层顺序编号,假如编号现身空挡,就证实不是全然二叉树,否则就是。

 

二叉树的质量
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。

 

##二叉树的仓储结构

1.二叉树的顺序存储结构:

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

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

2.二叉链表(链式存储结构)

二叉树每个结点最多有多少个男女,所以为它安顿一个数据域和多个指针域是比较自然的想法,我们称那样的链表叫做二叉链表。

 

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

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

2.中序遍历:规则是若树为空,则空操作再次回到,否则从根结点初叶(注意并不是先访问根结点),中序遍历根结点的左子树,然后是访问根结点,最后中序遍历右子树。

3.后序遍历:规则是若树为空,则空操作重临,否则从左到右先叶子后结点的主意遍历访问左右子树,最终是访问根结点。

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

*前序遍历算法:
/*二叉树的前序遍历递归算法*/
void
PreOrderTraverse(BiTree T)
{
if(T==NULL)
return;
printf(“%c”,
T-?lchild); /*呈现结点数据,可以变动为此外对结点操作*/

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

PreOrderTraverse(T->rchild); /*最后先序遍历右子树*/
}

*中序遍历算法:
/*二叉树的中序遍历递归算法*/
void
InOrderTraverse(BiTree T)
{
if(T==NULL)
return;

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

InOrderTraverse(T->rchild); /*终极中序遍历右子树*/
}

*后序遍历算法:
/*二叉树的后序遍历递归算法*/
void
PostOrderTraverse(BiTree T)
{
if(T==NULL)
return;

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

PostOrderTraverse(T->rchild); /*再持续遍历右子树*/
printf(“%c”,
T->data); /*来得结点数据,可以变更为别的对结点操作*/
}

**已知前序遍历系列和中序遍历系列,可以唯一确定一棵二叉树。

已知后序遍历连串和中序遍历系列,可以唯一确定一棵二叉树。

 

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

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

*T=(BiTree)malloc(sizeof(BiTNode));
if(!*T)

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

CreateBiTree(&(*T)->lchild); /*布局左子树*/

CreateBiTree(&(*T)->rchild); /*结构右子树*/
}
}

 

##线索二叉树

*对于一个有n个结点的儿茶链表,每个结点有指向左右孩子的五个指针域,所以一共是2n个指针域。而n个结点的二叉树一共有n-1条分支线数,也就是说,其实是存在2n-1(n-1)=n+1个空指针域。

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

*头脑二叉树,等于是把一棵二叉树转变成了一个双向链表。

*对二叉树以某种次序遍历使其成为线索二叉树的历程称作是线索化。

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

*线索化的原形就是将二叉链表中的空指针改为指向前驱或后继的线索。由于前驱和后继的新闻唯有在遍历该二叉树时才能赢得,所以线索化的历程就是在遍历的长河中修改空指针的长河。

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

#假诺所用的二叉树需平日遍历或探寻结点时须求某种遍历连串中的前驱和后继,那么选拔线索二叉链表的存储结构就是不行不利的选料。

 

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

#.树转换为二叉树
1.加线。在富有兄弟结点之间加一条连线。
2.去线。对树中种种结点,只保留它与第四个儿女结点的连线,删除它与任何儿女结点之间的连线。
3.层次调整。以树的根结点为轴心,将整棵树顺时针旋转一定的角度,使之结构层次分明。注意第三个男女是二叉树结点的左孩子,兄弟转换过来的子女是结点的右孩子。

#林子转换为二叉树
1.把各种树转换为二叉树。
2.先是棵二叉树不动,从第二棵二叉树开始,依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子,用线连接起来。当所有的二叉树连接起来后就收获了由森林转换来的二叉树。

#二叉树转换为树
1.加线。若某结点的右孩子存在,则将做左孩子的n各右孩子结点都看作此结点的孩子。将该结点与那一个右孩子结点用线连接起来。
2.去线。删除原二叉树中有着结点与其右孩子结点的连线。
3.层次调整。使之结构层次明显。

***看清一棵二叉树能够转换成一棵树仍旧森林,就是即便看那棵二叉树的根结点有没有右孩子,有就是树林,没有就是一棵树。

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

 

 

树与丛林的遍历
树的遍历分为二种艺术
1.一种是先根遍历树,即先访问树的根结点,然后挨家挨户先根遍历根的每棵子树。、
2.另一种是后跟遍历,即先逐一后根遍历每棵子树,然后再拜访根结点。

 

丛林的遍历也分为三种方法:
1.前序遍历:先访问森林中首先棵树的根结点,然后再依次县根遍历根的每棵子树,再相继用相同办法遍历除去第一棵树的剩余树构成的树丛。
2.后序遍历:是先访问森林中首先棵树,后跟遍历的点子遍历每棵子树,然后再拜访根结点,再逐一同样方式遍历除去第一棵树的剩余树构成的老林。

 

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

 

 

赫夫曼树及其使用
1、路径和途径长度
  在一棵树中,从一个结点往下能够已毕的男女或子孙结点之间的通路,称为路径。通路中拨出的多寡称为路径长度。若规定根结点的层数为1,则从根结点到第L层结点的路子长度为L-1。
2、结点的权及带权路径长度
  若将树中结点赋给一个颇具某种意义的数值,则那个数值称为该结点的权。结点的带权路径长度为:从根结点到该结点之间的不二法门长度与该结点的权的乘积。
3、树的带权路径长度
  树的带权路径长度规定为具备叶子结点的带权路径长度之和,记为WPL。
里头带权路径长度WPL最小的二叉树称作赫夫曼树。

 

#赫夫曼树的协会:
1.先把有权值得叶子结点根据从小到大的顺序排列成一个上行下效体系,即:A5,
E10, B15, D30, C40。
2.取头三个小小的权值的结点作为一个新节点N1的五个子结点,注意相对较小的是左孩子,那里就是A为N1的左孩子,E为N1的右孩子。新结点的权值为四个叶子权值得和5+10=15.
3.将N1替换A与E,插入有序种类中,保持从小到大排列。即:N115,B15,D30,C40.
4.再一次步骤2.将N1与B作为一个新节点N2的四个子结点。N2的权值=15+15=30。
5.将N2替换N1与B,插入有序种类中,保持从小到大排列。即:N230,D30,C40.
6.再一次步骤2.将N2于D作为一个新节点N3的三个子结点。N3的权值=30+30=60.
7.将N3替换N2与D,插入有序系列中,保持从小到大排列。即:C40,
N360.
8.重复步骤2.将C与N3作为一个新节点T的七个子结点,由于T即是根结点,已毕赫夫曼树的布局。

 

#布局赫夫曼树的赫夫曼算法描述:
1.基于给定的n个权值{w1,w2,…,wn}构成n棵二叉树的集合F={T1,T2,…,Tn},其中没棵二叉树Ti中唯有一个带权为w1根结点,其左右子树均为空。
2.在F中选择两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树,且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。
3.在F中删除那两棵树,同时将新收获的二叉树加入F中。
4.重复2和3步骤,直到F只含一棵树为止。那棵树便是赫夫曼树。

 

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

 

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

 

Leave a Comment.