三叉链表实现二叉树的基本操作-白红宇

强烈建议你试试无所不能的chatGPT，快点击我

三叉链表实现二叉树的基本操作

阅读量：6319 次

发布时间：2019-06-22

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

三叉链表存储表示

改进于二叉链表，增加指向父节点的指针，能更好地实现结点间的访问。

存储结构

/* 二叉树的三叉链表存储表示 */ typedef struct BiTPNode {   TElemType data;   struct BiTPNode *parent,*lchild,*rchild; /* 双亲、左右孩子指针 */ }BiTPNode,*BiPTree;

下面给出二叉树采用三叉链表，实现了二叉树的构造、遍历、深度、宽度、结点个数、叶子个数以及结点的交换、层次、祖先、双亲、左孩子、右孩子、左兄弟、右兄弟各种功能：

#include 
    
     using namespace std;const int MaxBTreeSize = 20;template
     
      class BTNode{public:	T data;	BTNode* lchild;	BTNode* rchild;	BTNode* parent;	BTNode():lchild(NULL),rchild(NULL),parent(NULL)	{ }};template
      
       class BTree{public: //提供接口	BTree();	BTree(const BTree
       
        & bTree);	~BTree();	const BTree
        
         & operator=(const BTree
         
          & bTree); void createBTree();//按先序建立二叉树 void InitBiTree(); //初始化二叉树 void destoryBTree();//销毁二叉树 bool isEmptyBTree();//检查二叉树是否为空 void inOrderTraverse(); //中序遍历 void preOrderTraverse();//先序遍历 void postOrderTraverse(); //后序遍历 void levelOrderTraverse();//层序遍历 int heightBTree();//二叉树高度 int widthBTree(); //二叉树宽度 int nodeCountBTree(); //二叉树结点个数 int LeavesCountBTree();//二叉树叶子个数 int nodeLevelBTree(T item);//结点item在的层次 bool allParentBTree(T item);//找item的所有祖先 void findCommonAncestor(const BTNode
          
           * p1,const BTNode
           
            * p2,BTNode
            
             *& ancestor);//二叉树中2个节点p1, p2的最小公共祖先节点 void longPathBTree();//输出从每个叶子结点到根结点的最长路径 bool isFullBTree(); //判断二叉树是否是完全二叉树 void exchangeChildBTree();//交换二叉树的孩子 bool findBTree(const T item,BTNode
             
              *& ret)const; //查找结点 bool getParent(const BTNode
              
               * p,BTNode
               
                *& ret) const; //返回父亲 bool getLeftChild(const BTNode
                
                 * p,BTNode
                 
                  *& ret) const; //返回左孩子 bool getRightChild(const BTNode
                  
                   * p,BTNode
                   
                    *& ret) const; //返回右孩子 bool getLeftSibling(const BTNode
                    
                     * p,BTNode
                     
                      *& ret) const; //返回左兄弟 bool getRightSibling(const BTNode
                      
                       * p,BTNode
                       
                        *& ret) const;//返回右兄弟protected://为了继承 BTNode
                        
                         * root;private://为了实现公有函数 void create(BTNode
                         
                          *& p); //以p为根结点建树 void createParent(BTNode
                          
                           * p); //为以p为根节点的树设置其指向双亲的结点 void copyTree(BTNode
                           
                            *& copyTreeRoot,BTNode
                            
                             * otherTreeRoot); //把以otherTreeRoot为根节点的部分拷贝到copyTreeRoot为根节点的部分 void destory(BTNode
                             
                              *& p); //销毁以p为根节点的部分 void inOrder(BTNode
                              
                               * p); //中序遍历以p为根节点的部分 void preOrder(BTNode
                               
                                * p); //先序遍历以p为根节点的部分 void postOrder(BTNode
                                
                                 * p); //后序遍历以p为根节点的部分 void levelOrder(BTNode
                                 
                                  * p); //层次遍历以p为根节点的部分 int height(BTNode
                                  
                                   * p); //计算以p为根节点的高度 int width(BTNode
                                   
                                    * p); int max(int x,int y); int min(int x,int y); //计算以p为根，俩孩子的最值 int nodeCount(BTNode
                                    
                                     * p); //计算以p为根节点的结点个数 int leavesCount(BTNode
                                     
                                      * p); //计算以p为根节点的叶子个数 void nodeLevel(T item,BTNode
                                      
                                       * p,int level,int& nlevel); //计算以p为根节点的中item所在层次，如有多个元素，则返回一个最小值（离根最近），如果没有出现，则返回0 bool find(BTNode
                                       
                                        *p,const T item,bool& isFind,BTNode
                                        
                                         *& cur)const; //在p指向的二叉树中，返回 值为item的指针 bool allParent(T item,BTNode
                                         
                                          * p,BTNode
                                          
                                           * path[MaxBTreeSize],int& len,int& seat,bool& isFind); //找item的所有祖先 void longPath(BTNode
                                           
                                            * p,int len,int& maxLen,BTNode
                                            
                                             *& longNode); 输出从每个叶子结点到根结点的最长路径 bool isFull(BTNode
                                             
                                              * p); //判断以p为根的二叉树是不是完全二叉树 void exchangeChild(BTNode
                                              
                                               *& p); //交换以p为根节点的二叉树};template
                                               
                                                BTree
                                                
                                                 ::BTree(){ root = NULL;}template
                                                 
                                                  BTree
                                                  
                                                   ::BTree(const BTree
                                                   
                                                    & bTree){ if (bTree.root==NULL) { root = NULL; } else { copyTree(this->root,bTree.root); }}template
                                                    
                                                     BTree
                                                     
                                                      ::~BTree(){ destory(root);}template
                                                      
                                                       const BTree
                                                       
                                                        & BTree
                                                        
                                                         ::operator=(const BTree
                                                         
                                                          & bTree){ if (this!=&bTree)//避免自己赋值 { if (root!=NULL)// { destory(root);//自己有成员，先销毁 } if (bTree.root==NULL) { root = NULL; } else { copyTree(this->root,bTree.root); } } return *this;}template
                                                          
                                                           void BTree
                                                           
                                                            ::createBTree(){ cout<<"按先序次序输入各结点值，输入#表示空结点:"<
                                                            
                                                             void BTree
                                                             
                                                              ::create(BTNode
                                                              
                                                               *& p){ T newData; cin>>newData; if ('#'==newData) { p=NULL; } else { p = new BTNode
                                                               
                                                                ; p->data = newData; //注意，把左孩子链到父亲的左链域的操作是在调用这个函数体的函数体中进行，具体就是p->lchild = new BTNode
                                                                
                                                                 ; create(p->lchild); create(p->rchild); //找到自己的儿子，并为其找到父亲 if (p->lchild!=NULL) { p->lchild->parent = p; } if (p->rchild!=NULL) { p->rchild->parent = p; } }}/*借助先根遍历，边遍历边初始化，在父亲找到儿子时，为儿子赋值*/template
                                                                 
                                                                  void BTree
                                                                  
                                                                   ::createParent(BTNode
                                                                   
                                                                    * p){ if (p==root) { p->parent = NULL; } if (p->lchild!=NULL) { p->lchild->parent = p; } if (p->rchild!=NULL) { p->rchild->parent = p; } createParent(p->lchild); createParent(p->rchild);}template
                                                                    
                                                                     void BTree
                                                                     
                                                                      ::InitBiTree(){ root = NULL;}//借助先序遍历实现二叉树的复制template
                                                                      
                                                                       void BTree
                                                                       
                                                                        ::copyTree(BTNode
                                                                        
                                                                         *& dstTreeRoot,BTNode
                                                                         
                                                                          * srcTreeRoot){ if (srcTreeRoot) { dstTreeRoot = new BTNode
                                                                          
                                                                           ; dstTreeRoot->data = srcTreeRoot->data; copyTree(dstTreeRoot->lchild,srcTreeRoot->lchild); copyTree(dstTreeRoot->rchild,srcTreeRoot->rchild); if (dstTreeRoot->lchild)//如果自己的孩子存在，则为孩子找到孩子的父亲 { dstTreeRoot->lchild->parent = dstTreeRoot; } if (dstTreeRoot->rchild) { dstTreeRoot->rchild->parent = dstTreeRoot; } }}template
                                                                           
                                                                            bool BTree
                                                                            
                                                                             ::isEmptyBTree(){ return (root==NULL);}template
                                                                             
                                                                              void BTree
                                                                              
                                                                               ::preOrderTraverse(){ preOrder(root); cout<
                                                                               
                                                                                
                                                                                 void BTree
                                                                                 
                                                                                  ::preOrder(BTNode
                                                                                  
                                                                                   * p){ if (p) { cout<
                                                                                   
                                                                                    data; preOrder(p->lchild); preOrder(p->rchild); }}template
                                                                                    
                                                                                     void BTree
                                                                                     
                                                                                      ::inOrderTraverse(){ inOrder(root); cout<
                                                                                      
                                                                                       
                                                                                        void BTree
                                                                                        
                                                                                         ::inOrder(BTNode
                                                                                         
                                                                                          * p){ if (p) { inOrder(p->lchild); cout<
                                                                                          
                                                                                           data; inOrder(p->rchild); }}template
                                                                                           
                                                                                            void BTree
                                                                                            
                                                                                             ::postOrderTraverse(){ postOrder(root); cout<
                                                                                             
                                                                                              
                                                                                               void BTree
                                                                                               
                                                                                                ::postOrder(BTNode
                                                                                                
                                                                                                 * p){ if (p) { postOrder(p->lchild);//先访问左结点 postOrder(p->rchild);//再访问右结点 cout<
                                                                                                 
                                                                                                  data; //再访问根 }}template
                                                                                                  
                                                                                                   void BTree
                                                                                                   
                                                                                                    ::levelOrderTraverse(){ levelOrder(root); cout<
                                                                                                    
                                                                                                     
                                                                                                      void BTree
                                                                                                      
                                                                                                       ::levelOrder(BTNode
                                                                                                       
                                                                                                        * p){ BTNode
                                                                                                        
                                                                                                         * cur; //定义队列 int front=0; int rear=0; BTNode
                                                                                                         
                                                                                                          * queue[MaxBTreeSize]; if (p) { queue[(rear++)%MaxBTreeSize]=p; while(front != rear)//队空停止执行 { cur = queue[(front++)%MaxBTreeSize];//总是先出队，在访问，在把孩子入队 cout<
                                                                                                          
                                                                                                           data; if ((rear+1)%MaxBTreeSize != front)//队不满,入左孩子 { if (cur->lchild) { queue[(rear++)%MaxBTreeSize]=cur->lchild; } } if ((rear+1)%MaxBTreeSize != front)//队不满，入右孩子 { if (cur->rchild) { queue[(rear++)%MaxBTreeSize]=cur->rchild; } } } }}template
                                                                                                           
                                                                                                            int BTree
                                                                                                            
                                                                                                             ::heightBTree(){ return height(root);}/*利用后根遍历得到--先算左右子树高度，再计算自己的高度*/template
                                                                                                             
                                                                                                              int BTree
                                                                                                              
                                                                                                               ::height(BTNode
                                                                                                               
                                                                                                                * p){ if (!p) { return 0; } else { /* int lchildHeight = 1+height(p->lchild); int rchildHeight = 1+height(p->rchild); if (lchildHeight > rchildHeight) { return lchildHeight; } else { return rchildHeight; } */ return 1+max(height(p->lchild),height(p->rchild)); }}/*借助层次遍历*/template
                                                                                                                
                                                                                                                 int BTree
                                                                                                                 
                                                                                                                  ::width(BTNode
                                                                                                                  
                                                                                                                   * p){ //使用队列，但是不能使用循环的队列，只能使用一般的队列，因为循环队列正常情况下也会出现front>last BTNode
                                                                                                                   
                                                                                                                    * cur; int front = 0;//这里front总是指向第一个元素，和循环队列没有区别 int rear=0; //这里rear总是指向最后一个元素，和循环队列有区别，循环队列总是指向最后一个元素的下一位front>last int last=0;//last是本层中最右一个节点的下标 int tmpWidth = 0;//tmpWidth表示局部宽度 int maxWidth = 0;//maxWidth保存最大宽度 BTNode
                                                                                                                    
                                                                                                                     * queueBTNode[MaxBTreeSize]; if (!p) { maxWidth=0; } else { //根结点入队 queueBTNode[rear] = p; while(front<=last)//当本层结点还没全部出队 { cur = queueBTNode[front++];//front总是指向第一个元素 tmpWidth++; if (cur->lchild) { queueBTNode[++rear]=cur->lchild;//rear总是指向刚刚入队的结点，即总是指向最后一个元素 } if (cur->rchild) { queueBTNode[++rear]=cur->rchild; } if (front>last)//本层已经处理完毕--队头已经超过上一层的最后一个元素 { last =rear; if (tmpWidth>maxWidth) { maxWidth=tmpWidth; } tmpWidth=0;//重新记录下一层的结点数 } } } return maxWidth;}template
                                                                                                                     
                                                                                                                      int BTree
                                                                                                                      
                                                                                                                       ::widthBTree(){ return width(root);}template
                                                                                                                       
                                                                                                                        int BTree
                                                                                                                        
                                                                                                                         ::nodeCountBTree(){ return nodeCount(root);}/*利用后根遍历得到*/template
                                                                                                                         
                                                                                                                          int BTree
                                                                                                                          
                                                                                                                           ::nodeCount(BTNode
                                                                                                                           
                                                                                                                            * p){ if (!p) { return 0; } else { return 1 + nodeCount(p->lchild) + nodeCount(p->rchild); }}template
                                                                                                                            
                                                                                                                             int BTree
                                                                                                                             
                                                                                                                              ::LeavesCountBTree(){ return leavesCount(root);}/*利用前根遍历得到*/template
                                                                                                                              
                                                                                                                               int BTree
                                                                                                                               
                                                                                                                                ::leavesCount(BTNode
                                                                                                                                
                                                                                                                                 * p){ if (!p) { return 0; } if (p->lchild==NULL && p->rchild==NULL)//先检查下自身是不是叶子，是返回1 { return 1; } else { return leavesCount(p->lchild) + leavesCount(p->rchild);//再求自己的左子树中的叶子个数 和 右子树的叶子个数 之后求和 }}/*如有多个节点，取离根最近的*//*利用先序的方式求层次，遇到第一个节点停止*/template
                                                                                                                                 
                                                                                                                                  void BTree
                                                                                                                                  
                                                                                                                                   ::nodeLevel(T item,BTNode
                                                                                                                                   
                                                                                                                                    * p,int level,int& nlevel){ if(p==NULL)//出口一：结点不存在 { nlevel = 0; } else { if (p->data == item)//出口二：找到该结点 { nlevel=level+1; } else //没找到，则往下递归 { if (nlevel==0) { nodeLevel(item,p->lchild,level+1,nlevel); } if (nlevel==0) { nodeLevel(item,p->rchild,level+1,nlevel); } } }}template
                                                                                                                                    
                                                                                                                                     int BTree
                                                                                                                                     
                                                                                                                                      ::nodeLevelBTree(T item){ int level =0; nodeLevel(item,root,0,level); return level;}/*利用先序遍历，把item的祖先都放到数组path中，之后直接输出，从根开始..要求找到第一个与item相同的结点的 所有双亲*/template
                                                                                                                                      
                                                                                                                                       bool BTree
                                                                                                                                       
                                                                                                                                        ::allParent(T item,BTNode
                                                                                                                                        
                                                                                                                                         * p,BTNode
                                                                                                                                         
                                                                                                                                          * path[MaxBTreeSize],int& len,int& seat,bool& isFind){ if (p!=NULL) { if (!isFind)//没找到的时候才继续找，找到直接跳出 { if (p->data !=item) { path[len++]=p; allParent(item,p->lchild,path,len,seat,isFind); allParent(item,p->rchild,path,len,seat,isFind); len--; } else { isFind = true; seat = len;//记录双亲个数 } } } return isFind;}template
                                                                                                                                          
                                                                                                                                           bool BTree
                                                                                                                                           
                                                                                                                                            ::allParentBTree(T item){ int seat = 0; bool isFind = false; BTNode
                                                                                                                                            
                                                                                                                                             * path[MaxBTreeSize]; int len = 0;//数组最后一个元素的位置 allParent(item,root,path,len,seat,isFind); for (int i=0;i
                                                                                                                                             
                                                                                                                                              data; } cout<
                                                                                                                                              
                                                                                                                                               bool BTree
                                                                                                                                               
                                                                                                                                                ::isFull(BTNode
                                                                                                                                                
                                                                                                                                                 * p){ bool isExist = false;//表示现在这个状态下,队列中是不是存在空指针 /* 当队中出现空指针时，看看空指针之后是不是有非空的指针， 如果空指针后有非空指针出现，则肯定不是完全二叉树, 如果空指针之后没有非空指针，则是完全二叉树 */ BTNode
                                                                                                                                                 
                                                                                                                                                  * cur; //定义队列 int front=0; int rear=0; BTNode
                                                                                                                                                  
                                                                                                                                                   * queue[MaxBTreeSize]; if (p) { queue[(rear++)%MaxBTreeSize]=p; while(front != rear)//队空停止执行 { cur = queue[(front++)%MaxBTreeSize];//总是先出队，在访问，在把孩子入队 if (cur==NULL)//入队的有空指针,使用标志位isExist记录，表示已经出现过空，之后再遇到非空时，就表示为不是完全二叉树。 { isExist = true; } else { if (isExist && (cur->lchild!=NULL || cur->rchild!=NULL)) { return false;//在cur指向之前已经有空指针出现，现在又有非空指针出现，则不是完全二叉树 } //不管孩子是否为空,都入队列 if ((rear+1)%MaxBTreeSize != front)//队不满,入左孩子 { queue[(rear++)%MaxBTreeSize]=cur->lchild; } if ((rear+1)%MaxBTreeSize != front)//队不满，入右孩子 { queue[(rear++)%MaxBTreeSize]=cur->rchild; } } } } return true;//执行至此必为队空且中间无空指针，是完全二叉树}template
                                                                                                                                                   
                                                                                                                                                    bool BTree
                                                                                                                                                    
                                                                                                                                                     ::isFullBTree(){ if (isFull(root)) { return true; } return false;}template
                                                                                                                                                     
                                                                                                                                                      void BTree
                                                                                                                                                      
                                                                                                                                                       ::longPathBTree(){ BTNode
                                                                                                                                                       
                                                                                                                                                        * longPathNode=NULL; int maxlen = 0; longPath(root,0,maxlen,longPathNode);//调用longPath函数能找到路径最长的那个叶子 if (root==NULL) { cout<<"二叉树为空！"<
                                                                                                                                                        
                                                                                                                                                         * cur = longPathNode; while(cur!=root) { cout<
                                                                                                                                                         
                                                                                                                                                          data; cur = cur->parent; } cout<
                                                                                                                                                          
                                                                                                                                                           data<
                                                                                                                                                           
                                                                                                                                                            void BTree
                                                                                                                                                            
                                                                                                                                                             ::longPath(BTNode
                                                                                                                                                             
                                                                                                                                                              * p,int len,int& maxLen,BTNode
                                                                                                                                                              
                                                                                                                                                               *& longNode){ if (p==NULL) { len=0; } else { len++; if (p->lchild==NULL && p->rchild==NULL)//到达叶子时才能达到最大，这时才与最大值比较 { if (len>maxLen) { maxLen = len; longNode = p; } } else { longPath(p->lchild,len,maxLen,longNode); longPath(p->rchild,len,maxLen,longNode); } len--;//要向上走，长度应该减一 }}/*利用先序遍历得到*/template
                                                                                                                                                               
                                                                                                                                                                void BTree
                                                                                                                                                                
                                                                                                                                                                 ::exchangeChild(BTNode
                                                                                                                                                                 
                                                                                                                                                                  *& p){ if(p) { if (p->lchild!=NULL || p->rchild!=NULL)//结点子树不为空，则交换左右子树 { BTNode
                                                                                                                                                                  
                                                                                                                                                                   * temp; temp = p->lchild; p->lchild = p->rchild; p->rchild = temp; } exchangeChild(p->lchild); exchangeChild(p->rchild); }}template
                                                                                                                                                                   
                                                                                                                                                                    void BTree
                                                                                                                                                                    
                                                                                                                                                                     ::exchangeChildBTree(){ exchangeChild(root);}template
                                                                                                                                                                     
                                                                                                                                                                      void BTree
                                                                                                                                                                      
                                                                                                                                                                       ::findCommonAncestor(const BTNode
                                                                                                                                                                       
                                                                                                                                                                        * p1,const BTNode
                                                                                                                                                                        
                                                                                                                                                                         * p2,BTNode
                                                                                                                                                                         
                                                                                                                                                                          *& ancestor){ int seat1=0;//记录找到时双亲的个数 int seat2=0; int len_p1=0;//记录正在处理结点的层次数 int len_p2=0; bool isFind_p1 = false;//二叉树中是否存在p1指向的结点 bool isFind_p2 = false; BTNode
                                                                                                                                                                          
                                                                                                                                                                           * path_p1[MaxBTreeSize]; BTNode
                                                                                                                                                                           
                                                                                                                                                                            * path_p2[MaxBTreeSize]; allParent(p1->data,root,path_p1,len_p1,seat1,isFind_p1); allParent(p2->data,root,path_p2,len_p2,seat2,isFind_p2); //当seat1 = seat2 = 0时，表示二叉树中没有此结点 for (int i=0;i<=seat1 && i<=seat2 ;i++) { if (path_p1[i] != path_p2[i]) { ancestor = path_p1[i-1]; return; } }}template
                                                                                                                                                                            
                                                                                                                                                                             void BTree
                                                                                                                                                                             
                                                                                                                                                                              ::destoryBTree(){ destory(root);}/*使用后根的方式销毁二叉树*/template
                                                                                                                                                                              
                                                                                                                                                                               void BTree
                                                                                                                                                                               
                                                                                                                                                                                ::destory(BTNode
                                                                                                                                                                                
                                                                                                                                                                                 *& p){ if(p) { destory(p->lchild);//销毁左子树 destory(p->rchild);//销毁右子树 delete p; //销毁根 p=NULL; }}template
                                                                                                                                                                                 
                                                                                                                                                                                  int BTree
                                                                                                                                                                                  
                                                                                                                                                                                   ::max(int x,int y){ if (x>y) { return x; } else { return y; }}template
                                                                                                                                                                                   
                                                                                                                                                                                    int BTree
                                                                                                                                                                                    
                                                                                                                                                                                     ::min(int x,int y){ if (x>y) { return y; } else { return x; }}template
                                                                                                                                                                                     
                                                                                                                                                                                      bool BTree
                                                                                                                                                                                      
                                                                                                                                                                                       ::findBTree(const T item,BTNode
                                                                                                                                                                                       
                                                                                                                                                                                        *& ret)const{ bool isFind = false; return find(root,item,isFind,ret);}/*使用先序查找*/template
                                                                                                                                                                                        
                                                                                                                                                                                         bool BTree
                                                                                                                                                                                         
                                                                                                                                                                                          ::find(BTNode
                                                                                                                                                                                          
                                                                                                                                                                                           *p,const T item,bool& isFind,BTNode
                                                                                                                                                                                           
                                                                                                                                                                                            *& cur)const{ if (p) { if (!isFind) { if (p->data!=item)//没有找到继续栈 { find(p->lchild,item,isFind,cur); } else { isFind = true; cur = p; } if (p->data!=item)//没有找到继续栈 { find(p->rchild,item,isFind,cur); } else { isFind = true; cur = p; } } } return isFind;}template
                                                                                                                                                                                            
                                                                                                                                                                                             bool BTree
                                                                                                                                                                                             
                                                                                                                                                                                              ::getParent(const BTNode
                                                                                                                                                                                              
                                                                                                                                                                                               * p,BTNode
                                                                                                                                                                                               
                                                                                                                                                                                                *& ret) const{ if(p->parent) { ret = p->parent; return true; } return false;}template
                                                                                                                                                                                                
                                                                                                                                                                                                 bool BTree
                                                                                                                                                                                                 
                                                                                                                                                                                                  ::getLeftChild(const BTNode
                                                                                                                                                                                                  
                                                                                                                                                                                                   * p,BTNode
                                                                                                                                                                                                   
                                                                                                                                                                                                    *& ret) const{ if (p->lchild) { ret = p->lchild; return true; } return false;}template
                                                                                                                                                                                                    
                                                                                                                                                                                                     bool BTree
                                                                                                                                                                                                     
                                                                                                                                                                                                      ::getRightChild(const BTNode
                                                                                                                                                                                                      
                                                                                                                                                                                                       * p,BTNode
                                                                                                                                                                                                       
                                                                                                                                                                                                        *& ret) const{ if (p->rchild) { ret = p->rchild; return true; } return false;}template
                                                                                                                                                                                                        
                                                                                                                                                                                                         bool BTree
                                                                                                                                                                                                         
                                                                                                                                                                                                          ::getLeftSibling(const BTNode
                                                                                                                                                                                                          
                                                                                                                                                                                                           * p,BTNode
                                                                                                                                                                                                           
                                                                                                                                                                                                            *& ret) const{ if (p->parent) { if (p->parent->lchild != p)//判断是否等于自身 { ret = p->parent->lchild; return true; } } return false;}template
                                                                                                                                                                                                            
                                                                                                                                                                                                             bool BTree
                                                                                                                                                                                                             
                                                                                                                                                                                                              ::getRightSibling(const BTNode
                                                                                                                                                                                                              
                                                                                                                                                                                                               * p,BTNode
                                                                                                                                                                                                               
                                                                                                                                                                                                                *& ret) const{ if (p->parent) { if (p->parent->rchild != p)//判断是否等于自身 { ret = p->parent->rchild; return true; } } return false;}//代码测试int main(){ BTree
                                                                                                                                                                                                                
                                                                                                                                                                                                                  tree; tree.createBTree(); //---遍历 cout<<"中序遍历:"; tree.inOrderTraverse(); cout<<"先序遍历:"; tree.preOrderTraverse(); cout<<"后序遍历:"; tree.postOrderTraverse(); cout<<"层次遍历:"; tree.levelOrderTraverse(); //调用拷贝构造函数 BTree
                                                                                                                                                                                                                 
                                                                                                                                                                                                                   tree1 = tree; //---结点个数，叶子个数 cout<<"叶子个数:"<
                                                                                                                                                                                                                  
                                                                                                                                                                                                                   <
                                                                                                                                                                                                                   
                                                                                                                                                                                                                    * ancestor = NULL; BTNode
                                                                                                                                                                                                                    
                                                                                                                                                                                                                     * ret1=NULL; BTNode
                                                                                                                                                                                                                     
                                                                                                                                                                                                                      * ret2=NULL; if (tree1.findBTree('C',ret1) && tree1.findBTree('G',ret2)) { tree1.findCommonAncestor(ret1,ret2,ancestor); cout<
                                                                                                                                                                                                                      
                                                                                                                                                                                                                       data<<"和"<
                                                                                                                                                                                                                       
                                                                                                                                                                                                                        data<<"的最近祖先为:"<
                                                                                                                                                                                                                        
                                                                                                                                                                                                                         data<
                                                                                                                                                                                                                         
                                                                                                                                                                                                                           tree2; tree2 = tree; //---结点D的层次、祖先、双亲、左孩子、右孩子、左兄弟、右兄弟 BTNode
                                                                                                                                                                                                                          
                                                                                                                                                                                                                           * cur = NULL; if (tree2.findBTree('D',cur))//判断二叉树中是不是有结点D { cout<<"D所在的层次为:"<
                                                                                                                                                                                                                           
                                                                                                                                                                                                                            <
                                                                                                                                                                                                                            
                                                                                                                                                                                                                             * ret=NULL; if (tree2.getParent(cur,ret)) { cout<
                                                                                                                                                                                                                             
                                                                                                                                                                                                                              data<<"的双亲为:"<
                                                                                                                                                                                                                              
                                                                                                                                                                                                                               data<
                                                                                                                                                                                                                               
                                                                                                                                                                                                                                data<<"没有双亲!"<
                                                                                                                                                                                                                                
                                                                                                                                                                                                                                 data<<"的左孩子为:"<
                                                                                                                                                                                                                                 
                                                                                                                                                                                                                                  data<
                                                                                                                                                                                                                                  
                                                                                                                                                                                                                                   data<<"没有左孩子!"<
                                                                                                                                                                                                                                   
                                                                                                                                                                                                                                    data<<"的右孩子为:"<
                                                                                                                                                                                                                                    
                                                                                                                                                                                                                                     data<
                                                                                                                                                                                                                                     
                                                                                                                                                                                                                                      data<<"没有右孩子!"<
                                                                                                                                                                                                                                      
                                                                                                                                                                                                                                       data<<"的左兄弟为:"<
                                                                                                                                                                                                                                       
                                                                                                                                                                                                                                        data<
                                                                                                                                                                                                                                        
                                                                                                                                                                                                                                         data<<"没有左兄弟!"<
                                                                                                                                                                                                                                         
                                                                                                                                                                                                                                          data<<"的右兄弟为:"<
                                                                                                                                                                                                                                          
                                                                                                                                                                                                                                           data<
                                                                                                                                                                                                                                           
                                                                                                                                                                                                                                            data<<"没有右兄弟!"<

要求输入二叉树的状态：

输入方法：

因为是按先序创建二叉树，因此应该先把要构建的二叉树的先序遍历写出来，没有子树的用#补充，就可以了

测试结果：

转载于:https://www.cnblogs.com/hdk1993/p/4926469.html

你可能感兴趣的文章

诺奖得主Wilczek：人工智能正在解放我们的大脑

自定义企业首页文档

C++实践参考——分数类中的运算符重载

数据库性能测试

如何从开发环境直连线上(IPTables)

记·处理服务端返回data不统一处理

Android Studio3.3你了解多少？

setContentView是如何一步一步被显示出来的？

电脑重装计划

【肥朝】从JDK中，我们能学到哪些设计模式？

RecyclerView综合案例库和系列博客

TensorFlow Build from Source for macOS

前端路由原理解析和实现

北邮前期准备

ES5和ES6中对继承的实现

Introducting To Siri Shortcuts

前端知识储备

阻塞同步异步

小程序分页加载

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！-- 愿君每日到此一游！

当前时间: 2025-01-25 18:02:22 当前IP: 18.119.126.72 联系邮箱:javaeecc@qq.com Copyright © 2020 - 2022 baihongyu.com 京ICP备2021015314号-2

强烈建议你试试无所不能的CHAT-GPT，快点击我

强烈建议你试试无所不能的CHAT-GPT，快点击我