第十章：基本数据结构（2）-白红宇

第十章：基本数据结构（2）

阅读量：7127 次

发布时间：2019-06-28

本文共 3095 字，大约阅读时间需要 10 分钟。

请写出一个O(n)时间的非递归过程，将给定的n节点二叉树中每个节点的关键字输出来。可以利用栈作为辅助数组数据结构。

中序输出

PUSH(root)

while !empty_stack(S)

　　if root->left

　　　　PUSH(root->left)

　　　　root<-root->left

　　else

　　　　root<-POP(S)

　　　　打印root数据

　　　　while !root->right&&!empty_stack(S)

　　　　　　root<-POP(S)

　　　　　　打印root数据

　　　　if root->right　

　　　　　　PUSH(root->right)

　　　　　　root<-root->right

前序输出

PUSH(root)

while !empty_stack(S)

　　root<-POP(S)

　　打印root数据

　　if root->right

　　　　PUSH(root->right)

　　if root->left

　　　　PUSH(root->left)

后序输出

PUSH(root)

while !empty_stack(S)

　　if root->right||root->left

　　　　if root->left

　　　　　　if root->right

　　　　　　　　PUSH(root->right)

　　　　　　PUSH(root->left)

　　　　　　root<-root->left

　　　　else

　　　　　　PUSH(root->right)

　　　　　　root<-root->right

　　else　　

　　　　root<-POP(S)

　　　　打印root数据

　　　　while !empty_stack(S)

　　　　　　p=POP(S)

　　　　　　if p->left==root||p->right==root

　　　　　　　　打印root数据

　　　　　　　　root=p

　　　　　　else

　　　　　　　　root=p;

　　　　　　　　PUSH(root)

　　　　　　　　break

1 typedef int Data; 2  3 struct TreeNode{ 4     Data data; 5     TreeNode *left; 6     TreeNode *right; 7 }; 8  9 /*10 建立一棵num个元素的有序二叉树11 */12 TreeNode *create_tree(int num){13     TreeNode *root,*p,*child,*parent;14     int i=0;15     p=(TreeNode *)malloc(sizeof(TreeNode));16     p->left=p->right=NULL;17     cin>>p->data;18     child=root=p;19     while (++i
     
      left=p->right=NULL;22         cin>>p->data;23         while (child){24             parent=child;25             if ((p->data)>(child->data)){26                 child=child->right;27             }else{28                 child=child->left;29             }30         }31         if (p->data>parent->data){32             parent->right=p;33         }else{34             parent->left=p;35         }36         child=root;37     }38     return root;39 }

1 //非递归中序输出 2 void midOrder(TreeNode *t){ 3     Stack s={
   0}; 4     TreeNode *p=NULL; 5     push(&s,t); 6     while(!empty_stack(&s)){ 7         if (t->left){ 8             push(&s,t->left); 9             t=t->left;10         }else{11             t=pop(&s);12             cout<
     
      data<
      
       right)&&!empty_stack(&s)){14                 t=pop(&s);15                 cout<
       
        data<
        
         right){18                 push(&s,t->right);19                 t=t->right;20             }21         }22     }23 }24 25 //非递归前序输出26 void preOrder(TreeNode *t){27     Stack s={
   0};28     TreeNode *p=NULL;29     push(&s,t);30     while (!empty_stack(&s)){31         t=pop(&s);32         cout<
         
          data<
          
           right){34 push(&s,t->right);35 }36 if (t->left){37 push(&s,t->left);38 }39 }40 }41 42 //非递归后序输出43 void postOrder(TreeNode *t){44 Stack s={ 0};45 TreeNode *p=NULL;46 push(&s,t);47 while (!empty_stack(&s)){48 if (t->left||t->right){ //如果t有孩子，则将孩子入栈49 if (t->left){50 if (t->right){51 push(&s,t->right);52 }53 push(&s,t->left);54 t=t->left;55 }else{56 push(&s,t->right);57 t=t->right;58 }59 }else{60 t=pop(&s); //从栈中取出叶子节点t61 cout<
           
            data<
            
             left==t||p->right==t){ //判断该节点是不是t的父节点,如果是则输出数据 65 cout<
             
              data<