二叉树的总结

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;
}