数据结构学习第5弹,非递归后序遍历贰叉树版本二

思路:

贰叉树的遍历

二叉树的操作有广大种,在那之中最常用的是二叉树的遍历。2叉树的遍历是指依据某种顺序访问2叉树中的每一个结点,使得各类结点都被仅且访问三次。
经过2遍完整的遍历,可使2叉树中的结点由原来的非线性体系变为某种意义的线性连串。依照根节点访问的逐一分裂,遍历的逐一分为前序遍历,中序遍历,后序遍历。

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

近日看了一下高校的数据结构,学到了从前没学到的事物看到了二叉树那一块,感到贰叉树是个很主要的东西,就看了须臾间平底是怎么落到实处的,尽管能看懂书上用c语言写的伪代码,可是不能够运营,身为贰个Java程序员,既然人家能用其余的言语能兑现,自个儿也去试着写了眨眼间间。

标志1个结点的左右子树是或不是业已被访问过,叶子节点也实行标识

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

美高梅开户网址 1

二叉树

  • 树中有3个根的非正规节点,用r解释;
  • 子树;
    树与非树?
  • 子树是不想交的;
  • 除开根节点外,各样结点点有且仅有1个父节点;
  • 壹棵N个结点的树有N-一条边;

先是付诸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;
  }
}

拓展:

先序遍历

先序遍历的递归定义:假设二叉树为空,则遍历的结果为空,否则:

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

上述图作为遍历对象的话:

  • 数据结构学习第5弹,非递归后序遍历贰叉树版本二。先拜访根节点A
  • 先序遍历根节点的左子树,然后继续服从先序遍历的逐条

  • 先走访结点B

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

末了赚取的遍历连串为: ABDEfGC

骨干术语

一、 结点的度 结点的子树个数
贰、树的度:树的持有结点最大的度数
3、叶结点:度为1的结点;
四、父节点:有子树的结点是其子树的根节点的父节点
5、子节点;
陆、兄弟结点:同壹父节点的各结点是互为的男士结点;
7、路线和路线长度;
八、祖先结点;
九、子孙节点;
1一、结点的层系;
1②、树的纵深;

达成格局

美高梅开户网址 2

image.png

二叉树:度为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特征能够达成多少个算法:(一)根到某节点的路线(二)七个节点的近年国有祖先

2叉树先序遍历递归算法的贯彻

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

首要性质

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

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

(一)先序遍历

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

美高梅开户网址 3

先序遍历.JPG

先序遍历顾名思义,便是先会遍历根节点->左孩子->右孩子。遍历是从根节点开头,碰着每种节点时,其遍历进程为:

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

typeDef struct{

二叉树先序遍历非递归算法的实现

因为实行的各类为从根节点开首,沿着左子树一贯找下去,找到底,然后回到到近来找过的结点的右子树。所以需求记录走访过的根节点,便于往回走,由于是先让根节点八个个记下起来,然后在回去的时候找近期刚找过的根节点,所以符合栈的特色(先进先出),用顺序栈存款和储蓄就可以。

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

2叉树的贮存结构

先序遍历递归完毕代码:

/**
   * 前序遍历 递归
   */
  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叉树

树立二叉树时的输入的树为把树的每3个叶子结点的男女结点填充为’#’。

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

顺序存款和储蓄结构

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

  • 父根节点 父节点[i/2]
  • 左孩子节点 二i
  • 右孩子节点贰i+1
    一般二叉树也能够动用那种结构,但会产生空间浪费。

先序遍历非递归实现代码

/**
   * 前序遍历 非递归
   * 输出结果 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

中序遍历

中序遍历的递归定义:假如2叉树为空,则遍历的结果为空,不然:

  • 中序遍历根节点的左子树
  • 做客根节点
  • 中序遍历根节点的右子树

有了先序遍历的经历,以上航海用教室作为遍历对象的话:
最终获得的遍历连串为: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

(二)中序遍历

美高梅开户网址 5

中序遍历.JPG

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

  • 中序遍历其左子树;
  • 做客根节点;
  • 中序遍历其右子树

void f(BiTree bt, ElemType x){

2叉树中序遍历递归算法完成

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

二叉树中序遍历非递归算法完毕

对于中序遍历与先序遍历分裂的是造访的次第不一样,但同样要用栈来记录

#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则表示该节点左右子树均遍历实现,则再三再四弹出直至出现第三个右子树不为空的节点,重复递归。

压栈图中,在前序遍历时,只要碰着节点(压栈进程)就直接出口就能够保险根节点首先被输出,而中序遍历由于供给在左子树输出完结后技术出口,因而如若保证在压栈重返时(出栈时)且准备遍历右子树时输出就可以。

后序遍历 非递归完成

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

过程

在沿左子树深深时,进入八个结点就将其压人货仓。倘使先序遍历,则在入栈以前访问之;
当沿左分支深人不下来时,则赶回,即从饭馆中弹出前面压人的结点;若为中序遍历,则此时作客
该结点,然后从该结点的右子树继续深切;若为后序遍历,则将此结点3回入栈,然后从该结点的
右子树继续深刻,与前边类同,仍为进入二个结点入栈1个结点,深切不下去再回来,直到第二遍
从栈里弹出该结点,才访问之。
之所以,依据上述描述的进程,使用货仓能够直接完结相应的非递归算法。先序和中序算法相
对间果些,而后序遍历因为要求一遍将3个结点人栈,意况稍复杂些。上面只以中序遍所头份
介绍二叉树遍历的非递归算法。
在按中序遍历2叉树时,遇到四个结点,就把它入栈,并去遍历它的左子树,当左子树遍历截至后,从栈顶弹出这几个结点并走访它,然后按其右指针再去中序遍历该结点的右子树。

您也许感兴趣的

贰叉树后序遍历递归算法完毕

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

假诺有七个遍历类别显著二叉树

非得要有中序遍历
一经已知先序和中序;

  1. 基于先序遍历体系第3个节点鲜明根节点;
  2. 杜绝根节点在中序遍历类别中分割出左右多少个子系列
  3. 对左子树和右子树分别递归分为左子树和右子树

(三)后序遍历

美高梅开户网址 6

此起彼伏遍历.JPG

后序遍历是指对树中任壹节点的拜访是在遍历完其左、右子树后举办的。遍历从根节点开端,遭受各个结点时,其遍历进程为:

  • 后序遍历其左子树;
  • 后序遍历其右子树
  • 走访根节点;
  • 非递归先序遍历贰叉树https://www.cnblogs.com/Coeus-P/p/9353186.html
  • 非递归后序遍历二叉树版本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叉寻找树。

对此二叉树ADT,一般供给提供以下操作:

  • 清空二叉查找树:MakeEmpty
  • 查找有些节点:Find
  • 除去有个别节点:DeleteElement
  • 搜索最大值:Find马克斯
  • 索求最小值:FindMin
  • 安插贰个节点:InsertElement
    贰叉查找树的平分深度为O(log(N)),可是假使插入成分体系递增或然递减,2叉查找树将滑坡成单链表。

后序遍历递归达成代码:

  /**
   * 后续遍历 递归
   * 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;
};

二叉查找树的基本数据成员为
递归清空核心函数:

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,将其入栈,然后沿其左子树一直往下寻觅,直到寻找到未有左孩子的结点,此时该结点出现在栈顶,不过此时不可能将其出栈并走访,由此其右孩子还为被访问。所以接下去根据同等的条条框框对其右子树举行一样的拍卖,当访问完其右孩申时,该结点又出新在栈顶,此时得以将其出栈并走访。那样就确认保障了不错的访问顺序。能够看出,在这些进程中,每一种结点都三回现身在栈顶,只有在其次次面世在栈顶时,技术访问它。由此必要多设置一个变量标志该结点是还是不是是第1次面世在栈顶。

/**
   * 后续遍历 非递归
   * 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);
        }
      }
    }
  }

其次种思路:对于任一节点,将其左子树入栈,直到左子树为空,查看当前栈顶得成分是不是有右子树也许当前右子树不对等前一造访节点,如有,重复在此之前将其左子树入栈,未有,访问当前节点,并把此节点出栈,并把当前节点作为访问过的节点。

 /**
   * 后续遍历 非递归
   * 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;
    }
  }

(4)层序遍历

层序遍历用到了队列,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地图