白书8.3 二叉树的表达

77 阅读 0 评论 51 点赞

我是靠谱客的博主柔弱月饼，最近开发中收集的这篇文章主要介绍白书8.3 二叉树的表达，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

代码如下：

# include <iostream>
using namespace std;

# define MAX 100001
# define NIL -1

struct Node{
int left,right,parent;
};

Node a[MAX];

int sibling(int x){
   int i=a[x].parent;
   if(x==a[i].left)   return a[i].right;
   else   return a[i].left;
}

int degree(int n){
   int i=0;
   if(a[n].left!=NIL)   i+=1;
   if(a[n].right!=NIL)   i+=1;
   return i;
}

int d[MAX];
int h[MAX];

int depth(int n,int m){/*一个编号，一个计数器 */
   if(n==NIL)   return;
   d[n]=m;
   depth(a[n].left,m+1);
   depth(a[n].right,m+1);
}//写void是因为感觉要构造一个数组，把整棵树各个节点的深度都存放进去，要调用也简单

int setheight(int u){
   int h1=0,h2=0;
   if(a[u].left!=NIL)   h1=setheight(a[u].left)+1;
   if(a[u].right!=NIL)   h2=setheight(a[u].right)+1;
   return h[u]={h1>h2?h1:h2};
}

void print(int n){
   cout<<"node "<<n<<":";
   cout<<"parent = "<<a[n].parent<<",";
   cout<<"sibling = "<<sibling(n)<<",";
   cout<<"degree = "<<degree(n)<<",";
   //cout<<"depth = "<<depth(n)<<",";
   cout<<"depth = "<<d[n]<<",";
   cout<<"height = "<<h[n]<<",";
}

int main()
{
   int n;
   cin>>n;
   int i;
   int v,l,r;//这里还要有一个v，可以让用户输入编号，因为用户的输入顺序不一定是按照i的自增
   for(i=0; i<n; i++)   a[i].parent=NIL;//回头补充：初始化双亲节点
   for(i=0; i<n; i++){
       cin>>v>>l>>r;
       a[v].left=l;
       a[v].right=r;//这里输入完了，但我还想要确定双亲节点，因为输出结果要有双亲
       if(a[v].left!=NIL)   a[l].parent=v;
       if(a[v].right!=NIL)   a[r].parent=v;
   }
   //好那现在这棵树就建好了，接下来看看输出要求，要输出兄弟节点的编号、度、深度、高度，以及是否为叶子、节点或者根
   int root;
   for(i=0; i<n; i++){
       if(a[i].parent==NIL)   root=i;//找出根节点
   }//对了，还得初始化一下双亲节点，令双亲节点全部都为空先

   depth(root,0);//感觉要先找到这个根节点在哪里，才能接着往下解决深度、高度的问题，首先就得求出这个根节点用户是写的是什么编号
   setheight(root);
   for(i=0; i<n; i++)   print(i);
}