威尼斯人线上娱乐

非递归后序遍历贰叉树版本二,中序遍历

16 4月 , 2019  

思路:

2叉树的遍历

二叉树的操作有无数种,当中最常用的是2叉树的遍历。二叉树的遍历是指遵照某种顺序访问二叉树中的每一种结点,使得各样结点都被仅且访问三回。
因而二遍完整的遍历,可使二叉树中的结点由原本的非线性种类变为某种意义的线性体系。根据根节点访问的种种不一致,遍历的各样分为前序遍历,中序遍历,后序遍历。

树:层次关系
Tree :n个节点构成的星星点点集合;
n=0时;称为空树;
对于非空树,具有特质有:

近些年看了一下大学的数据结构,学到了以前没学到的东西看到了2叉树那1块,认为2叉树是个很重要的事物,就看了一晃底层是怎么落到实处的,即使能看懂书上用c语言写的伪代码,然而不可能运维,身为三个Java程序员,既然人家能用其余的语言能完成,本身也去试着写了须臾间。

标记一个结点的左右子树是不是曾经被访问过,叶子节点也进行标识

二叉树的遍历方法与算法完成

威尼斯人线上娱乐 1

二叉树

  • 树中有1个根的异样节点,用r解释;
  • 非递归后序遍历贰叉树版本二,中序遍历。子树;
    树与非树?
  • 子树是不想交的;
  • 除此而外根节点外,各类结点点有且仅有多少个父节点;
  • 1棵N个结点的树有N-1条边;

先是付诸2叉树的节点代码

public class BinTree {

  public BinTree(String name) {
    this.name = name;
  }

  public BinTree(int name) {
    this.name = name + "";
  }

  BinTree left;
  BinTree right;
  public String name;



  public void setLeft(BinTree left) {
    this.left = left;
  }

  public void setRight(BinTree right) {
    this.right = right;
  }

  public void setName(String name) {
    this.name = name;
  }
}

拓展:

先序遍历

先序遍历的递归定义:如果贰叉树为空,则遍历的结果为空,否则:

  • 走访根节点
  • 先序遍历左子树
  • 先序遍历右子树

以上海体育场面作为遍历对象的话:

  • 先走访根节点A
  • 先序遍历根节点的左子树,然后继续根据先序遍历的壹壹

  • 先拜访结点B

  • 访问结点D
    • 左子树为空
    • 访问结点E
  • 走访结点f
    • 做客结点G
    • 右子树为空
  • 做客右子树结点C

末段赢得的遍历类别为: ABDEfGC

主导术语

一、 结点的度 结点的子树个数
二、树的度:树的富有结点最大的度数
3、叶结点:度为1的结点;
四、父节点:有子树的结点是其子树的根节点的父节点
5、子节点;
6、兄弟结点:同一父节点的各结点是互相的弟兄结点;
⑦、路线和路径长度;
8、祖先结点;
玖、子孙节点;
1一、结点的层系;
1二、树的吃水;

贯彻方式

威尼斯人线上娱乐 2

image.png

二叉树:度为2;
破例2叉树

  • 斜2叉树
  • 圆满二叉树/满二叉树
  • 一同2叉树(不完整)

下一场模拟一个栈的代码,会在前面非递归的时候用到

出于只是去遍历全体节点,未有思考品质上的主题素材,只是让我们探听思路,底层用ArrayList去贯彻栈成效

/*
模拟栈的功能
*/
public class Stack<E> {
  public List<E> mBinTrees = new ArrayList<>();

  /**
   * 把节点放入栈
   * 
   * @param binTree
   */
  public void push(E binTree) {
    mBinTrees.add(binTree);
  }

  /**
   * 从栈顶pop出一个节点并得到这个节点
   * 
   * @return
   */
  public E pop() {
    if (mBinTrees != null) {

      return mBinTrees.remove(mBinTrees.size() - 1);
    }

    return null;
  }

  /**
   * 判断栈里是否还有数据
   * 
   * @return
   */
  public boolean isEmpty() {
    return mBinTrees.size() == 0;
  }

  /**
   * 查看当前栈顶的元素
   * 
   * @return
   */
  public E top() {
    return mBinTrees.get(mBinTrees.size() - 1);
  }
}

遍历进程中读者会发现,某壹随时,从栈底到栈顶的成分刚好构成当前访问节点的到根节点的路线。利用那1特点可以兑现五个算法:(一)根到某节点的门径(二)四个节点的如今公共祖先

二叉树先序遍历递归算法的落到实处

void Preorder(BinTree t)
{
    if(t!=NULL)
    {
        printf("%c ",t->data);
        preOrder(t->leftChild);
        preOrder(t->rightChild);
    }
}

重大性质

二叉树第i层最大结点 2^(n-一)
纵深为k的二叉树最大结点总的数量为2^n-一
非空二叉树 n0为叶节点的个数 n2为度为二的非叶节点个数 满意n0=n2+壹;

常用的遍历方法:
先序–根,左子树,右子树
中序–左子树,根,右子树
后续–左子树,右子树,根
层次遍历–从上到下,从左到右

(一)先序遍历

先看下先序遍历的流程图,接下去的代码也会依据此图是遍历

威尼斯人线上娱乐 3

先序遍历.JPG

先序遍历顾名思义,就是先会遍历根节点->左孩子->右孩子。遍历是从根节点初步,蒙受每一种节点时,其遍历进程为:

  • 访问根节点;
  • 先序遍历其左子树;
  • 先序遍历其右子树;

typeDef struct{

2叉树先序遍历非递归算法的得以实现

因为实行的依次为从根节点初始,沿着左子树一贯找下去,找到底,然后回来到近年来找过的结点的右子树。所以须求记录走访过的根节点,便于往回走,由于是先让根节点1个个记录起来,然后在返回的时候找如今刚找过的根节点,所以符合栈的特性(先进先出),用顺序栈存款和储蓄就能够。

#define MAXSIZE 100
void Preorder2(BinTree t)
{
    if(t==NULL)
        return ;
    BinTree stack[MAXSIZE],p;
    int top = 0;
    p = t;
    //找到底,且栈中没有可以回去的结点时,遍历结束
    while(p!=NULL || top>0)
    {
        //找左子树,找到头为止
        while(p!=NULL)
        {
            printf("%c ",p->data);  //访问结点的指针域
            if(top<MAXSIZE-1)
            {
                stack[top] = p;
                p++;
            }
            else
            {
                printf("error\n");
                return ;
            }
        }
        //找右子树
        --top;
        p = stack[top];
        p = p->rightChild;
    }
}

二叉树的蕴藏结构

先序遍历递归完结代码:

/**
   * 前序遍历 递归
   */
  public static void preOrderTraversal(BinTree binTree) {
    if (binTree != null) {
      System.out.print(binTree.name);
      preOrderTraversal(binTree.left);
      preOrderTraversal(binTree.right);
    }
  }
BiTree t;
int tag;

按先序连串建立2叉树

建立2叉树时的输入的树为把树的每1个叶子结点的孩子结点填充为’#’。

void CreatBintree(BinTree *root)
{
    char ch;
    if((ch=getchar())=='#') //从键盘上输入二叉树结点数值到#截止
        *root = NULL
    else
    {
        *root = (BinNode*)malloc(sizeof(BinNode));
        (*root)->data = ch;
        CreatBintree(&((*root)->leftChild));
        CreatBintree(&((*root)->rightChild));
    }
}

顺序存款和储蓄结构

-完全二叉树
:从上到下、从左到右顺序存款和储蓄n个节点的完全贰叉树的节点父亲和儿子关系。

  • 父根节点 父节点[威尼斯人线上娱乐,i/2]
  • 左孩子节点 贰i
  • 右孩子节点二i+一
    相似二叉树也足以运用这种结构,但会招致空间浪费。

先序遍历非递归达成代码

/**
   * 前序遍历 非递归
   * 输出结果 ABDFECGHI
   */
  public static void preOrderTraversalNoDIGUI(BinTree binTree) {
    Stack<BinTree> stack = new Stack();
    BinTree t = binTree;
    while (t != null || !stack.isEmpty()) {
      while (t != null) {
        System.out.print(t.name);
        stack.push(t);
        t = t.left;
      }
      if (!stack.isEmpty()) {
        t = stack.pop();
        t = t.right;
      }
    }
  }

出口结果

ABDFECGHI

}Stack

中序遍历

中序遍历的递归定义:要是二叉树为空,则遍历的结果为空,不然:

  • 中序遍历根节点的左子树
  • 访问根节点
  • 中序遍历根节点的右子树

有了先序遍历的阅历,以上航海用体育地方作为遍历对象的话:
末段获得的遍历体系为:DEBGfAC

链表存款和储蓄

template <typename DataType>
struct TreeNode
{
    DataType data; //存储的数据
    TreeNode *left; //指向左子树根节点
    TreeNode *right; //指向右子树根节点
    //TreeNode * parent; //指向父节点,如果需要的话
    TreeNode(DataType inData): data(inData), right(nullptr), left(nullptr) {}
};

威尼斯人线上娱乐 4

image.png

(2)中序遍历

威尼斯人线上娱乐 5

中序遍历.JPG

中序遍历是指对树中任壹节点的访问是在遍历完其左子树后进行的,访问此结点后再对其右子树遍历。遍历从根节点开首,境遇每一个结点时,其遍历进程为:

  • 中序遍历其左子树;
  • 走访根节点;
  • 中序遍历其右子树

void f(BiTree bt, ElemType x){

贰叉树中序遍历递归算法达成

void Inorder(BinTree t)
{
    if(t!=NULL)
    {
        InOrder(t->leftChild);
        printf("%c ",t->data);
        InOrder(t->rightChild);
    }
}

遍历

//遍历
//先序遍历
template <typename DataType>
void Traverse(TreeNode<DataType> * inNode){
    if (inNode == nullptr){
    return;
    }
    //cout<<inNode->data<<endl;//如果在这里访问即为先序访问
    Traverse(inNode->left);
    //cout<<inNode->data<<endl;//如果在这里访问即为中序访问
    Traverse(inNode->right);
    //cout<<inNode->data<<endl;//如果在这里访问即为后序访问
    return;
}

中序遍历递归完成代码:

  /**
   * 中序遍历 递归
   * DBEFAGHCI
   */
  public static void inOrderTraversal(BinTree binTree) {
    if (binTree != null) {
      inOrderTraversal(binTree.left);
      System.out.print(binTree.name);
      inOrderTraversal(binTree.right);
    }
  }
Stack s[];
top = 0;
while(bt!=null||top>0)
    while(bt!=null){
        s[++top].t = bt;
        s[top].tag = 0;
        bt=bt->lchild;
    }
//注意这里是while   不是if
while(top!=0&&s[top].tag==1)
    print(visit(s[top--]));

if(top!=0){
    s[top].tag = 1;
    bt = s[top].t->rchild;
}

2叉树中序遍历非递归算法实现

对于中序遍历与先序遍历差别的是造访的一1差异,但一样要用栈来记录

#define MAXSIZE 100;
void Inorder2(BinTree t)
{
    if(t==NULL)
        return ;
    BinTree stack[MAXSIZE],p;
    int top = 0;
    p = t;
    while(p!=NULL || top>0)
    {
        //先遍历到底再访问结点
        while(p!=NULL)
        {
            if(top<MAXSIZE-1)
            {
                stack[top] = p;
                p++;
            }
            else
            {
                printf("error\n");
                return ;
            }
        }
        top--;
        p = stack[top];
        printf("%c ",p->data);  //访问结点的指针域
        p = p->rightChild;
    }
}

2叉树的非递归算法

先序遍历的非递归:使用宾馆

template <typename DataType>
void NonRecursiveTraverse(TreeNode<DataType> * inNode){
    stack<TreeNode<DataType>*> nodeStack;
    TreeNode<DataType> *cycleNode = inNode;
    while(inNode != nullptr||!nodeStack.empty()){
        //不断访问某一节点的左子节点并压栈知道最左子节点
        while(cycleNode != nullptr){
            //遇到节点先输出
            cout<<cycleNode->data<<endl;
            nodeStack.push(cycleNode);
            cycleNode = cycleNode->left;
        }
        //此时所有的左子树都压入栈中
        //弹出最后一个节点 访问该节点的右子节点并作为下一步作为下一轮遍历节点
        if(!inNode.empty()){
            cycleNode = nodeStack.top();
            cycleNode = cycleNode->right;
            nodeStack.pop();
        }
    }
}

中序遍历:先走访左子节点,在拜访根节点,再拜访右子节点。

template <typename DataType>
void NonRecursiveTraverse(TreeNode<DataType> * inNode){
    stack<TreeNode<DataType>*> nodeStack;
    TreeNode<DataType> *cycleNode = inNode;
    while(inNode != nullptr||!nodeStack.empty()){
        //不断访问某一节点的左子节点并压栈知道最左子节点
        while(cycleNode != nullptr){   
            nodeStack.push(cycleNode);
            cycleNode = cycleNode->left;
        }
        //此时所有的左子树都压入栈中
        //弹出最后一个节点 访问该节点的右子节点并作为下一步作为下一轮遍历节点
        if(!inNode.empty()){
            cycleNode = nodeStack.top();
            //在此处访问即为中序遍历,时机为压入右子节点之前
        //cout << cycleNode->data << endl; 
            cycleNode = cycleNode->right;
            nodeStack.pop();
        }
    }
}

出于扶持压栈,大家并从未将null压入栈中,尽管发现左子节点为null则在保存右子节点地址后平素弹出该节点,并动用右子节点作为下壹论访问开首节点,要是右子节点为null则表示该节点左右子树均遍历达成,则接二连三弹出直至出现第1个右子树不为空的节点,重复递归。

压栈图中,在前序遍历时,只要境遇节点(压栈进度)就直接出口就能够保障根节点首先被输出,而中序遍历由于须求在左子树输出实现后技艺出口,由此若是保证在压栈再次回到时(出栈时)且准备遍历右子树时输出就可以。

后序遍历 非递归达成

template <typename DataType>
void NonRecursiveTraverse(TreeNode<DataType> *inNode){
        stack<TreeNode<DataType> *>nodeStack;
        TreeNode<DataType> *cycleNode = inNode;
        TreeNode<DataType> *hasNode = nullptr;
        while(inNode != nullptr || !nodeStack.empty()){
            //不断访问某一节点的左子节点并压栈直到最左子节点
            while(cycleNode != nullptr){
                nodeStack.push(cycleNode);
                cycleNode = cycleNode->left;
            }
            //此时所有的子节点都已经压入栈中。
            //弹出最后一个节点,访问该节点的右子节点并作为下一轮遍历根节点
            if(!nodeStack.empty()){
                cycleNode = nodeStack.top();
                //此时判别是否已经加载右子树
                //如果为空则和中序遍历一样
                if(cycleNode->right == nullptr){
                    hascycle = cycleNode;
                    cout<< cycleNode->data<<endl;
                    nodeStack.pop();
                }
                else if(hascycle == cycleNOde->right){
                    hascycle = cycleNode;
                    cout<<cycleNode->data<<endl;
                    nodeStack.pop();
                }
                cycleNode = nullptr;
                if(!nodeStack.empty() && ndoeStack.top->right!=nullptr)) {
                    cycleNode = nodeStack.top()->right;
                }
            }
        }
}

中序遍历非递归达成代码:

  /**
   * 中序遍历 非递归
   * DBEFAGHCI
   */
  public static void inOrderTraversalNODIGUI(BinTree binTree) {
    Stack<BinTree> stack = new Stack();
    BinTree t = binTree;
    while (t != null || !stack.isEmpty()) {
      while (t != null) {
        stack.push(t);
        t = t.left;
      }
      if (!stack.isEmpty()) {
        t = stack.pop();
        System.out.println(t.name);
        t = t.right;
      }
    }
  }

}

后序遍历

后续遍历的递归定义:若二叉树为空,遍历结果为空,不然:

  • 后序遍历根节点的左子树
  • 此起彼伏遍历根节点的右子树
  • 访问根节点

上述图为遍历对象的话
遍历结果的队列为:EDGfBCA

层序遍历

二叉树遍历的骨干难题:2维结构的线性化

  • 从节点访问其左、右外孙子
  • 内需一个储存结构保留临时不访问的结点
  • 存储结构:货仓、队列

队列完毕:遍历从根节点起首,首先将根节点入队,然后初叶实行循环:结点出队,访问该结点,将左右幼子入队

void LevelOrderTraversal ( BinTree BT){
    Queue Q;BinTree T;
    //如果是空树直接返回
    if(!BT)
        return ;
    //创建并初始化队列Q
    Q = CreatQueue(Maxsize);
    AddQ(Q,BT);
    while( !IsEmptyQ(Q)){
        T = DeleteQ(Q);
        cout  <<T->data<<endl;
        if(T->left)   
            AddQ(Q,T->left);
        if(T->right)
            AddQ(Q,T->right)
    }
}

过程

在沿左子树深深时,进入三个结点就将其压人仓库。假若先序遍历,则在入栈以前访问之;
当沿左分支深人不下去时,则赶回,即从酒馆中弹出前边压人的结点;若为中序遍历,则此时访问
该结点,然后从该结点的右子树继续深远;若为后序遍历,则将此结点贰次入栈,然后从该结点的
右子树继续深刻,与日前类同,仍为进入多个结点入栈1个结点,深入不下来再回来,直到第二遍
从栈里弹出该结点,才访问之。
故此,根据上述描述的长河,使用仓库能够一向促成相应的非递归算法。先序和中序算法相
对间果些,而后序遍历因为急需几遍将叁个结点人栈,意况稍复杂些。上面只以中序遍所头份
介绍2叉树遍历的非递归算法。
在按中序遍历2叉树时,遇到一个结点,就把它入栈,并去遍历它的左子树,当左子树遍历结束后,从栈顶弹出这些结点并访问它,然后按其右指针再去中序遍历该结点的右子树。

您大概感兴趣的

贰叉树后序遍历递归算法达成

void Posorder(BinTree t)
{
    if(t!=NULL)
    {
        Posorder(t->leftChild);
        Posorder(t->rightChild);
        printf("%c ",t->data);
    }
}

倘诺有八个遍历连串明确二叉树

无法不要有中序遍历
一经已知先序和中序;

  1. 依照先序遍历类别首个节点明确根节点;
  2. 杜绝根节点在中序遍历系列中分割出左右五个子类别
  3. 对左子树和右子树分别递归分为左子树和右子树

(3)后序遍历

威尼斯人线上娱乐 6

后续遍历.JPG

后序遍历是指对树中任1节点的拜会是在遍历完其左、右子树后进行的。遍历从根节点开首,遭受每种结点时,其遍历进程为:

  • 后序遍历其左子树;
  • 后序遍历其右子树
  • 做客根节点;
  • 非递归先序遍历贰叉树https://www.cnblogs.com/Coeus-P/p/9353186.html
  • 非递归后序遍历2叉树版本二
  • 递归算法–2叉树宽度
  • 递归算法–调换2叉树左右子树
  • 递归算法–二叉树高度
  • 递归算法–二叉树中叶子结点
  • 递归算法–贰叉树中度为2的结点
  • 递归算法–二叉树中度为1的结点
  • 非递归完结斐波那契数列
  • 非递归后序遍历二叉树版本一
  • 层次遍历二叉树
  • 非递归中序遍历二叉树
  • 非递归先序遍历2叉树

二叉树后序遍历非递归算法达成

与前序遍历和中序遍历差别的是您跑完了左子树和右子树技能访问根节点,此时当你遍历完左子树时,你必要回到根节点,可是此时你还无法访问,因为您要先遍历右子树所以您还要根结点再度入栈,然后下次在出栈的时候技术访问,所以那边用2个符号来拍卖

#define MAXSIZE 100
typedef struct
{
    BinTree link;
    int flag;
}stackType;
void Posorder2(BinTree t)
{
    if(t==NULL)
        return ;
    stackType stack[MAXSIZE];
    BinTree p;
    int top = 0;
    while(p!=NULL || top>0)
    {
        if(p!=NULL)
        {
            //结点第一次进栈
            stack[top].link = p;
            stack[top].flag = 0;
            //找结点的左儿子
            p = p->leftChild;
            top++;
        }
        else
        {
            top--;
            p = stack[top].link;
            sign = stack[top].flag;
            if(sign==0)
            {
                //第二次进栈
                stack[top].link = p;
                stack[top].flag = 1;
                top++;
                p = p->rightChild;
            }
            else
            {
                //访问该结点的数据域
                printf("%c ",p->data);
                //找完讲p置为空防止在继续往左找下去
                p = NULL;
            }
        }
    }
}

2叉查找树的概念与贯彻

静态查找:二分查找
动态查找:二叉寻觅树;
也号称二叉排序树,或然2叉查找树;

  • 分空左子树的全部键值小于其根节点的键值。
  • 分空右子树的富有键值大于其根节点的键值。
  • 左右子树都是2叉搜索树。

对于2叉树ADT,一般供给提供以下操作:

  • 清空贰叉查找树:MakeEmpty
  • 招来有个别节点:Find
  • 删除有些节点:DeleteElement
  • 索求最大值:Find马克斯
  • 搜寻最小值:FindMin
  • 布置3个节点:InsertElement
    2叉查找树的平分深度为O(log(N)),可是只要插入元素种类递增只怕递减,二叉查找树将走下坡路成单链表。

后序遍历递归实现代码:

  /**
   * 后续遍历 递归
   * DEFBHGICA
   * 
   * @param tree
   */
  public static void postOrderTraversal(BinTree tree) {
    if (tree != null) {
      postOrderTraversal(tree.left);
      postOrderTraversal(tree.right);
      System.out.print(tree.name);
    }
  }

二叉树的层序遍历

对于先序,中序,后序来讲,他们属于深度遍历,也正是先探到低然后再折回到。对于层序遍历来讲,顾名思义,便是1层壹层的扫过去,所以层序遍历的艺术为先上层在下层,同层之间,从左到遍历过去。从那样的遍历描述能够旁观该遍历为广度遍历,可用队列来完成。
上海体育地方的遍历结果为: ABCDfEG

#define Error 0
#define OK 1
#define MAXSIZE 100
typedef char DataType;
typedef struct node
{
    DataType data;
    struct node* leftChild;
    struct node* rightChild;
}BinNode;
typedef BinNode* BinTree;
typedef BinTree ElemType;
typedef struct
{
    ElemType data[MAXSIZE];
    int front;
    int rear;
}SeQueue;
typedef int Status;

Status InitQueue(SeQueue *q)
{
    q->front = 0;
    q->rear = 0;
    return OK;
}
int EmptyQueue(SeQueue *q)
{
    if(q->rear == q->front)
        return 1;
    else
        return 0;
}
ElemType FrontQueue(SeQueue *q)
{
    if(EmptyQueue(q))
    {
        printf("Empty!\n");
    }
    return q->data[q->front];
}
Status DeQueue(SeQueue *q)
{
    if(EmptyQueue(q))
        return Error;
    q->front++;
    return OK;
}
Status EnQueue(SeQueue *q,ElemType e)
{
    if(q->rear == MAXSIZE)
        return Error;
    q->data[q->rear] = e;
    q->rear++;
    return OK;
}
Status LevelOrder(BinTree bt)
{
    if(bt==NULL)
        return Error;
    SeQueue q;
    InitQueue(&q);
    EnQueue(&q,bt);
    while(!EmptyQueue(&q))
    {
        BinTree tmp = FrontQueue(&q);   //获取队头元素
        printf("%c",tmp->data);
        //同层元素从左到右进行遍历
        if(tmp->leftChild!=NULL)        
            EnQueue(&q,tmp->leftChild);
        if(tmp->rightChild!=NULL)
            EnQueue(&q,tmp->rightChild);
        DeQueue(&q);
    }
    printf("\n");
    return OK;
}

二叉查找树的完毕

2叉树的着力构造定义:

template <typename DataType>
struct Node
{
    DataType data;
    Node *left;
    Node *right;
    Node(DataType inData): data(inData), left(nullptr), right(nullptr) {}
};

template <typename DataType>
class BinarySearchTree
{
public:
    BinarySearchTree(): root(nullptr) {}
    ~BinarySearchTree();
    void MakeEmpty(); //清空二叉查找树
    void MakeEmptyNon(); //非递归清空二叉树
    Node<DataType> * Find(DataType inElement); //查找某个元素
    Node<DataType> * FindNon(DataType inElement); //非递归查找
    void DeleteElement(DataType inElement); //删除一个节点
    Node<DataType> * FindMax(); //查找最大元素
    Node<DataType> * FindMaxNon(); //非递归查找最大元素
    Node<DataType> * FindMin(); //查找最小元素
    Node<DataType> * FindMinNon(); //非递归查找最小元素
    Node<DataType> * InsertElementNon(DataType inElement); //非递归插入一个元素
private:
    void MakeEmptyCore(Node<DataType> *inNode);
    Node<DataType> *FindCore(Node<DataType> *inNode, DataType inElement);
    //删除一个节点
    Node<DataType> * DeleteElementCore(Node<DataType> *inNode, DataType inElement);
    Node<DataType> *FindMaxCore(Node<DataType> *inNode);
    Node<DataType> *FindMinCore(Node<DataType> *inNode);
    Node<DataType> *root;
};

2叉查找树的大旨数据成员为
递归清空宗旨函数:

template <typename DataType>
void BinarySearchTree<DataType>::MakeEmptyCore(Node<DataType> *inNode)
{
    if (inNode == nullptr) {
        return;
    }
    MakeEmptyCore(inNode->left);
    MakeEmptyCore(inNode->right);
    delete inNode;
}

递归清空核心函数

template <typename DataType>
void BinarySearchTree<DataType>::MakeEmptyCore(Node<DataType> *inNode)
{
    if (inNode == nullptr) {
        return;
    }
    MakeEmptyCore(inNode->left);
    MakeEmptyCore(inNode->right);
    delete inNode;
}

递归清空入口函数,调用清台湾空中大学旨函数

template <typename DataType>
void BinarySearchTree<DataType>::MakeEmpty()
{
    MakeEmptyCore(root); root = nullptr;
}

非递归清空函数,采取某种非递归遍历函数思想就能够

template <typename DataType>
void BinarySearchTree<DataType>::MakeEmptyNon()
{
    stack<Node<DataType> *> nodeStack;
    Node<DataType> *cycleIter = root;
    while (cycleIter != nullptr || !nodeStack.empty()) {
        while (cycleIter != nullptr) {
            nodeStack.push(cycleIter);
            cycleIter = cycleIter->left;
        }

        if (!nodeStack.empty()) {
            Node<DataType> * tmp = nodeStack.top();
            cycleIter = tmp->right;
            delete tmp; nodeStack.pop();
        }
    }
    root = nullptr;
}

递归查找有些成分

template <typename DataType>
Node<DataType> *BinarySearchTree<DataType>::FindCore(Node<DataType> *inNode, DataType inElement)
{
    if (inNode == nullptr) {
        return nullptr;
    }
    if (inNode->data == inElement) {
        return inNode;
    }
    else if (inNode->data > inElement){
        return FindCore(inNode->left, inElement);
    }
    else {
        return FindCore(inNode->right, inElement);
    }
    return nullptr;
}

非递归查找

template <typename DataType>
Node<DataType> * BinarySearchTree<DataType>::FindNon(DataType inElement)
{
    Node<DataType> *cycleIter = root;
    while (cycleIter != nullptr) {
        if (cycleIter->data == inElement) {
            return cycleIter;
        }
        else if (cycleIter->data > inElement){
            cycleIter = cycleIter->left;
        }
        else {
            cycleIter = cycleIter->right;
        }
    }
    return nullptr;
}

递归删除节点函数大旨函数

template <typename DataType>
Node<DataType> * BinarySearchTree<DataType>::DeleteElementCore(Node<DataType> *inNode, DataType inElement)
{
    if (inNode == nullptr) {
        return nullptr;
    }
    else if (inNode->data > inElement) {
        inNode->left = DeleteElementCore(inNode->left, inElement);
    }
    else if (inNode->data < inElement) {
        inNode->right = DeleteElementCore(inNode->right, inElement);
    }
    else {
        if (inNode->left != nullptr && inNode->right != nullptr) {
            Node<DataType> *tmp = FindMinCore(inNode->right);
            inNode->data = tmp->data;
            inNode->right = DeleteElementCore(inNode->right, inNode->data);
        }
        else {
            Node<DataType> *tmp = inNode;
            if (inNode->left == nullptr) {
                inNode = inNode->right;
            }
            else {
                inNode = inNode->left;
            }
            delete  tmp;
        }
    }
    return inNode;
}

递归查找最大因素基本函数

template <typename DataType>
Node<DataType> * BinarySearchTree<DataType>::FindMaxCore(Node<DataType> *inNode)
{
    if (inNode == nullptr) {
        return nullptr;
    }
    else if (inNode->right == nullptr) {
        return inNode;
    }
    else {
        return FindMaxCore(inNode->right);
    }
}

递归查找最大因素

template <typename DataType>
Node<DataType> * BinarySearchTree<DataType>::FindMax()
{
    if (root == nullptr) {
        return nullptr;
    }
    return FindMaxCore(root);
}

非递归查找最大因素

template <typename DataType>
Node<DataType> * BinarySearchTree<DataType>::FindMaxNon()
{
    if (root == nullptr) {
        return nullptr;
    }
    Node<DataType> *pre = root;
    Node<DataType> *cycleIter = pre->right;
    while (cycleIter != nullptr) {
        pre = cycleIter;
        cycleIter = pre->right;
    }
    return pre;
}

递归删除节点函数宗旨要素

template <typename DataType>
Node<DataType> * BinarySearchTree<DataType>::DeleteElementCore(Node<DataType> *inNode, DataType inElement)
{
    if (inNode == nullptr) {
        return nullptr;
    }
    else if (inNode->data > inElement) {
        inNode->left = DeleteElementCore(inNode->left, inElement);
    }
    else if (inNode->data < inElement) {
        inNode->right = DeleteElementCore(inNode->right, inElement);
    }
    else {
        if (inNode->left != nullptr && inNode->right != nullptr) {
            Node<DataType> *tmp = FindMinCore(inNode->right);
            inNode->data = tmp->data;
            inNode->right = DeleteElementCore(inNode->right, inNode->data);
        }
        else {
            Node<DataType> *tmp = inNode;
            if (inNode->left == nullptr) {
                inNode = inNode->right;
            }
            else {
                inNode = inNode->left;
            }
            delete  tmp;
        }
    }
    return inNode;
}

后序遍历非递归达成代码:

有二种思路:

首先种思路:对于任1结点P,将其入栈,然后沿其左子树一直往下搜寻,直到找出到未有左孩子的结点,此时该结点出现在栈顶,可是此时无法将其出栈并访问,因而其右孩子还为被访问。所以接下去依照一样的规则对其右子树举办一样的处理,当访问完其右孩虎时,该结点又出现在栈顶,此时能够将其出栈并走访。那样就保障了正确的拜访顺序。可以见到,在那些历程中,每种结点都两回面世在栈顶,只有在第3遍出现在栈顶时,本事访问它。因而必要多设置1个变量标记该结点是还是不是是第3回出现在栈顶。

/**
   * 后续遍历 非递归
   * DEFBHGICA
   *
   * @param root
   */
  public static void postOrderTraversalNODIGUI(BinTree root) {
    BinTree cur;
    BinTree pre = null;
    Stack<BinTree> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
      cur = stack.top();
      if ((cur.left == null && cur.right == null)
          || (pre != null && (pre == cur.left || pre == cur.right))) {
        System.out.println(cur.name);
        stack.pop();
        pre = cur;
      } else {
        if (cur.right != null) {
          stack.push(cur.right);
        }
        if (cur.left != null) {
          stack.push(cur.left);
        }
      }
    }
  }

其次种思路:对于任一节点,将其左子树入栈,直到左子树为空,查看当前栈顶得成分是或不是有右子树恐怕当前右子树不对等前1拜访节点,如有,重复从前将其左子树入栈,没有,访问当前节点,并把此节点出栈,并把如今节点作为走访过的节点。

 /**
   * 后续遍历 非递归
   * DEFBHGICA
   *
   * @param root
   */
  public static void postOrderTraversalNODIGUI2(BinTree root) {
    BinTree tree = root;
    BinTree cur = null;
    BinTree pre = null;
    Stack<BinTree> stack = new Stack<>();
    while (!stack.isEmpty() || tree != null) {
      while (tree != null) {
        stack.push(tree);
        tree = tree.left;
      }
      cur = stack.top();
      if (cur.right != null && (pre != null && cur.right != pre)) {
        tree = cur.right;
      } else {
        System.out.println(cur.name);
        stack.pop();
      }
      pre = cur;
    }
  }

(四)层序遍历

层序遍历用到了队列,Java中有现有的队列,所以就分选了链表式的类别。
非递归代码

/**
   * 层序遍历
   * 
   * @param boot
   */
  public static void LevelOrderTraversal(BinTree boot) {
    LinkedBlockingQueue<BinTree> queue = new LinkedBlockingQueue<>();
    BinTree tree;
    if (boot == null) return;
    queue.add(boot);
    while (!queue.isEmpty()) {
      tree = queue.remove();
      System.out.println(tree.name);
      if (tree.left != null) {
        queue.add(tree.left);
      }
      if (tree.right != null) {
        queue.add(tree.right);
      }
    }
  }
先写到那吗,等学到了再次创下新。

2017.3.9

(五)求三个贰叉树的深浅

/**
   * 树的深度
   *用到了递归
   * @param bt
   */
  public static int postOrderGetHeight(BinTree bt) {
    int leftHeight;
    int rightHeight;
    int maxHeight;
    if (bt != null) {
      leftHeight = postOrderGetHeight(bt.left);
      rightHeight = postOrderGetHeight(bt.right);
      maxHeight = leftHeight > rightHeight ? leftHeight : rightHeight;
      return maxHeight + 1;
    }
    return 0;
  }


相关文章

发表评论

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

网站地图xml地图