二叉树的表达

二叉树 求深度和高度

#include<iostream> using namespace std; #define NIL -1 #define MAX 1000 struct tree { int p,l,r; }; tree T[MAX]; int n,D[MAX],H[MAX]; void setd(int u,int t){ D[u]=t; if(T[u].l!=NIL) setd(T[u].l,t+1); if(T[u].r!=NIL) setd(T[u].r,t+1); } int seth(int u){ int h1=0; int h2=0; if(T[u].l!=NIL) h1=seth(T[u].l)+1; if(T[u].r!=NIL) h2=seth(T[u].r)+1; return h1>h2?h1:h2; } int getsibling(int u){ if(T[u].p==NIL) return NIL; if(T[T[u].p].l!=u&&T[T[u].p].l!=NIL) return T[T[u].p].l; if(T[T[u].p].r!=u&&T[T[u].p].r!=NIL) return T[T[u].p].r; } void print (int u){ int i,c; int num=0; cout << "node" <<u<<" : "; cout << "parent" << T[u].p<<","; cout << "sibling" << getsibling(u)<<","; if(T[u].l!=NIL) num++; if(T[u].r!=NIL) num++; cout <<"degree"<<num<<","; cout<< "depeth"<<D[u] <<","; cout <<"height"<<H[u]<<","; if(T[u].p==NIL){ cout << "root, "; }else if(T[u].l==NIL&&T[u].r==NIL){ cout <<"leaf, "; }else cout << "中间节点, "; cout<<" [ "; cout<<T[u].l<<","<<T[u].r; cout <<" ]"<<endl; } int main(){ int v,l,r,root; cin>>n; for(int i=0;i<n;i++){ T[i].p=NIL; } for(int i=0;i<n;i++){ //cout <<"1"; //cin>>v>>l>>r; T[v].l=l; T[v].r=r; if(l!=NIL){ T[l].p=v; } if(r!=NIL){ T[r].p=v ; } } for(int i=0;i<n;i++){ if(T[i].p==NIL){ root = i; break; } } setd(root , 0); seth(root); for(int i=0 ;i<n;i++) print(i); }

二叉树的前序 中序 后序遍历

#include <iostream> using namespace std; #define NIL -1 #define MAX 1000 struct tree { int p,l,r; }; tree T[MAX]; int n,D[MAX],H[MAX]; void prepare(int u){ if(u==NIL) return; cout<<" "<<u; prepare(T[u].l); prepare(T[u].r); } void mid(int u){ if(u==NIL) return; mid(T[u].l); cout<<" "<<u; mid(T[u].r); } void end(int u){ if(u==NIL) return; end(T[u].l); end(T[u].r); cout<<" "<<u; } int main(){ int v,l,r,root; cin>>n; for(int i=0;i<n;i++){ T[i].p=NIL; } for(int i=0;i<n;i++){ //cout <<"1"; cin>>v>>l>>r; T[v].l=l; T[v].r=r; if(l!=NIL){ T[l].p=v; } if(r!=NIL){ T[r].p=v ; } } for(int i=0;i<n;i++){ if(T[i].p==NIL){ root = i; break; } } cout<<"pre"<<endl; prepare(root); cout<<endl; cout<<"mid"<<endl; mid(root); cout<<endl; cout<<"end"<<endl; end(root); return 0; }

测试数据

9 0 1 4 1 2 3 2 -1 -1 3 -1 -1 4 5 8 5 6 7 6 -1 -1 7 -1 -1 8 -1 -1