数据结构-二叉树

手工创建二叉树

// copyright by hwdong
#include <stdio.h>
#include <malloc.h>

typedef char EType;

typedef struct binode{
   EType data;
   struct binode *lchild,*rchild;
}BiNode;

BiNode  *newNode(){
    BiNode  *p = (BiNode  *)malloc(sizeof(BiNode) );
    if(!p) return 0;
    p->lchild = p->rchild = 0;
    return p;
}

void visit(EType e){
    printf("%c  ",e);
}

void IOT(BiNode *T ){
  if(!T) return ;
  IOT(T->lchild);
    visit(T->data);
    IOT(T->rchild);
}
void PreOT(BiNode *T ){
  if(!T) return ;
  visit(T->data);
  PreOT(T->lchild);
    
    PreOT(T->rchild);
}
void PostOT(BiNode *T ){
  if(!T) return ;
  PostOT(T->lchild);   
    PostOT(T->rchild);
    visit(T->data);
}

int main( ){
    BiNode *p;   
    BiNode *T = newNode();    T->data = 'A';
    T->lchild= newNode();   T->lchild->data = 'B';
    T->rchild= newNode();   T->rchild->data = 'C';
    p = T->lchild;
    p->lchild= newNode();   p->lchild->data = 'D';
    p->rchild= newNode();   p->rchild->data = 'E';
    IOT(T);  /*输出中序遍历序列*/
    printf("\n");
    PreOT(T);  /*输出先序遍历序列*/
    printf("\n");
    PostOT(T);  /*输出先序遍历序列*/
    printf("\n");
} 

从带空子树标记的先序序列创建二叉树

C语言版本

#include <stdio.h>

#include <malloc.h>

typedef char EType;

typedef struct binode {
  EType data;
  struct binode *lchild, *rchild;
}BiTNode;


BiTNode* PreOrderCreatBiTree() {
  char ch; BiTNode* T;
  scanf("%c", &ch);
  if (ch == '#') return 0;
  else {
    if (!(T = (BiTNode*)malloc(sizeof(BiTNode)))) {
      printf("内存不够!\n");
      return 0;
    }
    T->data = ch;
    T->lchild = PreOrderCreatBiTree();
    T->rchild = PreOrderCreatBiTree();
    return T;
  }
}

void IOT(BiTNode* T) {
  if (!T) return;
  printf("%c ", T->data);
  IOT(T->lchild);
  IOT(T->rchild);
}
int main() {
  BiTNode* root = PreOrderCreatBiTree();
  IOT(root);
}

c++引用版本

// copyright by hwdong
#include <cstdio>

typedef char Type;

typedef struct _BiNode{
    Type data;
    struct _BiNode *lchild, *rchild;
}BiTNode;

typedef BiTNode* BiTree;

void visit(BiTNode* p){
    printf("%c",p->data);
}

void PreTraverse(BiTNode* T){
    if(!T) return ;
    visit(T);
    PreTraverse(T->lchild);
    PreTraverse(T->rchild);
}


void PreOrderCreatBiTree(BiTNode* &T){
    Type e;
    scanf("%c",&e);
    if(e== '#'){ T = 0; return;} //递归出口


    if(!(T= new BiTNode) ){ //处理根
        throw "内存不够!";return;
    }
    T->data = e;

    PreOrderCreatBiTree(T->lchild);//左子树
    PreOrderCreatBiTree(T->rchild);//右子树
}

int Depth (BiTNode* T ){
  if (!T) return 0 ;
  int l = Depth( T->lchild );
  int r = Depth( T->rchild );  
  return l>r?l+1:r+1;
}

int main(){
    BiTNode* T = 0;
    PreOrderCreatBiTree(T);
    PreTraverse(T);
    int d = Depth(T);
    printf("\ndepth of the tree is :%d\n",d);

    return 0;
}

赏

支付宝打赏

微信打赏

您的打赏是对我最大的鼓励！

Binary Tree

CATALOG

FEATURED TAGS

FRIENDS