二叉樹層序遍歷遞歸python（遞歸層次遍歷二叉樹）

本文目錄一覽：

• 1、Python 二叉樹的創建和遍歷、重建
• 2、編寫一個程序，實現二叉樹的先序遍歷，中序遍歷，後序遍歷的各種遞歸和非遞歸算法，以及層次遍歷的算法
• 3、層序遍歷二叉樹
• 4、求二叉樹的層次遍歷代碼，求高手！！！
• 5、二叉樹的層次遍歷算法

Python 二叉樹的創建和遍歷、重建

幾個有限元素的集合，該集合為空或者由一個根（Root）的元素及兩不相交的（左子樹和右子樹）的二叉樹組成，是有序樹，當集合為空時，稱為空二叉樹，在二叉樹中，一個元素也稱為一個結點。

前序遍歷：若二叉樹為空，則空操作返回，否則先訪問根結點，然後前序遍歷左子樹，再前序遍歷右子樹

中序遍歷：若樹為空，則空操作返回，否則從根結點開始（不是先訪問根結點），中序遍歷根結點的左子樹，然後訪問根節點，最後中序遍歷右子樹。

後序遍歷：若樹為空，則空操作返回，否則從左到右先訪問葉子結點後結點的方式遍歷左右子樹，最後訪問根節點。

層序遍歷：若樹為空，則空操作返回，否則從樹的每一層，即從根節點開始訪問，從上到下逐層遍歷，在同一層中，按從左到右的順序對結點逐個訪問。

假設已知後序遍歷和中序遍歷結果，從後序遍歷的結果可以等到最後一個訪問的結點是根節點，對於最簡單的二叉樹，此時在中序遍歷中找到根節點之後，可以分辨出左右子樹，這樣就可以重建出這個最簡單的二叉樹了。而對於更為複雜的二叉樹，重建得到根結點和暫時混亂的左右結點，通過遞歸將左右結點依次重建為子二叉樹，即可完成整個二叉樹的重建。（在得到根結點之後，需要在中序遍歷序列中尋找根結點的位置，並將中序序列拆分為左右部分，所以要求序列中不能有相同的數字，這是序列重建為二叉樹的前提。）

Root =None

strs=”abc##d##e##”   #前序遍歷擴展的二叉樹序列

vals =list(strs)

Roots=Create_Tree(Root,vals)#Roots就是我們要的二叉樹的根節點。

print(Roots)

inorderSearch = inOrderTraverse2(Roots)

print(inorderSearch)

編寫一個程序，實現二叉樹的先序遍歷，中序遍歷，後序遍歷的各種遞歸和非遞歸算法，以及層次遍歷的算法

文件 main.cpp 代碼如下：

#includemalloc.h // malloc()等

#includestdio.h // 標準輸入輸出頭文件，包括EOF(=^Z或F6)，NULL等

#includestdlib.h // atoi()，exit()

#includemath.h // 數學函數頭文件，包括floor()，ceil()，abs()等

#define ClearBiTree DestroyBiTree // 清空二叉樹和銷毀二叉樹的操作一樣

typedef struct BiTNode

{

int data; // 結點的值

BiTNode *lchild,*rchild; // 左右孩子指針

}BiTNode,*BiTree;

int Nil=0; // 設整型以0為空

void visit(int e)

{ printf(“%d “,e); // 以整型格式輸出

}

void InitBiTree(BiTree T)

{ // 操作結果：構造空二叉樹T

T=NULL;

}

void CreateBiTree(BiTree T)

{ // 算法6.4：按先序次序輸入二叉樹中結點的值(可為字符型或整型，在主程中定義)，

// 構造二叉鏈表表示的二叉樹T。變量Nil表示空(子)樹。修改

int number;

scanf(“%d”,number); // 輸入結點的值

if(number==Nil) // 結點的值為空

T=NULL;

else // 結點的值不為空

{ T=(BiTree)malloc(sizeof(BiTNode)); // 生成根結點

if(!T)

exit(OVERFLOW);

T-data=number; // 將值賦給T所指結點

CreateBiTree(T-lchild); // 遞歸構造左子樹

CreateBiTree(T-rchild); // 遞歸構造右子樹

}

}

void DestroyBiTree(BiTree T)

{ // 初始條件：二叉樹T存在。操作結果：銷毀二叉樹T

if(T) // 非空樹

{ DestroyBiTree(T-lchild); // 遞歸銷毀左子樹，如無左子樹，則不執行任何操作

DestroyBiTree(T-rchild); // 遞歸銷毀右子樹，如無右子樹，則不執行任何操作

free(T); // 釋放根結點

T=NULL; // 空指針賦0

}

}

void PreOrderTraverse(BiTree T,void(*Visit)(int))

{ // 初始條件：二叉樹T存在，Visit是對結點操作的應用函數。修改算法6.1

// 操作結果：先序遞歸遍歷T，對每個結點調用函數Visit一次且僅一次

if(T) // T不空

{ Visit(T-data); // 先訪問根結點

PreOrderTraverse(T-lchild,Visit); // 再先序遍歷左子樹

PreOrderTraverse(T-rchild,Visit); // 最後先序遍歷右子樹

}

}

void InOrderTraverse(BiTree T,void(*Visit)(int))

{ // 初始條件：二叉樹T存在，Visit是對結點操作的應用函數

// 操作結果：中序遞歸遍歷T，對每個結點調用函數Visit一次且僅一次

if(T)

{ InOrderTraverse(T-lchild,Visit); // 先中序遍歷左子樹

Visit(T-data); // 再訪問根結點

InOrderTraverse(T-rchild,Visit); // 最後中序遍歷右子樹

}

}

void PostOrderTraverse(BiTree T,void(*Visit)(int))

{ // 初始條件：二叉樹T存在，Visit是對結點操作的應用函數

// 操作結果：後序遞歸遍歷T，對每個結點調用函數Visit一次且僅一次

if(T) // T不空

{ PostOrderTraverse(T-lchild,Visit); // 先後序遍歷左子樹

PostOrderTraverse(T-rchild,Visit); // 再後序遍歷右子樹

Visit(T-data); // 最後訪問根結點

}

}

void main()

{

BiTree T;

InitBiTree(T); // 初始化二叉樹T

printf(“按先序次序輸入二叉樹中結點的值,輸入0表示節點為空，輸入範例：1 2 0 0 3 0 0\n”);

CreateBiTree(T); // 建立二叉樹T

printf(“先序遞歸遍歷二叉樹：\n”);

PreOrderTraverse(T,visit); // 先序遞歸遍歷二叉樹T

printf(“\n中序遞歸遍歷二叉樹：\n”);

InOrderTraverse(T,visit); // 中序遞歸遍歷二叉樹T

printf(“\n後序遞歸遍歷二叉樹：\n”);

PostOrderTraverse(T,visit); // 後序遞歸遍歷二叉樹T

}

這樣可以么？

層序遍歷二叉樹

#includestdio.h

#includestdlib.h

#define m 100

typedef char etype;

typedef struct bitnode

{

etype data;

struct bitnode *lch,*rch;

}bitnode,*bitree;

bitree que[m];

int front=0,rear=0;

bitnode *creat_bt1();

bitnode *creat_bt2();

void preorder(bitnode *p);

void inorder(bitnode *p);

void postorder(bitnode *p);

void enqueue(bitree);

bitree delqueue();

void levorder(bitree);

int treedepth(bitree);

void prtbtree(bitree,int);

void exchange(bitree);

int leafcount(bitree);

void paintleaf(bitree);

bitnode *t;

int count=0;

void main()

{

char ch;int k;

do{

printf(“\n\n\n”);

printf(“\n==========主菜單==============”);

printf(“\n 1.建立二叉樹方法 1”);

printf(“\n 2.建立二叉樹方法 2”);

printf(“\n 3.先序遞歸遍歷二叉樹”);

printf(“\n 4.中序遞歸遍歷二叉樹”);

printf(“\n 5.後序遞歸遍歷二叉樹”);

printf(“\n 6.層次遍歷二叉樹”);

printf(“\n 7.計算二叉樹的高度”);

printf(“\n 8.計算二叉樹中葉結點個數”);

printf(“\n 9.交換二叉樹的左右子樹”);

printf(“\n 10.打印二叉樹”);

printf(“\n 0.結束程序運行”);

printf(“\n===============================”);

printf(“\n 請輸入您的選擇(0,1,2,3,4,5,6,7,8,9,10)”);

scanf(“%d”,k);

switch(k)

{case 1:t=creat_bt1();break;

case 2:printf(“\n請輸入二叉樹各節點的值：”);fflush(stdin);

t=creat_bt2();break;

case 3:if(t)

{printf(“先序遍歷二叉樹：”);

preorder(t);

printf(“\n”);

}

else printf(“二叉樹為空!\n”);

break;

case 4:if(t)

{printf(“中序遍歷二叉樹：”);

inorder(t);

printf(“\n”);

}

else printf(“二叉樹為空!\n”);

break;

case 5:if(t)

{printf(“後序遍歷二叉樹：”);

postorder(t);

printf(“\n”);

}

else printf(“二叉樹為空!\n”);

break;

case 6:if(t)

{printf(“層次遍歷二叉樹：”);

levorder(t);

printf(“\n”);

}

else printf(“二叉樹為空!\n”);

break;

case 7:if(t)

{printf(“二叉樹的高度為：%d”,treedepth(t));

printf(“\n”);

}

else printf(“二叉樹為空!\n”);

break;

case 8:if(t)

{printf(“二叉樹的葉子結點數為：%d\n”,leafcount(t));

printf(“二叉樹的葉結點數為：”);paintleaf(t);

printf(“\n”);

}

else printf(“二叉樹為空!\n”);

break;

case 9:if(t)

{printf(“二叉樹的左右子樹：\n”);

exchange(t);

prtbtree(t,0);

printf(“\n”);

}

else printf(“二叉樹為空!\n”);

break;

case 10:if(t)

{printf(“逆時針旋轉90度輸出的二叉樹：\n”);

prtbtree(t,0);

printf(“\n”);

}

else printf(“二叉樹為空!\n”);

break;

case 0:exit(0);

}

}while(k=1k=10);

printf(“\n再見! 按回車鍵，返回…\n”);

ch=getchar();

}

bitnode *creat_bt1()

{

bitnode *t,*p,*v[20];int i,j;etype e;

printf(“\n請輸入二叉樹各結點的編號和對應的值(如：1，a):”);

scanf(“%d,%c”,i,e);

while(i!=0e!=’#’)

{

p=(bitnode *)malloc(sizeof(bitnode));

p-data=e;p-lch=NULL;p-rch=NULL;

v[i]=p;

if(i==1)t=p;

else

{j=i/2;

if(i%2==0) v[j]-lch=p;

else

v[j]-rch=p;

}

printf(“\n 請繼續輸入二叉樹各結點的編號和對應的值：”);

scanf(“%d,%c”,i,e);

}

return(t);

}

bitnode *creat_bt2()

{

bitnode *t;etype e;

scanf(“%c”,e);

if(e==’#’)

t=NULL;

else

{

t=(bitnode *)malloc(sizeof(bitnode));

t-data=e;

t-lch=creat_bt2();

t-rch=creat_bt2();

}

return(t);

}

void preorder(bitnode *p){

if(p)

{

printf(“%3c”,p-data);

preorder(p-lch);

preorder(p-rch);

}

}

void inorder(bitnode *p)

{

if(p){

inorder(p-lch);

printf(“%3c”,p-data);

inorder(p-rch);

}

}

void postorder(bitnode *p)

{

if(p)

{

postorder(p-lch);

postorder(p-rch);

printf(“%3c”,p-data);

}

}

void enqueue(bitree T)

{

if(front!=(rear+1)%m)

{rear=(rear+1)%m;

que[rear]=T;}

}

bitree delqueue()

{

if(front==rear)return NULL;

front=(front+1)%m;

return(que[front]);

}

void levorder(bitree T)

{

bitree p;

if(T)

{

enqueue(T);

while(front!=rear)

{

p=delqueue();

printf(“%3c”,p-data);

if(p-lch!=NULL)enqueue(p-lch);

if(p-rch!=NULL)enqueue(p-rch);

}

}

}

int treedepth(bitree bt)

{

int hl,hr,max;

if(bt!=NULL)

{

hl=treedepth(bt-lch);

hr=treedepth(bt-rch);

max=(hlhr)? hl:hr;

return(max+1);

}

else

return(0);

}

void prtbtree(bitree bt,int level)

{

int j;

if(bt){

prtbtree(bt-rch,level+1);

for(j=0;j=6*level+1;j++)printf(” “);

printf(“%c\n”,bt-data);

prtbtree(bt-lch,level+1);

}

}

void exchange(bitree bt)

{

bitree p;

if(bt)

{p=bt-lch;bt-lch=bt-rch;bt-rch=p;

exchange(bt-lch);exchange(bt-rch);

}

}

int leafcount(bitree bt)

{

if(bt!=NULL)

{

leafcount(bt-lch);

leafcount(bt-rch);

if((bt-lch==NULL)(bt-rch==NULL))

count++;

}

return(count);

}

void paintleaf(bitree bt)

{

if(bt!=NULL)

{

if(bt-lch==NULLbt-rch==NULL)

printf(“%3c”,bt-data);

paintleaf(bt-lch);

paintleaf(bt-rch);

}

}

求二叉樹的層次遍歷代碼，求高手！！！

#include “stdio.h”typedef int Datatype#define MAXNODE 100

//二叉鏈表的存儲typedef struct BiTNode { Datatype data; struct BiTNode *lchild,*rchild;//左右孩子指針}BiTreeNode,*BiTree;

//三叉鏈表的存儲typedef struct BiTNode { Datatype data; struct BiTNode *lchild,*rchild,*parent;}BiTreeNode,*BiTree;

//算法3.1：二叉樹的先序遍歷遞歸算法void PreOrder(BiTree bt){ if(bt!=NULL){ visit(bt-data);//訪問根結點 PreOrder(bt-lchild); PreOrder(bt-rchild); }}

//算法3.2：二叉樹的中序遍歷遞歸算法void InOrder(BiTree bt){ if(bt!=NULL){ InOrder(bt-lchild); visit(bt-data); InOrder(bt-rchild); }}

//算法3.3：二叉樹的後序遍歷遞歸算法void InOrder(BiTree bt){ if(bt!=NULL){ InOrder(bt-lchild); InOrder(bt-rchild); visit(bt-data); }}

//算法3.4：二叉樹的層次遍歷算法void LevelOrder(BiTree bt){ BiTreeNode Queue[MAXNODE]; //定義隊列 int front,rear; if(bt==NULL) return //空二叉樹，遍歷結束 front=-1; rear=0; Queue[rear]=bt; //根結點入隊 while(rear!=front){ //隊列不空，繼續遍歷；否則，遍歷結束 front++; //出隊 visit(Queue[front]-data); //訪問剛出隊的元素 if(Queue[front]-lchild!=NULL){ //如果有左孩子，左孩子入隊 rear++; Queue[rear]=Queue[front]-lchild; } if(Queue[front]-rchild!=NULL){ //如果有右孩子，右孩子入隊 rear++; Queue[rear]=Queue[front]-rchild; } }}

//算法3.5：中序遍歷的非遞歸算法void NRInOrder(BiTree bt){ BiTree S[MAXNODE],p=bt;//定義棧 int top=-1; if(bt==NULL) return;//空二叉樹，遍歷結束 while(!(p==NULLtop==0)){ while(p!=NULL){ if(topMAXNODE-1) S[top++]=p;//當前指針p入棧 else{printf(“棧溢出\n”);return;} p=p-lchild;//指針指向p的左孩子結點 } if(top==-1) return //棧空，結束 else{ p=S[–top];//彈出棧頂元素 visit(p-data);//訪問結點的數據域 p=p-rchild;//指向p的右孩子結點 } }}

//算法3.6：根據先序與中序遍歷結果建立二叉樹void PreInOrd(char preord[],char inord[],int i,int j,int k,int h,BiTree *t)//先序序列從i到j,中序序列從k到h，建立一個二叉樹放到t中{ int m; (*t)=new BTNode; (*t)-data=preord[i];//二叉樹的根 m=k; while (i[m]!=preord[i])m++;//在中序序列中定位樹根 /********遞歸調用建立左子樹******/ if(m==k)(*t)-left=NULL; else PreInOrd(preord,inord,i+1,i+m-k,k,m-1,(*t)-left); /********遞歸調用建立左子樹******/ if(m==k)(*t)-right=NULL; else PreInOrd(preord,inord,i+1,i+m-k,k,m-1,(*))-right);}BTree * createBT(char preord[],char inord[],int n,BTree root)//n為二叉樹接點的個數，建立的二叉樹放在root中{ if(n=0) root=NULL; else PreInOrd(preord,inord,1,n,1,n,root) return root;}

//算法3.7：統計二叉樹的葉子結點算法int BitreeLeaf(BTree bt) if(bt==NULL) return 0; if(bt-left==NULL bt-right==NULL) return 1; return (BitreeLeaf(bt-left)+BirLeaf(bt-right));}

//算法3.8：求二叉樹深度算法int BitreeDepth (BiTree bt){ if(bt==NULL) return 0; if(bt-lchild==NULL bt-rchild==NULL) return1; depthL=BitreeDepth(bt-lchild); depthR=BitreeDepth(bt-rchild); return 1+max(depthL,depthR);}

//算法3.12：二叉樹的查找算法BiTree SearchBST(BiTree bt,KeyType key){ if(bt==NULL || key==bt-data.key) return bt; if(keybt-data.key) return SearchBST(bt-lchild,key); else return SearchBST(bt-rchild,key);}

//算法3.13：在二叉樹中插入結點int InseartBST(BiTreeNode **bt,Datatype e){ BiTreeNode *qq=new BiTreeNode(),*pp=new BiTreeNode(); BiTreeNode **qq=qq,*s,**p=pp; *q=OxO; *p=OxO; if(SearchBST(*bt,e.key,p,q)==0)//待查結點是否在二叉排序樹中 { s=new BiTreeNode(); s-data=e;s-lchild=s-rchild=OxO;//待查結點 if(!(*q)) *bt=s;//二叉樹的根 else if(e.key(*q)-data.key) (*q)-lchild=s;//作為左兒子插入 else(*q)-rchild=s;//作為右兒子插入 return 1; } else return 0;}

//算法3.14：在二叉排序樹中刪除結點int DeleteNode(BitreeNode **t,int key){ BiTreeNode *pp=new BiTreeNode(),*ff=new BiTreeNode; BiTreeNode **p=pp,*s,*q,**f=ff; *p=OxO;*f=OxO; int flag=0; if(SearchBST(*t,key,f,p)!=0){ flag=1;//查找成功，置刪除標記，待刪除結點為p if(!((*p)-rchild)){//結點無右兒子，結點只有一個分支或為葉子結點 if((*f)-lchild==*p) (*f)-lchild=(*P)-lchild; else (*f)-rchild=(*p)-lchild; } else{//結點有右兒子 if(!((*p)-lchild)){//結點無左兒子，一個分支 if((*f)-lchild==*p) (*f)-lchild=(*P)-rchild; else (*f)-rchild=(*p)-rchild; } else {//結點有左二子，兩個分支 q=*p; s=(*p)-lchild; while(s-rchild){q=s;s=s-rchild;}//在結點p的左分支上沿右指針域往下找，直到右指針域為空時為止 (*p)-data=s-data; if(q!=*p){(q)-rchild=s-lchild;} else(q)-lcild=s-lchild; } } } return flag;}

二叉樹的層次遍歷算法

二叉樹的層次遍歷算法有如下三種方法：

給定一棵二叉樹，要求進行分層遍歷，每層的節點值單獨打印一行，下圖給出事例結構：

對此二叉樹遍歷的結果應該是：

1，

2 ， 3

4， 5， 6

7， 8

第一種方法，就是利用遞歸的方法，按層進行打印，我們把根節點當做第0層，之後層次依次增加，如果我們想打印第二層怎麼辦呢，利用遞歸的代碼如下：

[cpp] view plaincopy

int print_at_level(Tree T, int level) {

  if (!T || level 0)

      return 0;

  if (0 == level) {

      cout T-data ” “;

      return 1;

  }

  return print_at_level(T-lchild, level – 1) + print_at_level(T-rchild, level – 1);

如果我們成功的打印了給定的層次，那麼就返回非0的正值，如果失敗返回0。有了這個思路，我們就可以應用一個循環，來打印這顆樹的所有層的節點，但是有個問題就是我們不知道這棵二叉樹的深度，怎麼來控制循環使其結束呢，仔細看一下print_at_level，如果指定的Tree是空的，那麼就直接返回0，當返回0的時候，我們就結束循環，說明沒有節點可以打印了。

[cpp] view plaincopy

void print_by_level_1(Tree T) {

  int i = 0;

  for (i = 0; ; i++) {

      if (!print_at_level(T, i))

          break;

  }

  cout endl;

}

以上的方法可以很清楚的看出，存在重複訪問的情況，就是第0層訪問的次數最多，第1層次之。所以這個遞歸的方法不是很有效的方法。

第二種方法：我們可以設置兩個隊列，想象一下隊列的特點，就是先進先出，首先把第0層保存在一個隊列中，然後按節點訪問，並把已經訪問節點的左右孩子節點放在第二個隊列中，當第一個隊列中的所有節點都訪問完成之後，交換兩個節點。這樣重複下去，知道所有層的節點都被訪問，這樣做的代價就是空間複雜度有點高。

[cpp] view plaincopy

void print_by_level_2(Tree T) {

  dequetree_node_t* q_first, q_second;

  q_first.push_back(T);

  while(!q_first.empty()) {

      while (!q_first.empty()) {

          tree_node_t *temp = q_first.front();

          q_first.pop_front();

          cout temp-data ” “;

          if (temp-lchild)

              q_second.push_back(temp-lchild);

          if (temp-rchild)

              q_second.push_back(temp-rchild);

      }

      cout endl;

      q_first.swap(q_second);

  }

}

第三種方法就是設置雙指針，一個指向訪問當層開始的節點，一個指向訪問當層結束節點的下一個位置：

這是第一層訪問的情況，當訪問第0層之後的結構如下，把第0層的所有子節點加入之後：

訪問完第1層之後：

之後大家就可以自己畫圖了，下面給出程序代碼：

[cpp] view plaincopy

void print_by_level_3(Tree T) {

  vectortree_node_t* vec;

  vec.push_back(T);

  int cur = 0;

  int end = 1;

  while (cur vec.size()) {

      end = vec.size();

      while (cur end) {

          cout vec[cur]-data ” “;

          if (vec[cur]-lchild)

              vec.push_back(vec[cur]-lchild);

          if (vec[cur]-rchild)

              vec.push_back(vec[cur]-rchild);

          cur++;

      }

      cout endl;

  }

}

最後給出完成代碼的測試用例：124##57##8##3#6##

[cpp] view plaincopy

#includeiostream

#includevector

#includedeque

using namespace std;

typedef struct tree_node_s {

  char data;

  struct tree_node_s *lchild;

  struct tree_node_s *rchild;

}tree_node_t, *Tree;

void create_tree(Tree *T) {

  char c = getchar();

  if (c == ‘#’) {

      *T = NULL;

  } else {

      *T = (tree_node_t*)malloc(sizeof(tree_node_t));

      (*T)-data = c;

      create_tree((*T)-lchild);

      create_tree((*T)-rchild);

  }

}

void print_tree(Tree T) {

  if (T) {

      cout T-data ” “;

      print_tree(T-lchild);

      print_tree(T-rchild);

  }

}

int print_at_level(Tree T, int level) {

  if (!T || level 0)

      return 0;

  if (0 == level) {

      cout T-data ” “;

      return 1;

  }

  return print_at_level(T-lchild, level – 1) + print_at_level(T-rchild, level – 1);

}

void print_by_level_1(Tree T) {

  int i = 0;

  for (i = 0; ; i++) {

      if (!print_at_level(T, i))

          break;

  }

  cout endl;

}

void print_by_level_2(Tree T) {

  dequetree_node_t* q_first, q_second;

  q_first.push_back(T);

  while(!q_first.empty()) {

      while (!q_first.empty()) {

          tree_node_t *temp = q_first.front();

          q_first.pop_front();

          cout temp-data ” “;

          if (temp-lchild)

              q_second.push_back(temp-lchild);

          if (temp-rchild)

              q_second.push_back(temp-rchild);

      }

      cout endl;

      q_first.swap(q_second);

  }

}

void print_by_level_3(Tree T) {

  vectortree_node_t* vec;

  vec.push_back(T);

  int cur = 0;

  int end = 1;

  while (cur vec.size()) {

      end = vec.size();

      while (cur end) {

          cout vec[cur]-data ” “;

          if (vec[cur]-lchild)

              vec.push_back(vec[cur]-lchild);

          if (vec[cur]-rchild)

              vec.push_back(vec[cur]-rchild);

          cur++;

      }

      cout endl;

  }

}

int main(int argc, char *argv[]) {

  Tree T = NULL;

  create_tree(T);

  print_tree(T);

  cout endl;

  print_by_level_3(T);

  cin.get();

  cin.get();

  return 0;

}