5)二叉树[3]求所有结点到根节点的路径

  1 #include "iostream"
  2 using namespace std;
  3 
  4 typedef char type;
  5 struct bnode{
  6     type data;
  7     type parent;
  8     bnode *lchild,*rchild;
  9 };
 10 
 11 class tree{
 12 public:
 13     tree();//初始化
 14     ~tree();
 15     void create_tree(bnode *&T);//建立二叉树
 16     void parent(bnode *&T,bnode *root);//求二叉树所有结点的父节点
 17     bnode *pa(bnode *p,bnode *T);//求结点p的父节点
 18     void path(bnode *p,bnode *root);//结点p到根节点的路径
 19     void all_path(bnode *T,bnode *root);
 20 private:
 21     bool flags;
 22     bnode *temp;
 23 };
 24 
 25 tree::tree()//初始化
 26 {
 27     temp = new bnode;
 28     temp = NULL;
 29     flags = true;
 30 }
 31 
 32 void tree::create_tree(bnode *&T)//建立二叉树
 33 {
 34     type x;
 35     cin>>x;
 36     if(x=='#')T=NULL;
 37     else {
 38         T = new bnode;
 39         T->data = x;
 40         T->parent='#';
 41         create_tree(T->lchild);//建立左子树
 42         create_tree(T->rchild);//建立右子树
 43     }
 44 }
 45 
 46 bnode *tree::pa(bnode *p,bnode *T)
 47 {
 48     if(flags&&T)
 49     {
 50         if(T->lchild==p||T->rchild==p)//父节点找到，终止递归
 51         {
 52             flags = false;
 53             temp = T;
 54         }else{
 55             pa(p,T->lchild);//在左子树中寻找
 56             pa(p,T->rchild);//在右子树中寻找
 57             
 58         }
 59     }
 60     return temp;
 61 }
 62 
 63 void tree::parent(bnode *&T,bnode *root)
 64 {
 65     if(T)
 66     {
 67         if(T->parent=='#')
 68         {
 69             if(pa(T,root))//如果父节点存在
 70             {
 71                 T->parent = pa(T,root)->data;
 72                 temp = NULL;
 73             }
 74         }
 75         //cout<<"Pannel point:"<<T->data<<",parent:"<<T->parent<<endl;
 76         flags = true;
 77         parent(T->lchild,root);
 78         parent(T->rchild,root);
 79 
 80     }
 81     
 82 }
 83 
 84 void tree::path(bnode *p,bnode *root)
 85 {
 86     cout<<"["<<p->data<<"->"<<root->data<<"]:";
 87     cout<<p->data<<" ";
 88     while(p->parent!='#')
 89     {
 90         p =pa(p,root);
 91         temp = NULL;
 92         flags = true;
 93         cout<<p->data<<" ";
 94     }
 95     cout<<endl;
 96 }
 97 
 98 void tree::all_path(bnode *T,bnode* root)
 99 {
100     if(T)
101     {
102         if(T!=root)path(T,root);
103         all_path(T->lchild,root);
104         all_path(T->rchild,root);
105     }
106 }
107 tree::~tree(){}
108 
109 int main()
110 {
111     tree Tree;
112     bnode *T;
113     cout<<"Create Tree['#'表示空节点]:"<<endl;
114     cout<<"Tree:";
115     Tree.create_tree(T);
116     cout<<"Tree finished!"<<endl;
117     Tree.parent(T,T);
118     cout<<"Path:"<<endl;
119     Tree.all_path(T,T); 
120     return 0;
121 }