#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代表取右上