#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
using namespace std;
//头文件
#define VALUE int
//定义数据类型
//-----------------------------------------------
typedef struct BITREE{
 VALUE value;
 int unicode;
 struct BITREE *leftson;
 struct BITREE *rightson;
}BITREE;
//二叉树的定义
//定义根
BITREE root;
//定义树的高度
long high=0;
//定义叶子数
long leaves=0;
//树的队列模型
VALUE treeline[100000];
//二叉树操作
//----------------------------------------------
//创建左子树,返回左子树地址
BITREE* createleftson(BITREE *father,VALUE value){
 BITREE *leftson;
 leftson=(BITREE *)malloc(sizeof(BITREE));
 leftson->value=value;
 father->leftson=leftson;
 leftson->leftson=NULL;
 leftson->rightson=NULL;
 leftson->unicode=father->unicode*2;
 treeline[leftson->unicode]=leftson->value;
 return leftson;
}
//创建右子树，返回右子树地址
BITREE* createrightson(BITREE *father,VALUE value){
 BITREE *rightson;
 rightson=(BITREE *)malloc(sizeof(BITREE));
 rightson->value=value;
 father->rightson=rightson;
 rightson->leftson=NULL;
 rightson->rightson=NULL;
 rightson->unicode=father->unicode*2+1;
 treeline[rightson->unicode]=rightson->value;
 return rightson;
}
//遍历二叉树（为了插节点）
int traversal_node(BITREE *root){
 if(root==NULL)
  return 1;
 if(root->unicode%2==0){
  root->unicode*=2;
  treeline[root->unicode]=root->value;
 }
 else
 {
  root->unicode*=2;
  root->unicode--;
  treeline[root->unicode]=root->value;
 }
 traversal_node(root->leftson);
 traversal_node(root->rightson);
}
//插入左节点，返回左结点地址
BITREE* createleftnode(BITREE *father,VALUE value){
 BITREE *newnode;
 newnode=(BITREE *)malloc(sizeof(BITREE));
 newnode->leftson=father->leftson;
 newnode->rightson=NULL;
 father->leftson=newnode;
 newnode->value=value;
 newnode->unicode=father->unicode*2;
 treeline[newnode->unicode]=newnode->value;
 traversal_node(newnode->leftson);
 return newnode;
}
//插入右结点，返回右结点地址
BITREE* createrightnode(BITREE *father,VALUE value){
 BITREE *newnode;
 newnode=(BITREE *)malloc(sizeof(BITREE));
 newnode->rightson=father->rightson;
 newnode->leftson=NULL;
 father->rightson=newnode;
 newnode->value=value;
 newnode->unicode=father->unicode*2+1;
 treeline[newnode->unicode]=newnode->value;
 traversal_node(newnode->rightson);
 return newnode;
}
//遍历二叉树（先序）
int traversal_first(BITREE *root){
 if(root==NULL)
  return 1;
 //to do
 traversal_first(root->leftson);
 traversal_first(root->rightson);
}
//遍历二叉树（中序）
int traversal_middle(BITREE *root){
 if(root==NULL)
  return 1;
 traversal_middle(root->leftson);
 //to do
 traversal_middle(root->rightson);
}
//遍历二叉树（后序）
int traversal_last(BITREE *root){
 if(root==NULL)
  return 1;
 traversal_last(root->leftson);
 traversal_last(root->rightson);
 //to do
}
//树的高度
int highoftree(BITREE *root){
 int l,r;
 if(root){
  l=highoftree(root->leftson);
  r=highoftree(root->rightson);
  if(l>r)
   return l+1;
  else
   return r+1;
 }
 else
  return 0;
}
/*
 if(root->leftson==NULL&&root->rightson==NULL)
  return 1;
 if(root->leftson==NULL)
  return highoftree(root->rightson)+1;
 if(root->rightson==NULL)
  return highoftree(root->leftson)+1;
 else
  return highoftree(root->leftson)>highoftree(root->rightson)?highoftree(root->leftson):highoftree(root->rightson)+1;
*/
//已知unicode探求树的拓扑路径
int* findpath(int unicode){ 
 int *path;
 path=(int *)malloc(sizeof(int)*1000);
 int k,point=0;
 k=unicode;
 while(k!=1){
  if(k%2==0){
   *(path+point)=2;
   k/=2;
   point++;
  }
  else{
   *(path+point)=1;
   k=(k-1)/2;
   point++;
  }
 }
 *(path+point)=0;
 return path;
}
//注：1代表取左上，2代表取右上

二叉树的实现与一些基本操作（C++环境）