数据结构 二叉树的递归与非递归

C语言中总括2叉树的幅度的两种艺术

本文实例讲述了C语言完成线索二叉树的概念与遍历。分享给我们供大家参谋,具体如下:

数据结构 二叉树的递归与非递归

本文实例讲述了PHP完结贰叉树深度优先遍历(前序、中序、后序)和广度优先遍历(档次)。分享给我们供大家参照他事他说加以考察,具体如下:

二叉树作为一种很奇特的数据结构,作用上有一点都不小的功力!后日就来探望怎么计算贰个2叉树的最大的宽度吧。

#include <stdio.h>
#include <malloc.h>
typedef char TElemType;
// 二叉树的二叉线索存储表示
typedef enum{
 Link,
 Thread
}PointerTag; // Link(0):指针,Thread(1):线索
typedef struct BiThrNode
{
 TElemType data;
 struct BiThrNode *lchild,*rchild; // 左右孩子指针
 PointerTag LTag,RTag; // 左右标志
}BiThrNode,*BiThrTree;
TElemType Nil = ' '; // 字符型以空格符为空
BiThrTree pre; // 全局变量,始终指向刚刚访问过的结点
// 按先序输入二叉线索树中结点的值,构造二叉线索树T
// 空格(字符型)表示空结点
int CreateBiThrTree(BiThrTree *T)
{
 TElemType h;
 scanf("%c",&h);
 if(h==Nil)
 *T=NULL;
 else
 {
 *T=(BiThrTree)malloc(sizeof(BiThrNode));
 if(!*T)
  exit(0);
 (*T)->data=h; // 生成根结点(先序)
 CreateBiThrTree(&(*T)->lchild); // 递归构造左子树
 if((*T)->lchild) // 有左孩子
  (*T)->LTag=Link;
 CreateBiThrTree(&(*T)->rchild); // 递归构造右子树
 if((*T)->rchild) // 有右孩子
  (*T)->RTag=Link;
 }
 return 1;
}
// 算法6.7 P135
// 中序遍历进行中序线索化。
void InThreading(BiThrTree p)
{
 if(p)
 {
 InThreading(p->lchild); // 递归左子树线索化
 if(!p->lchild) // 没有左孩子
 {
  p->LTag=Thread; // 前驱线索
  p->lchild=pre; // 左孩子指针指向前驱
 }
 if(!pre->rchild) // 前驱没有右孩子
 {
  pre->RTag=Thread; // 后继线索
  pre->rchild=p; // 前驱右孩子指针指向后继(当前结点p)
 }
 pre=p; // 保持pre指向p的前驱
 InThreading(p->rchild); // 递归右子树线索化
 }
}
// 算法6.6 P134
// 中序遍历二叉树T,并将其中序线索化,Thrt指向头结点。
int InOrderThreading(BiThrTree *Thrt,BiThrTree T)
{ *Thrt=(BiThrTree)malloc(sizeof(BiThrNode)); // 建头结点
 if(!*Thrt)
 exit(0);
 (*Thrt)->LTag=Link; //标志左孩子为指针
 (*Thrt)->RTag=Thread; //标志右孩子为线索
 (*Thrt)->rchild=*Thrt; // 右指针回指
 if(!T) // 若二叉树空,则左指针回指
 (*Thrt)->lchild=*Thrt;
 else
 {
 (*Thrt)->lchild=T; //头结点左指针指向树的根
 pre = *Thrt;
 InThreading(T); // 中序遍历进行中序线索化
 pre->RTag=Thread; // 最后一个结点线索化
 pre->rchild=*Thrt;
 (*Thrt)->rchild=pre;
 }
 return 1;
}
// 算法6.5 P134
// 中序遍历二叉线索树T(头结点)的非递归算法。
int InOrderTraverse_Thr(BiThrTree T,int(*Visit)(TElemType))
{
 BiThrTree p;
 p=T->lchild; // p指向根结点
 while(p!=T)
 { // 空树或遍历结束时,p==T
 while(p->LTag==Link)
  p=p->lchild;
 if(!Visit(p->data)) // 访问其左子树为空的结点
  return 0;
 while(p->RTag==Thread&&p->rchild!=T)
 {
  p=p->rchild;
  Visit(p->data); // 访问后继结点
  }
 p=p->rchild;
 }
 return 1;
}
int vi(TElemType c)
{
 printf("%c ",c);
 return 1;
}
int main()
{
 BiThrTree H,T;
 printf("请按先序输入二叉树(如:ab三个空格,表示a为根结点,"
 "b为左子树的二叉树)\n");
 CreateBiThrTree(&T); // 按先序产生二叉树
 InOrderThreading(&H,T); // 中序遍历,并中序线索化二叉树
 printf("中序遍历(输出)二叉线索树:\n");
 InOrderTraverse_Thr(H,vi); // 中序遍历(输出)二叉线索树
 printf("\n");
 system("pause");
 return 0;
}

实例代码:

前言:

运用递归格局

运维结果:

#include <iostream> 
#include <queue> 
#include <stack> 
#include <assert.h> 
using namespace std; 
template<class T> 
struct BinaryTreeNode 
{ 
  BinaryTreeNode<T>* _left; 
  BinaryTreeNode<T>* _right; 
  T _data; 
  BinaryTreeNode(const T& x) 
    :_left(NULL) 
    , _right(NULL) 
    , _data(x) 
  {} 
    }; 
template <class T> 
class BinaryTree 
{ 
  typedef BinaryTreeNode<T> Node; 
public: 
  BinaryTree() 
    :_root(NULL) 
  {} 
  BinaryTree(T* a, size_t n, const T& invalid) 
  { 
    size_t index = 0; 
     _root=CreateTree(a, n, invalid, index); 
  } 
  BinaryTree(const BinaryTree<T>& t) 
  {  
    _root = _Copy(t._root); 
  } 
  BinaryTree<T>& operator=( BinaryTree<T>& t) 
  { 
    swap(_root,t._root); 
    return *this; 
  } 
  ~BinaryTree() 
  { 
      _DestroyTree(_root); 
  } 
  Node* CreateTree(const T* a, size_t n, const T& invalid, size_t& index) 
  { 
    assert(a); 
    Node* root = NULL; 
    if (index < n && a[index] != invalid) 
    { 
      root = new Node(a[index]); 
      root->_left = CreateTree(a, n, invalid, ++index); 
      root->_right = CreateTree(a, n, invalid, ++index); 
    } 
    return root; 
  } 

纵深优先遍历:对每一个或者的道岔路线深远到不能够再长远甘休,而且每种结点只好访问一回。要非常注意的是,2叉树的深浅优先遍历相比特殊,能够细分为先序遍历、中序遍历、后序遍历。具体表明如下:

上边是代码内容:

图片 1

 先序遍历(递归法)  

前序遍历:根节点->左子树->右子树
中序遍历:左子树->根节点->右子树
后序遍历:左子树->右子树->根节点

int GetMaxWidth(BinaryTree pointer){
  int width[10];//加入这棵树的最大高度不超过10
  int maxWidth=0;
  int floor=1;
  if(pointer){
    if(floor==1){//如果访问的是根节点的话,第一层节点++;
      width[floor]++;
      floor++;
      if(pointer->leftChild)
        width[floor]++;
      if(pointer->rightChild)
        width[floor]++;
    }else{
      floor++;
      if(pointer->leftChild)
        width[floor]++;
      if(pointer->rightChild)
        width[floor]++;
    }
    if(maxWidth<width[floor])
      maxWidth=width[floor];
    GetMaxWidth(pointer->leftChild);
    floor--;//记得退回一层,否则会出错。因为已经Get过了,所以要及时的返回。
    GetMaxWidth(pointer->rightChild);
  }
  return maxWidth;
}

梦想本文所述对大家C语言程序设计有所帮助。

 void PrevOrder() 
  { 
    _PrevOrder(_root); 
    cout << endl; 
  } 
  //先序遍历非递归 
  void PrevOrderNorR( ) 
  { 
    Node* cur = _root; 
    stack< Node* >s; 
    while (cur||!s.empty()) 
    { 
      while (cur) 
      { 
        cout << cur->_data << " "; 
        s.push(cur); 
        cur = cur->_left; 
      } 
      Node* top = s.top(); 
      s.pop(); 
      cur = top->_right; 
    } 
    cout << endl; 
  } 

广度优先遍历:又叫档期的顺序遍历,从上往下对每一层依次走访,在每一层中,从左往右(也足以从右往左)访问结点,访问完1层就进入下壹层,直到未有结点能够访问停止。

利用非递归形式

你恐怕感兴趣的小说:

  • c语言版本2叉树基本操作示例(先序 递归
    非递归)
  • 应用C语言营造基本的二叉树数据结构
  • C语言达成二叉树遍历的迭代算法
  • C语言中总括二叉树的肥瘦的两种艺术
  • 用C语言决断1个2叉树是不是为另多个的子结构
  • C语言 二叉树的链式存款和储蓄实例
  • C语言二叉树的非递归遍历实例深入分析
  • 接纳C语言求2叉树结点的最低公共祖先的秘籍
  • C语言数据结构之线索2叉树及其遍历
  • C语言实现二叉树的检索及连锁算法示例
  • C语言2叉树常见操作详解【前序,中序,后序,档次遍历及非递归查找,总计个数,相比,求深度】

后序遍历     

比方说对于时而这棵树:

接纳非递归形式测算②叉树的小幅度要求注重队列。代码如下:

 void PostOrder() 
  { 
    _PostOrder(_root); 
    cout << endl; 
  } 
  //后序遍历非递归 
  void PostOrderNorR() 
  {  
      Node* cur = _root; 
      Node* prev = NULL; 
      stack< Node* >s; 
      while (cur || !s.empty()) 
      { 
        while (cur) 
        { 
          s.push(cur); 
          cur = cur->_left; 
        } 
        Node* top = s.top(); 
        if (NULL==top->_right && prev==top->_right) 
        { 
          cout << top->_data << " "; 
           s.pop(); 
           prev = top; 
        } 
        cur = top->_right; 
      } 
      cout << endl; 
  } 

  //中序遍历 
  void InOrder() 
  { 
    _InOrder(_root); 
    cout << endl; 
  } 
  //中序遍历非递归 
  void InOrderNorR() 
  { 
    Node* cur = _root; 
    stack< Node* >s; 
    while (cur || !s.empty()) 
    { 
      while (cur) 
      { 
        s.push(cur); 
        cur = cur->_left; 
      } 
      Node* top = s.top(); 
      s.pop(); 
      cout << top->_data << " "; 
      cur = top->_right; 
    } 
    cout << endl; 
  } 

  //节点个数 
  size_t Size() 
  { 
    return _Size(_root); 
  } 
  //叶子节点个数 
  size_t LeafSize() 
  { 
    return _LeafSize(_root); 
  } 
  //树的深度 
  size_t Depth() 
  { 
    return _Depth(_root); 
  }  
  size_t GetKLevel(size_t k) 
  { 
    return _GetKLevel(_root,k); 
  } 
  // 查找 
  Node* Find(size_t x) 
  { 
    return _Find(_root,x); 
  } 
  //层序遍历 
  void LevelOrder() 
  { 
    queue<Node*> q; 
    if (_root) 
    { 
      q.push(_root); 
    } 
    while (!q.empty()) 
    { 
      Node* front = q.front(); 
      cout << front->_data << " "; 
      q.pop(); 
      if (front->_left) 
      { 
        q.push(front->_left); 
      } 
      if (front->_right) 
      { 
        q.push(front->_right); 
      } 
    } 
    cout << endl; 
  } 

protected: 
  Node* _Copy(Node* root) 
  { 
    if (root==NULL) 
    { 
      return NULL; 
    } 
    Node* NewRoot = new Node(root->_data); 
    NewRoot->_left = _Copy(root->_left); 
    NewRoot->_right = _Copy(root->_right); 
    return NewRoot; 
  } 
  void _DestroyTree(Node* root) 
  { 
    if (NULL==root) 
    { 
      return; 
    } 
   _DestroyTree(root->_left); 
   _DestroyTree(root->_right); 
   delete root; 
  } 
  void _PrevOrder(BinaryTreeNode<T>* root) 
  { 
    if (root) 
    { 
      cout << root->_data << " ";  
      _PrevOrder(root->_left); 
      _PrevOrder(root->_right); 
    }   
  } 
  void _PostOrder(BinaryTreeNode<T>* root) 
  { 
    if (root) 
    { 
      _PostOrder(root->_left); 
      _PostOrder(root->_right); 
      cout << root->_data << " "; 
    } 
  } 
  void _InOrder(BinaryTreeNode<T>* root) 
  { 
    if (root) 
    { 
      _InOrder(root->_left); 
      cout << root->_data << " "; 
      _InOrder(root->_right); 

    } 
  } 
  int _Size(BinaryTreeNode<T>* root) 
  { 
   if (root==0) 
   { 
     return 0; 
   } 
   return _Size(root->_left) + _Size(root->_right) + 1; 
  } 
  int _LeafSize(BinaryTreeNode<T>* root) 
  { 
    if (root==NULL) 
    { 
    return 0; 
    } 
    else if (root->_left == NULL&&root->_right == NULL) 
    { 
      return 1; 
    } 
    return _LeafSize(root->_left) + _LeafSize(root->_right); 
  } 
  int _Depth(Node* root) 
  { 
    if (root==NULL) 
    { 
      return 0; 
    } 
    int left = _Depth(root->_left); 
    int right = _Depth(root->_right); 
    return left > right ? left + 1 : right + 1; 
  } 


  int _GetKLevel(Node* root, size_t k) 
  { 
    assert(k>0); 
    if (root==NULL) 
    { 
      return 0; 
    } 
    else if (k==1) 
    { 
      return 1; 
    } 
    return _GetKLevel(root->_left, k - 1) + _GetKLevel(root->_right, k - 1); 
  } 
  Node* _Find(Node* root, const T& x) 
  { 
    if (root==NULL) 
    { 
      return NULL; 
    } 
    if (root->_data==x) 
    { 
      return root; 
    } 
    Node* ret = _Find(root->_left,x); 
    if (ret != NULL) 
      return ret; 
    return _Find(root->_right, x); 
  } 

  private: 
  BinaryTreeNode<T>* _root; 
}; 





void TestBinaryTree() 
{ 
  int array[10] = { 1, 2, 3, '#', '#', 4, '#', '#', 5, 6 }; 
  BinaryTree<int> t1(array,sizeof(array)/sizeof(array[0]),'#'); 
  BinaryTree<int>t2(t1); 
  BinaryTree<int> t3; 
  t3 = t2; 
  t2.LevelOrder(); 
  t3.LevelOrder(); 
  t1.LevelOrder(); 
  t1.PrevOrder(); 
  t1.PrevOrderNorR(); 
  t1.InOrder(); 
  t1.InOrderNorR(); 
  t1.PostOrder(); 
  t1.PostOrderNorR(); 
  cout << endl; 
  cout << t1.Size() << endl; 
  cout << t1.LeafSize() << endl; 
  cout << t1.Depth() << endl; 

  cout << t1.GetKLevel(2) << endl; 
  cout << t1.Find(2) << endl; 
} 

图片 2

int GetMaxWidth(BinaryTree pointer){
  if(pointer==null){
    return 0;
  }
  Queue<BinaryTreeNode> queue=new ArrayDeque<BinaryTreeNode>();
  int maxWidth=1;//最大宽度
  queue.add(pointer);
  while(true){
    int size=queue.size();//计算当前层的节点的个数
    if(size==0){
      break;
    }
    while(size>0){//如果当前层还有节点就进行下去
      BinaryTreeNode node=queue.poll();
      size--;
      if(node->leftChild)
        queue.add(node->leftChild);//当前节点的左子树入队
      if(node->rightChild)
        queue.add(node->rightChild);//当前节点的右子树入队
      maxWidth=Math.max(size,queue.size());
    }
  }
  return maxWidth;//返回计算所得的最大的二叉树的宽度。
}

感谢阅读,希望能扶助到大家,多谢大家对本站的帮忙!

纵深优先遍历:

总结:

您大概感兴趣的篇章:

  • C++
    数据结构2叉树(前序/中序/后序递归、非递归遍历)
  • C++使用递归和非递归算法达成的二叉树叶子节点个数总结方法
  • C++基于递归和非递归算法剖断四个2叉树结构是还是不是完全同样(结构和数码都如出一辙)
  • C++基于递归和非递归算法求二叉树镜像的艺术
  • C++非递归队列达成二叉树的广度优先遍历
  • C++非递归构建2叉树实例
  • C语言数据结构之二叉树的非递归后序遍历算法

前序遍历:十 8 柒 九 1贰 1壹 一三
中序遍历:柒 8 九 10 1一 1贰 一三
后序遍历:七 九 八 1一 一三 1贰 10

发表评论

电子邮件地址不会被公开。 必填项已用*标注

CopyRight © 2015-2020 金沙中心城 All Rights Reserved.
网站地图xml地图