【bf88必发唯一官网】数据结构,很好的稿子

by admin on 2019年1月31日

1.施用递归的法则,只但是在原本打印结点的地点,改成了扭转结点,给结点赋值的操作
if(ch==’#’){*T=NULL;}else{malloc();(*T)->data=ch;createFunc((*T)->lchild);createFunc((*T)->rchild);}

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

概念  

                       树(一对多的数据结构)

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

#include

bf88必发唯一官网 1

树(Tree)是n(n>=0)个结点的有限集。n=0时号称空树。在自由一颗非空树种:

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

#include

二叉树的遍历搜索路径

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

  遍历是二叉树上最主要的运算之一,是二叉树上进行任何运算之基础。

[编写本段]

算法与落到实处

  

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

bf88必发唯一官网 2

#include

遍历方案

  

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

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

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

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

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

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

  注意:

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

  

(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()     //再次回到结点指针类型

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

}

}

【bf88必发唯一官网】数据结构,很好的稿子。中序遍历的算法完成

   

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

  void InOrder(BinTree T)

  { //算法里①~⑥是为了求证履行进程加入的标注

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

  ② InOrder(T->lchild);

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

  ④ InOrder(T->rchild);

  ⑤ }

  ⑥ } // InOrder

  

结点间涉及:
结点的子树的跟称为该结点的子女,相应地,该结点称为孩子的父母。
同一个父母的子女之间互称兄弟,结点的祖先是从根到该结点所经分支上的保有结点。

  

//前序遍历的算法程序

voidPreOrder(BiTNode *root)

【bf88必发唯一官网】数据结构,很好的稿子。{

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

bf88必发唯一官网,}

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的行列便为该结点对应字符的编码,那就是赫夫曼编码。

 

发表评论

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

网站地图xml地图