递归与非递归实现遍历,第五次笔记

C指针编制程序之道 —第伍遍笔记

**//数据结构中指针的运用
//内部存储器中的旅馆和数据结构中的旅社室友不一样的
//在数据结构中,平时把商旅放在一齐表示的后生可畏种数据结构,
//不过在内部存储器中堆是积攒动态的内部存款和储蓄器,栈是存放静态的以致调用的函数。
//在数据结构中提到了旅舍,队列,链表等在那处根本完毕的是队列。
//循环队列的指针应用
#include
#include
#define QueueSize_UarLen 8
using namespace std;
typedef struct
{
int front;
int rear;
int counter;
int uart_data[QueueSize_UartLen];
}CIRQUEUE_UART;

//队列的开始化
void InitQueue(CIRQUEUE_UART *queue)
{
queue->front = 0;
queue->rear = 0;
queue->counter = 0;
}

//入队
int InQueue(CIRQUEUE_UART *queue, int data)
{
if(QueueFull(queue))
{
//输出队列满了
return 0;
}
else
{
queue->uart_data[queue->rear] = data;
queue->counter++;
queue->rear = (queue->rear + 1) % QueueSize_UartLen;
//这里的上一句相当于
//if(queue-
//{
// queue_rear = 0;
//}
//else
//{
// queue->rear ++;
//}
return 1;
}
}

//出队
int OutQueue(CIRQUEUE_UART *queue, int *p_data)
{
if(QueueEmpty(queue))
{
//输出队空提示
//return 0;
}else
{
*p_data = queue->data(font);
queue->counter–;
queue->front = (queue->front + 1) % QueueSize_UartLen;
return 1;
}

}

//推断队列是或不是为空
int QueueEmpty(QueueSize_UartLen *queue)
{
return queue->counter == 0;
}

//剖断是或不是是满的
int QueueFull(QueueSize_UartLen *queue)
{
return queue->counter == QueueSize_UartLen;
}

int main()
{
/**
*
* /
**

}

*//C世界的树
//这里写的是二叉树的两种遍历格局
#include
#include
typedef struct tree_node
{
char data;
struct tree_node
lchild, *rchild;

}BT_Node;

#define Tree_NodeLen sizeof(BT_Node)
BT_Node *tree;
BT_Node *Creat_BTree(BT_Node *t);
void visit_Node(BT_Node *tree);
void Pre_Order(BT_Node *tree);
void Mid_Order(BT_Node *tree);
void After_Order(BT_Node *tree);

int main()
{
printf(“n请输入输的节点n”);
tree = Creat_BTree(Tree);
if(tree)
{
printf(“n前序遍历n”);
Pre_Order(tree);
printf(“n”);

printf(“n中序遍历n”);
Mid_Oder(tree);
printf(“n”);

printf(“n中序遍历n”);
After_Order(tree);
printf(“n”);
}
printf(“n”);
return 0;
}

BT_Node *Create_BTree(BT_Node *tree)
{
char ch;
ch = getchar();
if(ch == ‘*’)
{
tree = null;
}
else
{
tree = (BT_Node *)malloc(Tree_NodeLen);
tree->data = ch;
tree->lchild = Create_BTree(tree->lchild);
tree->rchild = Create_BTree(tree->rchild);
}
return(tree);
}

void Visited_Node(BT_Node *tree)
{
printf(” “);
putchar(tree->data);
printf(“t”);
}

void Pre_Order(BT_Node *tree)
{
if(! tree)
{
return;
}
else
{
Visit_Node(tree);
Pre_Order(tree->lchild);
Pre_Order(tree->rchild);
}
}

void Mid_Order(BT_Node *tree)
{
if(!tree)
{
return;
}
else
{
Mid_Order(tree->lchild);
Visit_Node(tree);
Mid_Order(tree->rchild);
}
}

void After_Order(BT_Node *tree)
{
if(! tree)
{
return;

}
else
{
After_Order(tree->lchild);
After_Order(tree->rchild);
Visited_Node(tree);
}

}
**

—第四次笔记
//数据结构中指针的应用 //内部存储器中的库房和数据结构中的仓库室友差其余//在数据结构中,日常把饭店放在少年老成…

  PreOrderTraverse(pBTree->lchild); // 先序遍历左子树
  PreOrderTraverse(pBTree->rchild); // 先序遍历右子树
 }
}

//
// 最初化栈
int InitStack(Stack *s)
{
 s->base = (StackElemType *)malloc(sizeof(StackElemType) *
STACK_INIT_SIZE);

 printf(“上边实施调换左右子树操作:n”);
 SwapLeftRightSubtree(&tree);

 printf(“n非递归后序遍历:n”);
 NoneRecursionPostOrder(*tree);

 if (pBTree != NULL)
 {
  EnQueue(&queue, *pBTree); // 将根结点指针入队
 }

 if (pBTree->lchild !=
NULL)//leftDepth所表示的层数是周旋以pBTree的左节点为根的树的层数
 {
  leftDepth = GetLevelByValue(pBTree->lchild, e);
 }

 if (pBTree != NULL)
 {
  if ((pBTree->lchild != NULL && pBTree->rchild == NULL) ||
(pBTree->lchild == NULL && pBTree->rchild != NULL))
  {
   count++;
  }

  count += GetCountOfTwoDegree(pBTree->lchild) +
GetCountOfTwoDegree(pBTree->rchild);
 }

#include “Stack.h”

//
// 结点的数目标类型
typedef char ElemType;

  return ERROR;
 }
 else
 {
  pQueue->base[pQueue->rear] = e;
  pQueue->rear = (pQueue->rear + 1) % MAX_QUEUE_SIZE;

/*****************************************************************************
* 方法名:InOrderTraverse
* 描述:  中序遍历二叉树
* 参数:  pBTree–指向BTree结构体的指针
******************************************************************************/
void InOrderTraverse(BTree *pBTree)
{
 if (pBTree)
 {
  InOrderTraverse(pBTree->lchild); // 中序遍历左子树
  printf(“%c”, pBTree->data);       // 中序访问根结点
  InOrderTraverse(pBTree->rchild); // 中序遍历右子树
 }
}

 if (!s->base) // 申请栈内部存款和储蓄器战败
 {
  exit(OVERFLOW);
 }

// 栈体量相当不够用时,栈的增量
#define STACK_SIZE_INCREMENT 10

  count += GetNodesCount(pBTree->lchild) +
GetNodesCount(pBTree->rchild);
 }

 printf(“n=======================================================n”);

 if (pBTree->data == e)//这里的1是相对于以pBTree为根节点的层数值。
 {
  return 1;
 }

 if (pBTree != NULL)
 {
  if (pBTree->lchild != NULL && pBTree->rchild != NULL)
  {
   count++;
  }

 return count;
}

int main()
{
 BTree *tree = NULL;

//
// 开始化栈
int InitStack(Stack *s);

 return 0;
}

 if (leftDepth != 0 || rightDepth != 0) // 判定是还是不是找到该结点
 {
  level++;
 }

#include <stdio.h>

 printf(“n”);
 return 0;
}
[cpp] 
text.txt的内容: 
ABC##DE#G##F### 

#include “BinaryTree.h”

//
// 剖断栈是还是不是为空
// 返回非0表示空
int IsStackEmpty(Stack s)
{
 return !(s.top – s.base);
}

typedef BTree QueueElemType;

//
// 二叉树结构体
typedef struct tagBinaryTree
{
 ElemType data;                 // 数据
 struct tagBinaryTree *lchild;     // 指向左孩子
 struct tagBinaryTree *rchild;     // 指向右孩子
}BTree;

//
// 交流左右子树
void SwapLeftRightSubtree(BTree **pBTree)
{
 BTree *tmp = NULL;

 if (pBTree != NULL)
 {
  count++;

//
// 推断栈是不是为空
int IsStackEmpty(Stack s);

  count += GetCountOfOneDegree(pBTree->lchild) +
GetCountOfOneDegree(pBTree->rchild);
 }

#include <stdio.h>
#include <stdlib.h>

队列头文件:
#include <stdio.h>

栈完毕文件:

  return ERROR;
 }
 else
 {
  *e = pQueue->base[pQueue->front];
  pQueue->front = (pQueue->front + 1) % MAX_QUEUE_SIZE;

 free(q);
}

  depth = leftDepth > rightDepth ? leftDepth + 1: rightDepth + 1;
 }

 return OK;
}

 printf(“n树的吃水为:%dn”, GetDepth(tree));

 if (*pBTree != NULL)
 {
  // 调换当前结点的左右子树
  tmp = (*pBTree)->lchild;
  (*pBTree)->lchild = (*pBTree)->rchild;
  (*pBTree)->rchild = tmp;

 InitializeQueue(&queue); // 初步化队列

栈头文件:

//
// 队列结构体
typedef struct tagQueue
{
 BTree *base;
 int front;      // 头指针提醒器,若队列不空,则指向队列中队头成分
 int rear;       //
尾指针提醒吕,若队列不空,则指向队列队尾的下二个任务
}Queue;

 //
 // 查找结果要么在左子树找到,要么在右子树中找到,要么找不到
 if (leftDepth > 0 && rightDepth == 0) // 在左子树中找到
 {
  level = leftDepth;
 }
 else if (leftDepth == 0 && rightDepth > 0) // 在右子树中找到
 {
  level = rightDepth;
 }

//
// 退队
int DeQueue(Queue *pQueue, QueueElemType *e);
#endif[cpp] view plaincopyprint?
队列完毕文件: 
 
#include <stdio.h>  
#include <stdlib.h>  
 
#include “Queue.h”  
#include “BinaryTree.h”  
 
//  
// 循环队列的得以完成公文:Queue.c  
 
//  
// 构造二个空的类别  
int InitializeQueue(Queue *pQueue) 

    pQueue->base = (QueueElemType *)malloc(sizeof(QueueElemType) *
MAX_QUEUE_SIZE); 
 
    // 申请空间失败,则脱离程序  
    if (pQueue->base == NULL) 
    { 
        exit(OVERFLOW); 
    } 
 
    pQueue->front = pQueue->rear = 0; 
 
    return OK; 

 
//  
// 决断队列是不是为空  
// 重回0表示非空,重回非0,表示空  
int IsQueueEmpty(Queue queue) 

    return !(queue.front – queue.rear); 

 
//  
// 决断队列是还是不是为满  
// 再次来到0表示示满,重回非0,表示已满  
int IsQueueFull(Queue queue) 

    return (queue.rear + 1) % MAX_QUEUE_SIZE == queue.front ; 

 
//  
// 入队  
int EnQueue(Queue *pQueue, QueueElemType e) 

    if (IsQueueFull(*pQueue)) 
    { 
        printf(“队列已经满,不能入队!n”); 
 
        return ERROR; 
    } 
    else 
    { 
        pQueue->base[pQueue->rear] = e; 
        pQueue->rear = (pQueue->rear + 1) % MAX_QUEUE_SIZE; 
 
        return OK; 
    } 

 
//  
// 退队  
int DeQueue(Queue *pQueue, QueueElemType *e) 

    if (IsQueueEmpty(*pQueue)) 
    { 
        printf(“队列为空,不可能实践退队操作n”); 
 
        return ERROR; 
    } 
    else 
    { 
        *e = pQueue->base[pQueue->front]; 
        pQueue->front = (pQueue->front + 1) % MAX_QUEUE_SIZE; 
 
        return OK; 
    } 

/*****************************************************************************
* 方法名:CreateBinaryTree
* 描述: 
递归创立生龙活虎棵二叉树,按先序输入二叉树中结点的成分的值,“#”号表示空树
* 参数:  pBTree–指向BTree结构体的指针的指针
* 重临值:重返OK–表示创设成功
*         重回EWranglerRO福睿斯–表示创制退步
******************************************************************************/
int CreateBinaryTree(BTree **pBTree)
{
 ElemType data;
 
 scanf(“%c”, &data);

//
//
决断值e是不是为二叉树中某些结点的值,重临其所在的层数,再次来到0表示不在树中
int GetLevelByValue(BTree *pBTree, ElemType e)
{
 int leftDepth = 0;
 int rightDepth = 0;
 int level = 0;

  if (e.lchild != NULL)   // 若存在左孩子,则左孩子入队
  {
   EnQueue(&queue, *e.lchild);
  }

#ifndef QUEUE_H
#define QUEUE_H

//
// 构造四个空的行列
int InitializeQueue(Queue *pQueue);

//
// 出栈
void Pop(Stack *s, StackElemType *e)
{
 if (s->top == s->base) // 固然栈为空栈
 {
  return;
 }

 while (!IsQueueEmpty(queue))
 {
  DeQueue(&queue, &e);

 fclose(stdin);

 if (data == ‘#’)
 {
  *pBTree = NULL;

[cpp] 
队列头文件: 
#include <stdio.h>  
 
#include “BinaryTree.h”  
 
//  
// 队列头文件:Queue.h  
 
#ifndef QUEUE_H  
#define QUEUE_H  
 
//  
// 队列最大因素个数  
#define MAX_QUEUE_SIZE 10  
 
typedef BTree QueueElemType; 
 
//  
// 队列结构体  
typedef struct tagQueue 

    BTree *base; 
    int front;      //
头指针提示器,若队列不空,则指向队列中队头成分  
    int rear;       //
尾指针提示吕,若队列不空,则指向队列队尾的下叁个任务  
}Queue; 
 
//  
// 构造三个空的行列  
int InitializeQueue(Queue *pQueue); 
 
//  
// 判定队列是还是不是为空  
int IsQueueEmpty(Queue queue); 
 
//  
// 推断队列是不是为满  
int IsQueueFull(Queue queue); 
 
//  
// 入队  
int EnQueue(Queue *pQueue, QueueElemType e); 
 
//  
// 退队  
int DeQueue(Queue *pQueue, QueueElemType *e); 
#endif 

 if (CreateBinaryTree(&tree) == OK)  // 缔造二叉树
 {
  printf(“二叉树创立成功!n”);
 }

//
// 入栈
void Push(Stack *s, StackElemType e)
{
 StackElemType *tmp;
 if (s->top – s->base >= s->stackSize) // 栈已经满
 {
  tmp = (StackElemType *)realloc(s->base, (STACK_SIZE_INCREMENT +
s->stackSize)
                                        * sizeof(StackElemType));
  if (!tmp)
  {
   exit(OVELX570FLOW); // 重新分配失利则脱离
  }

 

//
// 二叉树的头文件:BinaryTree.h

 return OK;
}

 *(s->top) = e;
 s->top++;
}

 while (p || !IsStackEmpty(s))
 {
  while (p)
  {
   printf(“%c”, p->data); // 访谈根结点
   Push(&s, *p);           // 根结点指针入栈
   p = p->lchild;          // 一贯向左走到底
  }

 if (pBTree != NULL)
 {
  leftDepth = GetDepth(pBTree->lchild);  // 获取左子树的纵深
  rightDepth = GetDepth(pBTree->rchild); // 获取右子树的吃水
  distance = leftDepth > rightDepth ? leftDepth – rightDepth :
rightDepth – leftDepth;

 printf(“n后序遍历(#意味着空子树):n”);
 PostOrderTraverse(tree);

//
// 获取度为1的结点的个数
int GetCountOfOneDegree(BTree *pBTree)
{
 int count = 0;

/*****************************************************************************
* 方法名:LevelOrderTraverse
* 描述:  层序遍历二叉树
* 参数:  pBTree–指向BTree结构体的指针
******************************************************************************/
void LevelOrderTraverse(BTree *pBTree)
{
 Queue queue;         // 队列变量
 QueueElemType e;     // 队列成分指针变量

 s->top = s->base;
 s->stackSize = STACK_INIT_SIZE;

 // 申请空间战败,则脱离程序
 if (pQueue->base == NULL)
 {
  exit(OVERFLOW);
 }

//
// 顺序栈的兑现文件:Stack.c

//
// 循环队列的贯彻文件:Queue.c

 printf(“n该二叉树是或不是为平衡二叉树?n”);
 if (IsBalanceBinaryTree(tree))
 {
  printf(“Yes!n”);
 }
 else
 {
  printf(“No!n”);
 }

/*****************************************************************************
* 方法名:PostOrderTraverse
* 描述:  后序遍历二叉树
* 参数:  pBTree–指向BTree结构体的指针
******************************************************************************/
void PostOrderTraverse(BTree *pBTree)
{
 if (pBTree)
 {
  PostOrderTraverse(pBTree->lchild);   // 后序遍历左子树
  PostOrderTraverse(pBTree->rchild);   // 后序遍历右子树
    printf(“%c”, pBTree->data); // 后序访问根结点
 }
}

#include “BinaryTree.h”
#include “Queue.h”
#include “Stack.h”

#include “BinaryTree.h”
//
// 栈的头文件宣称部分:Stack.h

 return count;
}
//
// 获取二叉树的结点的总和
int GetNodesCount(BTree *pBTree)
{
 int count = 0;

 printf(“n中序遍历(#意味着空子树):n”);
 InOrderTraverse(tree);

//
// 剖断后生可畏棵二叉树是或不是为平衡二叉树
// 平衡二叉树的定义:
假若放肆节点的左右子树的吃水相差不超越1,那那棵树正是平衡二叉树
//
算法思路:递归决断每一个节点的左右子树的纵深是还是不是离开大于1,假使过量1,表明该二叉树不
//           是平衡二叉树,不然继续递归剖断
int IsBalanceBinaryTree(BTree *pBTree)
{
 int leftDepth = 0;
 int rightDepth = 0;
 int distance = 0;

 p = &tree;

//
// 获取叶子结点的个数
int GetLeafCount(BTree *pBTree)
{
 int count = 0;

#define OK 1
#define ERROR 0
#define OVERFLOW -1

//
// 出栈
void Pop(Stack *s, StackElemType *e);

#endif
[cpp]
二叉树完毕公文及测量检验: 
#include <stdio.h>  
#include <stdlib.h>  
 
#include “BinaryTree.h”  
#include “Queue.h”  
#include “Stack.h”  
 
/*****************************************************************************
* 方法名:CreateBinaryTree
* 描述: 
递归创设后生可畏棵二叉树,按先序输入二叉树中结点的因素的值,“#”号表示空树
* 参数:  pBTree–指向BTree结构体的指针的指针
* 再次来到值:再次来到OK–表示成立成功
*         再次回到ETiguanRO凯雷德–表示创设失败
******************************************************************************/ 
int CreateBinaryTree(BTree **pBTree) 

    ElemType data; 
     
    scanf(“%c”, &data); 
 
    if (data == ‘#’) 
    { 
        *pBTree = NULL; 
 
        return OK; 
    } 
    else  
    { 
        if (((*pBTree) = (BTree *)malloc(sizeof(BTree))) == NULL) 
        { 
            exit(OVERFLOW); 
        } 
 
        (*pBTree)->data = data; 
        CreateBinaryTree(&(*pBTree)->lchild); // 创立左子树  
        CreateBinaryTree(&(*pBTree)->rchild); // 创制右子树  
    } 
 
    return OK; 

 
/*****************************************************************************
* 方法名:PreOrderTraverse
* 描述:  先序遍历二叉树
* 参数:  pBTree–指向BTree结构体的指针
******************************************************************************/ 
void PreOrderTraverse(BTree *pBTree) 

    if (pBTree) 
    { 
        printf(“%c”, pBTree->data);       // 先序访问根结点  
 
        PreOrderTraverse(pBTree->lchild); // 先序遍历左子树  
        PreOrderTraverse(pBTree->rchild); // 先序遍历右子树  
    } 

 
/*****************************************************************************
* 方法名:InOrderTraverse
* 描述:  中序遍历二叉树
* 参数:  pBTree–指向BTree结构体的指针
******************************************************************************/ 
void InOrderTraverse(BTree *pBTree) 

    if (pBTree) 
    { 
        InOrderTraverse(pBTree->lchild); // 中序遍历左子树  
        printf(“%c”, pBTree->data);       // 中序访问根结点  
        InOrderTraverse(pBTree->rchild); // 中序遍历右子树  
    } 

 
/*****************************************************************************
* 方法名:PostOrderTraverse
* 描述:  后序遍历二叉树
* 参数:  pBTree–指向BTree结构体的指针
******************************************************************************/ 
void PostOrderTraverse(BTree *pBTree) 

    if (pBTree) 
    { 
        PostOrderTraverse(pBTree->lchild);   // 后序遍历左子树  
        PostOrderTraverse(pBTree->rchild);   // 后序遍历右子树  
                printf(“%c”, pBTree->data); // 后序访谈根结点  
    } 

 
/*****************************************************************************
* 方法名:LevelOrderTraverse
* 描述:  层序遍历二叉树
* 参数:  pBTree–指向BTree结构体的指针
******************************************************************************/ 
void LevelOrderTraverse(BTree *pBTree) 

    Queue queue;         // 队列变量  
    QueueElemType e;     // 队列成分指针变量  
 
    InitializeQueue(&queue); // 开首化队列  
 
    if (pBTree != NULL) 
    { 
        EnQueue(&queue, *pBTree); // 将根结点指针入队  
    } 
 
    while (!IsQueueEmpty(queue)) 
    { 
        DeQueue(&queue, &e); 
 
        printf(“%c”, e.data); 
 
        if (e.lchild != NULL)   // 若存在左孩子,则左孩子入队  
        { 
            EnQueue(&queue, *e.lchild); 
        } 
 
        if (e.rchild != NULL)   // 若存在右孩子,则右孩子入队  
        { 
            EnQueue(&queue, *e.rchild); 
        } 
    } 

 
/*****************************************************************************
* 方法名:GetDepth
* 描述:  获取树的深度
* 参数:  pBTree–指向BTree结构体的指针
* 重返值:树的吃水
******************************************************************************/ 
int GetDepth(BTree *pBTree) 

    int depth = 0; 
    int leftDepth = 0; 
    int rightDepth = 0; 
 
    if (pBTree) 
    { 
        leftDepth = GetDepth(pBTree->lchild);  //
获取左子树的纵深  
        rightDepth = GetDepth(pBTree->rchild); //
获取右子树的吃水  
 
        depth = leftDepth > rightDepth ? leftDepth + 1: rightDepth +
1; 
    } 
 
    return depth; 

 
/*****************************************************************************
* 方法名:IsLeaf
* 描述:  推断该结点是或不是为叶子结点
* 参数:  node–结点
* 再次来到值:1–代表叶子结点,0–代表非叶子结点
******************************************************************************/ 
int IsLeaf(BTree node) 

    if (node.lchild == NULL && node.rchild == NULL) 
    { 
        return 1; 
    } 
 
    return 0; 

 
/*****************************************************************************
* 方法名:TraverseLeafNodes
* 描述:  遍历全部的卡片结点
* 参数:  pBTree–指向BTree结构体的指针
******************************************************************************/ 
void TraverseLeafNodes(BTree *pBTree) 

    if (pBTree != NULL) 
    { 
        if (1 == IsLeaf(*pBTree)) 
        { 
            printf(“%c”, pBTree->data); 
        } 
        else 
        { 
            TraverseLeafNodes(pBTree->lchild); 
            TraverseLeafNodes(pBTree->rchild); 
        }    
    } 

 
//  
// 剖断风华正茂棵二叉树是不是为平衡二叉树  
// 平衡二叉树的定义:
假诺放肆节点的左右子树的深浅相差不超过1,那那棵树正是平衡二叉树  
//
算法思路:递归推断每种节点的左右子树的深度是或不是离开大于1,倘若过量1,表明该二叉树不  
//           是平衡二叉树,不然继续递归决断  
int IsBalanceBinaryTree(BTree *pBTree) 

    int leftDepth = 0; 
    int rightDepth = 0; 
    int distance = 0;  
 
    if (pBTree != NULL) 
    { 
        leftDepth = GetDepth(pBTree->lchild);  //
获取左子树的纵深  
        rightDepth = GetDepth(pBTree->rchild); //
获取右子树的吃水  
        distance = leftDepth > rightDepth ? leftDepth – rightDepth :
rightDepth – leftDepth; 
 
        return distance > 1 ? 0 :
IsBalanceBinaryTree(pBTree->lchild) &&
IsBalanceBinaryTree(pBTree->rchild); 
    } 

 
//  
// 获取叶子结点的个数  
int GetLeafCount(BTree *pBTree) 

    int count = 0; 
 
    if (pBTree != NULL) 
    { 
        if (IsLeaf(*pBTree)) 
        { 
            count++; 
        } 
        else 
        { 
            count = GetLeafCount(pBTree->lchild) +
GetLeafCount(pBTree->rchild); 
        } 
    } 
 
    return count; 

 
//  
// 获取度为1的结点的个数  
int GetCountOfOneDegree(BTree *pBTree) 

    int count = 0; 
 
    if (pBTree != NULL) 
    { 
        if ((pBTree->lchild != NULL && pBTree->rchild == NULL) ||
(pBTree->lchild == NULL && pBTree->rchild != NULL)) 
        { 
            count++; 
        } 
 
        count += GetCountOfOneDegree(pBTree->lchild) +
GetCountOfOneDegree(pBTree->rchild); 
    } 
 
    return count; 

 
//  
// 获取度为2的结点的个数  
int GetCountOfTwoDegree(BTree *pBTree) 

    int count = 0; 
 
    if (pBTree != NULL) 
    { 
        if (pBTree->lchild != NULL && pBTree->rchild != NULL) 
        { 
            count++; 
        } 
 
        count += GetCountOfTwoDegree(pBTree->lchild) +
GetCountOfTwoDegree(pBTree->rchild); 
    } 
 
    return count; 

//  
// 获取二叉树的结点的总量  
int GetNodesCount(BTree *pBTree) 

    int count = 0; 
 
    if (pBTree != NULL) 
    { 
        count++; 
 
        count += GetNodesCount(pBTree->lchild) +
GetNodesCount(pBTree->rchild); 
    } 
 
    return count; 

 
//  
// 调换左右子树  
void SwapLeftRightSubtree(BTree **pBTree) 

    BTree *tmp = NULL; 
 
    if (*pBTree != NULL) 
    { 
        // 交换当前结点的左右子树  
        tmp = (*pBTree)->lchild; 
        (*pBTree)->lchild = (*pBTree)->rchild; 
        (*pBTree)->rchild = tmp; 
 
        SwapLeftRightSubtree(&(*pBTree)->lchild); 
        SwapLeftRightSubtree(&(*pBTree)->rchild); 
    } 

 
//  
//
决断值e是还是不是为二叉树中有个别结点的值,再次回到其所在的层数,再次来到0表示不在树中  
int GetLevelByValue(BTree *pBTree, ElemType e) 

    int leftDepth = 0; 
    int rightDepth = 0; 
    int level = 0; 
 
    if (pBTree->data ==
e)//这里的1是对立于以pBTree为根节点的层数值。  
    { 
        return 1; 
    } 
 
    if (pBTree->lchild !=
NULL)//leftDepth所表示的层数是相对以pBTree的左节点为根的树的层数  
    { 
        leftDepth = GetLevelByValue(pBTree->lchild, e); 
    } 
 
    if (pBTree->rchild != NULL) 
    { 
        //
rightDepth所代表的层数是相对以pBTree的右节点为根的树的层数  
        rightDepth = GetLevelByValue(pBTree->rchild, e); 
    } 
 
    //  
    // 查找结果依然在左子树找到,要么在右子树中找到,要么找不到  
    if (leftDepth > 0 && rightDepth == 0) // 在左子树中找到  
    { 
        level = leftDepth; 
    } 
    else if (leftDepth == 0 && rightDepth > 0) // 在右子树中找到  
    { 
        level = rightDepth; 
    } 
 
    if (leftDepth != 0 || rightDepth != 0) // 判定是或不是找到该结点  
    { 
        level++; 
    } 
 
    return level; 

 
//  
// 非递归中序遍历  
void NoneRecursionInOrder(BTree tree) 

    Stack s; 
    StackElemType *p = NULL, *q; 
 
    q = (StackElemType *)malloc(sizeof(StackElemType)); //
用于指向退栈成分之处  
    InitStack(&s); 
    p = &tree; 
 
    while (p || !IsStackEmpty(s)) 
    { 
        if (p) 
        { 
            Push(&s, *p);  
            p = p->lchild; 
        } 
        else 
        { 
            Pop(&s, q); 
            printf(“%c”, q->data); 
            p = q->rchild; 
        } 
    } 
 
    free(q); 

 
//  
// 非递归前序遍历  
void NoneRecursionPreOrder(BTree tree) 

    Stack s; 
    StackElemType *p = NULL, *q; 
 
    q = (StackElemType *)malloc(sizeof(StackElemType)); //
用于指向退栈成分的地址  
    InitStack(&s); 
    p = &tree; 
 
    while (p || !IsStackEmpty(s)) 
    { 
        while (p) 
        { 
            printf(“%c”, p->data); // 访谈根结点  
            Push(&s, *p);           // 根结点指针入栈  
            p = p->lchild;          // 从来向左走到底  
        } 
 
        Pop(&s, q); 
        p = q->rchild;   // 向右走一步  
    } 
 
    free(q); 

 
//  
// 非递归后序遍历  
void NoneRecursionPostOrder(BTree tree) 

    StackElemType *stack[STACK_INIT_SIZE], *p; 
    int tag[STACK_INIT_SIZE], //
值独有0和1,当中0表示该结点的左子树已经访谈  
                              // 值为1代表该结点的右子树已经访谈  
        top = 0; // 栈顶提醒器  
 
    p = &tree; 
 
    while (p || top != 0)// 树未遍历完毕只怕栈不空  
    { 
        while (p) 
        { 
            top++; 
            stack[top] = p;  
            tag[top] = 0; 
            p = p->lchild; // 从根伊始向左走到底  
        } 
 
        if (top > 0) // 栈不空  
        { 
            if (tag[top] == 1)//
表示曾经访谈该结点的右子树,并再次来到   
            { 
                p = stack[top–]; // 退栈  
                printf(“%c”, p->data); 
 
                p = NULL; // 后一次步入循环时,就不会再遍历左子树  
            } 
            else // 表示刚从该结点的左子树重临,以往起来遍历右子树  
            { 
                p = stack[top]; // 取栈顶成分  
                if (top > 0) // 栈不空  
                { 
                    p = p->rchild; 
                    tag[top] = 1; // 标记该结点的右子树已经访谈  
                } 
            } 
        } 
    } 

 
int main() 

    BTree *tree = NULL; 
 
    printf(“按先序输入二叉树结点成分的值,输入#代表空树:n”); 
 
    freopen(“test.txt”, “r”, stdin); 
 
    if (CreateBinaryTree(&tree) == OK)  // 创制二叉树  
    { 
        printf(“二叉树创立成功!n”); 
    } 
 
    printf(“先序遍历(#意味着空子树):n”); 
    PreOrderTraverse(tree); 
 
    printf(“n中序遍历(#表示空子树):n”); 
    InOrderTraverse(tree); 
 
    printf(“n后序遍历(#代表空子树):n”); 
    PostOrderTraverse(tree); 
 
    printf(“n树的吃水为:%dn”, GetDepth(tree)); 
 
    printf(“n层序遍历:n”); 
    LevelOrderTraverse(tree); 
 
    printf(“n遍历叶子结点:n”); 
    TraverseLeafNodes(tree); 
 
    printf(“n叶子结点的个数:%dn”, GetLeafCount(tree)); 
    printf(“度为1的结点的个数:%dn”, GetCountOfOneDegree(tree)); 
    printf(“度为2的结点的个数:%dn”, GetCountOfTwoDegree(tree)); 
    printf(“n二叉树的结点总的数量为:%dn”, GetNodesCount(tree)); 
 
    printf(“n该二叉树是或不是为平衡二叉树?n”); 
    if (IsBalanceBinaryTree(tree)) 
    { 
        printf(“Yes!n”); 
    } 
    else 
    { 
        printf(“No!n”); 
    } 
 
 
    printf(“n结点值为A的结点在第%d层n”, GetLevelByValue(tree,
‘A’)); 
    printf(“n结点值为B的结点在第%d层n”, GetLevelByValue(tree,
‘B’)); 
    printf(“n结点值为C的结点在第%d层n”, GetLevelByValue(tree,
‘C’)); 
    printf(“n结点值为D的结点在第%d层n”, GetLevelByValue(tree,
‘D’)); 
    printf(“n结点值为E的结点在第%d层n”, GetLevelByValue(tree,
‘E’)); 
    printf(“n结点值为F的结点在第%d层n”, GetLevelByValue(tree,
‘F’)); 
    printf(“n结点值为G的结点在第%d层n”, GetLevelByValue(tree,
‘G’)); 
    printf(“n结点值为M的结点在第%d层n”, GetLevelByValue(tree,
‘M’)); 
 
    printf(“n非递归中序遍历:n”); 
    NoneRecursionInOrder(*tree); 
 
    printf(“n非递归前序遍历:n”); 
    NoneRecursionPreOrder(*tree); 
 
    printf(“n非递归后序遍历:n”); 
    NoneRecursionPostOrder(*tree); 
 
   
printf(“n=======================================================n”); 
 
    printf(“下边执行交流左右子树操作:n”); 
    SwapLeftRightSubtree(&tree); 
 
    printf(“先序遍历(#意味着空子树):n”); 
    PreOrderTraverse(tree); 
 
    printf(“n中序遍历(#意味着空子树):n”); 
    InOrderTraverse(tree); 
 
    printf(“n后序遍历(#表示空子树):n”); 
    PostOrderTraverse(tree); 
 
    printf(“n树的吃水为:%dn”, GetDepth(tree)); 
 
    printf(“n层序遍历:n”); 
    LevelOrderTraverse(tree); 
 
    printf(“n遍历叶子结点:n”); 
    TraverseLeafNodes(tree); 
 
     
 
    fclose(stdin); 
 
    printf(“n”); 
    return 0; 

发表评论

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