第五章树和二叉树笔记完结-白红宇

第五章树和二叉树笔记完结

阅读量：5887 次

发布时间：2019-06-19

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

PS：对于递归实现的前序，中序，后序算法，无非是在递归时，根的访问位置不同而已，代码内容几乎相似。非递归算法实现时，当root指针或栈非空时，先循环考虑root是否为否执行相应的操作，对于栈判断是否为空，进行root的转换。前序，后序，中序的非递归算法区别无非是每棵树的根节点的输出时机不同而已，具体实现大同小异。

1.二叉树的前序遍历-------------------非递归实现算法（伪代码）和递归实现

非递归实现伪代码：

1.栈s初始化（空栈）；2.循环直到root为空且栈s为空 　2.1 当root不空时循环　　2.1.1 输出root->data;    　2.1.2 将指针root的值保存到栈中；    　2.1.3 继续遍历root的左子树（root=root->lchild）　2.2 如果栈s不空，则　　2.2.1 将栈顶元素弹出至root（root=s.pop()）；　　2.2.2 准备遍历root的右子树(root=root->rchild)；

代码：

template 
     
      void BiTree::PreOrder(BiNode
      
        *root) {  SeqStack
       
        
          *>  s;     while (root!=NULL | | !s.empty())     {         while (root!= NULL)         {             cout<
         
          data;             s.push=root;             root=root->lchild;           }         if (!s.empty()) {              root=s.pop();             root=root->rchild;           }     }}

递归实现：

template   
     
      void   BiTree::PreOrder(BiNode
      
        *root) {        if (root ==NULL)  return;             else {            cout<
       
        data;                     PreOrder( root->lchild );                PreOrder(  root->rchild);            } }

2.二叉树的建立伪代码：

1.按前序扩展遍历序列输入输入节点的值2.如果输入节点之为“#”,则建立一棵空的子树3.否则，根结点申请空间，将输入值写入数据域中，4.以相同方法的创建根节点的左子树5.以相同的方法创建根节点的右子树递归方法

代码：

template 
     
      BiTree ::BiTree(){       root=creat()；}template 
      
       BiNode
       
         * BiTree ::Creat(){     BiNode
        
          *root; char ch;    cin>>ch;    if (ch=='# ')     root=NULL;     else {        root=new BiNode
         
          ;         root->data=ch;        root->lchild=creat();         root->rchild= creat();     }    return root}

中序遍历---------递归算法

template 
     
      void BiTree::InOrder (BiNode
      
        *root){         if (root==NULL) return;              else {               InOrder(root->lchild);                cout<
       
        data;                InOrder(root->rchild);         }}

中序遍历--------非递归算法（伪代码）：

1.栈s初始化（空栈）；2.循环直到root为空且栈s为空 　2.1 当root不空时循环        2.1.1 将指针root的值保存到栈中；    　2.1.2 继续遍历root的左子树（root=root->lchild）　2.2 如果栈s不空，则　　2.2.1 将栈顶元素弹出至root（root=s.pop()）； 　　  2.2.2 输出root->data;　　2.2.3 准备遍历root的右子树(root=root->rchild)；

代码：

template 
     
      void BiTree::InOrderwithoutD(BiNode
      
        *root){    stack< BiNode
       
         * > aStack;    while (!aStack.empty() || root)    {        while (root)         {            aStack.push(root);            root = root->lchild;        }        if (!aStack.empty())        {            root = aStack.top();            aStack.pop();            cout << root->data;            root = root->rchild;        }    }}

后序遍历-----------递归算法

template 
     
      void BiTree::PostOrder(BiNode
      
        *root){     if (root==NULL) return;     else {         PostOrder(root->lchild);          PostOrder(root->rchild);          cout<
       
        data;              }}

后序遍历的非递归实现：一种你叫巧妙的方法

分析：对于每一个节点压入栈两次，再循环体中，每次弹出一个赋值给p,若p仍和栈的栈顶元素相似，说明它的孩子们还没有访问过，将孩子们加入栈中，否则访问p。也就是第一次弹出将p的孩子们压入栈，第二次弹出访问p。

template
     
                            ///后序遍历void BiTree
      
       ::PostOrder(BiNode
       
         *root){     stack
        
         
          * >astack;     BiNode
          
            *p=root; astack.push(p); astack.push(p); while(!astack.empty()) { p=astack.top(); astack.pop(); if(!astack.empty()&&p==astack.top()) { if(p->rchild) astack.push(p->rchild), astack.push(p->rchild); if(p->lchild) astack.push(p->lchild), astack.push(p->lchild); } else { cout<
           
            data; } }}

通过递归方式建树并测试：

代码：

#include
     
      using namespace std;template 
      
       struct BiNode{    T  data;    BiNode
       
         *lchild, *rchild;};template 
        
         class BiTree{public:    BiTree(){Creat(root);}    void PreOrder() { PreOrder(root); }    void InOrder() { InOrder(root); }    void PostOrder() { PostOrder(root);}    void LevelOrder(){LevelOrder(root);}private:    BiNode
         
           *root;    void Creat(BiNode
          
            *& root); void Release(BiNode
           
             *root); void PreOrder(BiNode
            
              *root); void InOrder(BiNode
             
               *root); void PostOrder(BiNode
              
                *root); void LevelOrder(BiNode
               
                 *root);};template
                
                  ///建立二叉树void BiTree
                 
                  ::Creat(BiNode
                  
                   *&root){ T ch; cin >> ch; if (ch == '#') root = NULL; else { root = new BiNode
                   
                    ; root->data = ch; Creat(root->lchild); Creat(root->rchild); }}template
                    
                      ///前序遍历void BiTree
                     
                      ::PreOrder(BiNode
                      
                        *root){ if (root == NULL) return; else { cout << root->data; PreOrder(root->lchild); PreOrder(root->rchild); }}template
                       
                         ///中序遍历void BiTree
                        
                         ::InOrder(BiNode
                         
                           *root){ if (root == NULL) return; else { InOrder(root->lchild); cout << root->data; InOrder(root->rchild); }}template
                          
                            ///后序遍历void BiTree
                           
                            ::PostOrder(BiNode
                            
                              *root){ if (root == NULL) return; else { PostOrder(root->lchild); PostOrder(root->rchild); cout << root->data ; }}template
                             
                              void BiTree
                              
                               ::Release(BiNode
                               
                                * root){ if (root != NULL) { Release(root->lchild); Release(root->rchild); delete root; }}template
                                
                                  ///层序遍历void BiTree
                                 
                                  ::LevelOrder(BiNode
                                  
                                    *root){ queue
                                   
                                    
                                      *>aqueue; if(root)///当根节点不为空 { aqueue.push(root); while(!aqueue.empty()) { root=aqueue.front(); aqueue.pop(); cout<
                                     
                                      data; if(root->lchild) aqueue.push(root->lchild); if(root->rchild) aqueue.push(root->rchild); } }}int main()///在主函数中测试前、中、后、层序遍历{ char s; while (true) { BiTree
                                      
                                        a; cin>>s; a.PreOrder(); cout << endl; a.InOrder(); cout << endl; a.PostOrder(); cout << endl; a.LevelOrder(); cout<

非递归实现二叉树的前、中、后序访问并测试代码：

#include
     
      using namespace std;template 
      
       struct BiNode{	T  data;	BiNode
       
         *lchild, *rchild;};template 
        
         class BiTree{public:	BiTree(){Creat(root);}	~BiTree(){Release(root);}	void PreOrder() { PreOrder(root); }	void InOrder() { InOrder(root); }	void PostOrder() { PostOrder(root);}	void LevelOrder(){LevelOrder(root);}private:	BiNode
         
           *root;	void Creat(BiNode
          
            *& root); void Release(BiNode
           
             *root); void PreOrder(BiNode
            
              *root); void InOrder(BiNode
             
               *root); void PostOrder(BiNode
              
                *root); void LevelOrder(BiNode
               
                 *root);};template
                
                  ///建立二叉树void BiTree
                 
                  ::Creat(BiNode
                  
                   *&root){ T ch; cin >> ch; if (ch == '#') root = NULL; else { root = new BiNode
                   
                    ; root->data = ch; Creat(root->lchild); Creat(root->rchild); }}/*非递归实现前序遍历时，当根节点和栈都不为空时，先访问当前的根节点，倘若不为空，输出当前节点的值将当前的根节点入栈 ，继续遍历当前节点的左孩子，否则若栈不为空，将节点出栈，访问它的右孩子，直到根节点和栈都为空*/template
                    
                      ///前序遍历void BiTree
                     
                      ::PreOrder(BiNode
                      
                        *root){ stack
                       
                        
                          *>astack; while(root||!astack.empty()) { while(root) { cout<
                         
                          data; astack.push(root); root=root->lchild; } if(!astack.empty()) { root=astack.top(); astack.pop(); root=root->rchild; } }}template
                          
                            ///中序遍历void BiTree
                           
                            ::InOrder(BiNode
                            
                              *root){ stack
                             
                              
                               * >astack; while(root||!astack.empty()) { while(root) { astack.push(root); root=root->lchild; } if(!astack.empty()) { root=astack.top(); cout<
                               
                                data; astack.pop(); root=root->rchild; } }}/*对于每个节点，都压入两遍，在循环体中，每次弹出一个节点赋给p，如果p仍然等于栈的头结点，说明p的孩子们还没有被操作过，应该把它的孩子们加入栈中，否则，访问p。也就是说，第一次弹出，将p的孩子压入栈中，第二次弹出，访问p。*/template
                                
                                  ///后序遍历void BiTree
                                 
                                  ::PostOrder(BiNode
                                  
                                    *root){ stack
                                   
                                    
                                     * >astack; BiNode
                                     
                                       *p=root; astack.push(p); astack.push(p); while(!astack.empty()) { p=astack.top(); astack.pop(); if(!astack.empty()&&p==astack.top()) { if(p->rchild) astack.push(p->rchild), astack.push(p->rchild); if(p->lchild) astack.push(p->lchild), astack.push(p->lchild); } else { cout<
                                      
                                       data; } }}template
                                       
                                        void BiTree
                                        
                                         ::Release(BiNode
                                         
                                          * root){ if (root != NULL) { Release(root->lchild); Release(root->rchild); delete root; }}template
                                          
                                            ///层序遍历void BiTree
                                           
                                            ::LevelOrder(BiNode
                                            
                                              *root){ queue
                                             
                                              
                                                *>aqueue; if(root)///当根节点不为空 { aqueue.push(root); while(!aqueue.empty()) { root=aqueue.front(); aqueue.pop(); cout<
                                               
                                                data; if(root->lchild) aqueue.push(root->lchild); if(root->rchild) aqueue.push(root->rchild); } }}int main(){ char s; while (true) { BiTree
                                                
                                                  a; cin>>s; a.PreOrder(); cout << endl; a.InOrder(); cout << endl; a.PostOrder(); cout << endl; a.LevelOrder(); cout<

关于树的节点数、叶子节点数、高度、交换左右子树算法的实现及检验：

#include 
     
       using namespace std;struct BiNode{    char data;    BiNode *lchild,*rchild;};class BiTree{  public:	     int number;		 int leave; BiTree();		 void PreOrder(){PreOrder(root);}         void countNode(){countNode(root);}         void countLeaf(){countLeaf(root);}         int height(){return height(root);}         void swapTree(){swapTree(root);}private:         BiNode *root;          BiNode *creat();		 void PreOrder(BiNode *root);//前序遍历		 void countNode(BiNode *root);		 void countLeaf(BiNode *root);		 int height(BiNode *root);		 void swapTree(BiNode *root);}; BiTree ::BiTree(){ root=creat(); }BiNode * BiTree ::creat(){	BiNode *root;	char ch; cin>>ch;	if (ch=='#') root=NULL;	else {		  root=new BiNode;		  root->data=ch; root->lchild=creat();		  root->rchild= creat(); } 		  return root;}void BiTree::countNode(BiNode *root) {///统计节点数	if (root ==NULL) return;	else {		    countNode(root->lchild);			number++;			countNode(root->rchild); 			        }}void BiTree::countLeaf(BiNode *root) {///统计叶子节点数	if (root ==NULL) return;	 else {		    if(root->lchild==NULL&&root->rchild==NULL){ leave++; }			  countLeaf(root->lchild); 			  countLeaf(root->rchild);             }} int BiTree::height(BiNode *root) {///统计树的高度	   int lheight=0,rheight=0;	   if(root){ lheight=height(root->lchild);	             rheight=height(root->rchild);				 if(lheight>rheight) return lheight+1;				 else return rheight+1;                }        else  return 0; }void BiTree::swapTree(BiNode *root)///左后树交换{	BiNode *temp;	if(root){ temp=root->lchild;	root->lchild=root->rchild;	root->rchild=temp;	swapTree(root->lchild);	swapTree(root->rchild); 	}}void BiTree::PreOrder(BiNode *root){	if (root ==NULL) return;	else { cout<
      
       data;	PreOrder(root->lchild);	PreOrder(root->rchild); }}int main() {	char ch='Y';	while(ch=='Y'){		BiTree bt;		bt.number=0;		bt.countNode();		cout<
       
        <
        
         >ch; }	return 0;}

线索二叉树的实现：

enum flag{Child,Thread};template
     
      struct ThrNode{    T data;    ThrNode
      
        *lchild,*rchild;    flag ltag,rtag;};template
       
        class InThrBiTree{   public:       InThrBiTree(){this->root=Creat();ThrBiTree(root);}       ~InThrBiTree();        ThrNode
        
         *Next(ThrNode
         
           *p);        void InOrder(ThrNode
          
            *root); ThrNode
           
             *pre; private: ThrNode
            
              *root; ThrNode
             
               * Creat(); void ThrBiTree(ThrNode
              
                *root);};template 
               
                ThrNode
                
                 * InThrBiTree
                 
                  ::Creat( ){ ThrNode
                  
                    *root; T ch; cout<<"请输入创建一棵二叉树的结点数据"<
                   
                    >ch; if (ch=="#") root = NULL; else{ root=new ThrNode
                    
                     ; root->data = ch; root->ltag = Child; root->rtag = Child; root->lchild = Creat( ); root->rchild = Creat( ); } return root;}template
                     
                      void InThrBiTree
                      
                       ::ThrBiTree(ThrNode
                       
                         *root)///递归实现线索二叉树{ if(root==NULL) return; else { if(!root->lchid) { root->lrag=Thread; root->lchild=pre; } } if(!root->rchild) root->rtag=Thread; if(!pre) { if(pre->rtag==Thread) { pre->rchild=root; } } pre==root; ThrBiTree(root->rchild);}template
                        
                         ThrNode
                         
                          * InThrBiTree
                          
                           ::Next(ThrNode
                           
                             *p){ ThrNode
                            
                             *q;///要查找的P的后继 if(p->rtag==Thread) q=p->rchild; else { q=p->rchild; while(q->ltag==Child) { q=q->lchild; } } return q;}template
                             
                              void InThrBiTree
                              
                               ::InOrder(ThrNode
                               
                                 *root){ ThrNode
                                
                                  *p=root; if(root==NULL) return; while(p->ltag==Child) {p=p->lchild;cout<
                                 
                                  data<<" ";} while(!p->rchild) { p=Next(p); cout<
                                  
                                   data<<" "; } cout<

转载于:https://www.cnblogs.com/dean-SunPeishuai/p/10674881.html

你可能感兴趣的文章