美文网首页
二叉树的总结

二叉树的总结

作者: xiaoyanhan | 来源:发表于2016-10-10 10:35 被阅读220次

    1、二叉树的数据结构

    
typedef struct TreeNode{

char value;\\符号

struct TreeNode * LeftChild;\\左孩子

struct TreeNode * RightChild;\\右孩子

}TreeNode,*Tree;

    2、二叉树的创建

    Tree CreatTree()
{   
    char value;
    TreeNode * Node;
    scanf("%c",&value);
    if(value=='#')//#代表空节点，用来控制树的结构
        Node=NULL;
    else{
        Node=(TreeNode *)malloc(sizeof(TreeNode));
        Node->value=value;
        Node->LeftChild=CreatTree();
        Node->RightChild=CreatTree();
}
    return Node;

}
    树的结构:
    Paste_Image.png
    输入:AB#C##D## ;

    3、二叉树的遍历

    二叉树的遍历分为前序遍历、中序遍历、后序遍历。主要分别在于根节点的遍历优先级。前序：根、左、右；中序：左、根、右；后序：左、右、根。
    ①递归遍历

    Tree Travel(Tree tree)
{
    if(tree==NULL)
          return NULL;
    else
    {        
               /****前序遍历****/
          printf("%c\t",tree->value);
          Travel(tree->LeftChild);
          Travel(tree->RightChild);

              /****中序遍历****/
          Travel(tree->LeftChild);
          printf("%c\t",tree->value);
          Travel(tree->RightChild);

              /****后序遍历****/
          Travel(tree->LeftChild);
          Travel(tree->RightChild); 
          printf("%c\t",tree->value);
    }
}

    ②非递归遍历

    void PreTravel(Tree tree)
{
   stack<Tree> s;
   while(tree||!s.empty())
   {
       while(tree)
       {
           printf("%c\t",tree->value);
           s.push(tree);
           tree=tree->LeftChild;
       }
       tree=s.top();
       s.pop();
       tree=tree->RightChild;
      
   }
}
void MiddleTravel(Tree tree)
{
   stack<Tree> s;
   while(tree||!s.empty())
   {
       while(tree)
       {
           s.push(tree);
           tree=tree->LeftChild;
       }
       tree=s.top();
      printf("%c\t",tree->value);
      s.pop();
      tree=tree->RightChild;
   }
}

void PostTravel(Tree T)  // 后序遍历的非递归      
{      
    stack<Tree> S;      
    Tree curr = T ;           // 指向当前要检查的节点    
    Tree previsited = NULL;    // 指向前一个被访问的节点    
    while(curr != NULL || !S.empty())  // 栈空时结束      
    {      
        while(curr != NULL)            // 一直向左走直到为空    
        {      
            S.push(curr);      
            curr = curr->LeftChild;      
        }      
        curr = S.top();    
        // 当前节点的右孩子如果为空或者已经被访问，则访问当前节点    
        if(curr->RightChild== NULL || curr->RightChild== previsited)      
        {      
            cout<<curr->value<<"  ";      
            previsited = curr;      
            S.pop();      
            curr = NULL;      
        }      
        else    
            curr = curr->RightChild;      // 否则访问右孩子    
    }      
}

    4、求二树的高度

    对此问题我们可以采用递归的思想，将问题进行分解。树的高度=max{左子树的高度，右子树的高度}+1。

    Paste_Image.png 
    int Height(Tree tree)
{
  int high;
  int left_high;
  int right_high;
  if(tree==NULL)
      return 0;
  left_high=Height(tree->LeftChild);
  right_high=Height(tree->RightChild);
  if(left_high>right_high)
        high=left_high+1;
  else
        high=right_high+1;
  return high;
}

    5、二叉树的层次遍历

    算法步骤：

    ①将根结点压进队列Q;
    ②对队列Q进行出队操作，打印出队结点信息，然后将出队结点的左右孩子结点（当其孩子结点存在的情况下）压入队列Q；
    ③重复步骤②的操作直至队列为空

    void HierarchyTravel(Tree tree)
{
     LinkQueue q;;
     Init(&q);
     EnQueue(&q,*tree);
     TreeNode node;
     printf("HierarchyTravel：");
     while(!QueueEmpty(&q))
     {
         DeQueue(&q,&node);
         printf("%c\t",node.value);
         if(node.LeftChild)
             EnQueue(&q,*node.LeftChild);
         if(node.RightChild)
             EnQueue(&q,*node.RightChild);
     }
}

    6、测试代码

    #include "stdafx.h"
#include "stdlib.h"
typedef struct TreeNode{
    char value;
    struct TreeNode * LeftChild;
    struct TreeNode * RightChild;
}TreeNode,*Tree;
typedef struct QNode{
    TreeNode Node;
    struct QNode * next;
}QNode,*QueueNode;
typedef struct LinkQueue{
    QueueNode front;
    QueueNode rear;
}LinkQueue;
Tree CreatTree()
{   
    char value;
    TreeNode * Node;
    scanf("%c",&value);
    if(value=='#')
        Node=NULL;
    else{
        Node=(TreeNode *)malloc(sizeof(TreeNode));
        Node->value=value;
        Node->LeftChild=CreatTree();
        Node->RightChild=CreatTree();
}
    return Node;

}
void PreTravel(Tree tree)
{
    if(tree)
    {
        printf("%c\t",tree->value);
        PreTravel(tree->LeftChild);
        PreTravel(tree->RightChild);
    }
}
void MiddleTravel(Tree tree)
{
    if(tree)
    {   
        MiddleTravel(tree->LeftChild);
        printf("%c\t",tree->value);
        MiddleTravel(tree->RightChild);
    }
}
void PostTravel(Tree tree)
{
    if(tree)
    {   
        PostTravel(tree->LeftChild);    
        PostTravel(tree->RightChild);
        printf("%c\t",tree->value);
    }
}
void Init(LinkQueue *q)//队列初始化
{
    q->front=q->rear=(QueueNode)malloc(sizeof(QNode));

    if(!q->front)
        exit(0);
    q->front->next=NULL;

}
void EnQueue(LinkQueue *q,TreeNode treenode)//入队
{
    QueueNode qnode;
    qnode=(QueueNode)malloc(sizeof(QNode));
    qnode->Node=treenode;
    /****插入队列****/
    qnode->next=q->rear->next;
    q->rear->next=qnode;
    /****改队尾指针****/
    q->rear=qnode;
}
void DeQueue(LinkQueue *q,TreeNode *node)//出队
{
    QueueNode p;
    p=q->front->next;
    *node=p->Node;
    q->front->next=p->next;
    if(q->rear==p)       //p将被释放，需要对q->rear进行处理。（不能缺)
        q->rear=q->front;
    free(p);
}
int QueueEmpty(LinkQueue *q)//判断队列是否为空
{
    if(q->rear==q->front)
        return 1;
    else
        return 0;
}
void HierarchyTravel(Tree tree)
{
     LinkQueue q;;
     Init(&q);
     EnQueue(&q,*tree);
     TreeNode node;
     while(!QueueEmpty(&q))
     {
         DeQueue(&q,&node);
         printf("%c\t",node.value);
         if(node.LeftChild)
             EnQueue(&q,*node.LeftChild);
         if(node.RightChild)
             EnQueue(&q,*node.RightChild);
     }
}
int Height(Tree tree)
{
  int high;
  int left_high;
  int right_high;
  if(tree==NULL)
      return 0;
  left_high=Height(tree->LeftChild);
  right_high=Height(tree->RightChild);
  if(left_high>right_high)
        high=left_high+1;
  else
        high=right_high+1;
  return high;
}
int _tmain(int argc, _TCHAR* argv[])
{  
    Tree tree;
    int high;
    printf("输入二叉树节点:");
    tree=CreatTree();
    printf("\n中序遍历:");
    MiddleTravel(tree);
    printf("\n先序遍历:");
    PreTravel(tree);
    printf("\n后序遍历:");
    PostTravel(tree);
    high=Height(tree);
    printf("\n层次遍历:");
    HierarchyTravel(tree);
    printf("\n树高是:%d\n",high);
    system("PAUSE");
    return 0;
}
    Paste_Image.png

    7、二叉树的非递归遍历代码

    #include "stdafx.h"
#include "stdlib.h"
#include <stack>
#include <iostream>
using namespace std;
typedef struct TreeNode{
    char value;
    struct TreeNode * LeftChild;
    struct TreeNode * RightChild;
}TreeNode,*Tree;
Tree CreatTree()
{   
    char value;
    TreeNode * Node;
    scanf("%c",&value);
    if(value=='#')
        Node=NULL;
    else{
        Node=(TreeNode *)malloc(sizeof(TreeNode));
        Node->value=value;
        Node->LeftChild=CreatTree();
        Node->RightChild=CreatTree();
}
    return Node;

}
void PreTravel(Tree tree)
{
   stack<Tree> s;
   while(tree||!s.empty())
   {
       while(tree)
       {
           printf("%c\t",tree->value);
           s.push(tree);
           tree=tree->LeftChild;
       }
       tree=s.top();
       s.pop();
       tree=tree->RightChild;
      
   }
}
void MiddleTravel(Tree tree)
{
   stack<Tree> s;
   while(tree||!s.empty())
   {
       while(tree)
       {
           s.push(tree);
           tree=tree->LeftChild;
       }
       tree=s.top();
      printf("%c\t",tree->value);
      s.pop();
      tree=tree->RightChild;
   }
}

void PostTravel(Tree T)  // 后序遍历的非递归      
{      
    stack<Tree> S;      
    Tree curr = T ;           // 指向当前要检查的节点    
    Tree previsited = NULL;    // 指向前一个被访问的节点    
    while(curr != NULL || !S.empty())  // 栈空时结束      
    {      
        while(curr != NULL)            // 一直向左走直到为空    
        {      
            S.push(curr);      
            curr = curr->LeftChild;      
        }      
        curr = S.top();    
        // 当前节点的右孩子如果为空或者已经被访问，则访问当前节点    
        if(curr->RightChild== NULL || curr->RightChild== previsited)      
        {      
            cout<<curr->value<<"  ";      
            previsited = curr;      
            S.pop();      
            curr = NULL;      
        }      
        else    
            curr = curr->RightChild;      // 否则访问右孩子    
    }      
}  
int _tmain(int argc, _TCHAR* argv[])
{  
    Tree tree;
    int high;
    printf("输入二叉树节点:");
    tree=CreatTree();
   printf("\n中序遍历:");
    MiddleTravel(tree);
    printf("\n先序遍历:");
    PreTravel(tree);
    printf("\n后序遍历:");
    PostTravel(tree);
 /*   high=Height(tree);
    printf("\n层次遍历:");
    HierarchyTravel(tree);
    printf("\n树高是:%d\n",high);*/
    system("PAUSE");
    return 0;
}

    相关文章

      网友评论

          本文标题：二叉树的总结

          本文链接：https://www.haomeiwen.com/subject/fwwmyttx.html

          延伸阅读

          深度阅读

          • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

          栏目导航

          热点阅读

          关于我们|服务条款|联系我们|二叉树的总结|投稿指南|网站地图|RSS订阅|排版工具|手机版

          提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

          Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

          备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

          本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

          所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！