【4858.com】树与二叉树,非递归后序遍历二叉树版本二

By admin in 4858.com on 2019年4月1日

思路:

二叉树的遍历

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

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

近期看了一下大学的数据结构,学到了原先没学到的东西看到了二叉树那一块,感觉二叉树是个很首要的东西,就看了一下底层是怎么落到实处的,即便能看懂书上用c语言写的伪代码,可是无法运作,身为二个Java程序员,既然外人能用其余的语言能落到实处,自身也去试着写了一下。

标记一个结点的左右子树是或不是早已被访问过,叶子节点也进行标记

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

4858.com 1

二叉树

  • 树中有八个根的特有节点,用r解释;
  • 子树;
    树与非树?
  • 子树是不想交的;
  • 除了根节点外,种种结点点有且仅有叁个父节点;
  • 一棵N个结点的树有N-1条边;

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

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、子节点;
⑥ 、兄弟结点:同一父节点的各结点是互相的小兄弟结点;
⑦ 、路径和途径长度;
⑧ 、祖先结点;
九 、子孙节点;
1一 、结点的层次;
1② 、树的深浅;

贯彻方式

4858.com 2

image.png

二叉树:度为2;
新鲜二叉树

  • 斜二叉树
  • 全盘二叉树/满二叉树
  • 一心二叉树(不完全)

接下来模拟3个栈的代码,会在前边非递归的时候用到

出于只是去遍历全体节点,没有考虑品质上的题材,只是让我们探听思路,底层用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);
    }
}

首要性质

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

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

(1)先序遍历

【4858.com】树与二叉树,非递归后序遍历二叉树版本二。先看下先序遍历的流程图,接下去的代码也会根据此图是遍历

4858.com 3

先序遍历.JPG

先序遍历顾名思义,正是先会遍历根节点->左孩子->右孩子。遍历是从根节点开头,境遇每种节点时,其遍历进度为:

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

typeDef struct{

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

4858.com,因为实行的逐条为从根节点开端,沿着左子树平素找下去,找到底,然后回来到近年来找过的结点的右子树。所以须求记录走访过的根节点,便于往回走,由于是先让根节点2个个笔录起来,然后在回到的时候找近年来刚找过的根节点,所以符合栈的特征(先进先出),用顺序栈存款和储蓄即可。

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

按先序系列建立二叉树

成立二叉树时的输入的树为把树的每三个纸牌结点的男女结点填充为’#’。

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]
  • 左孩子节点 2i
  • 右孩子节点2i+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

中序遍历

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

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

有了先序遍历的经历,以上海教室作为遍历对象的话:
末尾收获的遍历体系为:DEBGfAC

链表存款和储蓄

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

4858.com 4

image.png

(2)中序遍历

4858.com 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;
}

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

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

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

二叉树的非递归算法

先序遍历的非递归:使用堆栈

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

层序遍历

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

  • 从节点访问其左、右外甥
  • 急需四个仓库储存结构保留临时不访问的结点
  • 储存结构:堆栈、队列

队列达成:遍历从根节点早先,首先将根节点入队,然后开首履行循环:结点出队,访问该结点,将左右幼子入队

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个结点就将其压人堆栈。假设先序遍历,则在入栈以前访问之;
当沿左分支深人不下来时,则赶回,即从仓库中弹出前面压人的结点;若为中序遍历,则此时造访
该结点,然后从该结点的右子树继续深远;若为后序遍历,则将此结点贰遍入栈,然后从该结点的
右子树继续深切,与前方类同,仍为进入3个结点入栈三个结点,深远不下去再重返,直到首次
从栈里弹出该结点,才访问之。
就此,依照上述描述的进程,使用堆栈能够向来促成相应的非递归算法。先序和中序算法相
对间果些,而后序遍历因为急需五遍将三个结点人栈,意况稍复杂些。上边只以中序遍所头份
介绍二叉树遍历的非递归算法。
在按中序遍历二叉树时,境遇1个结点,就把它入栈,并去遍历它的左子树,当左子树遍历结束后,从栈顶弹出那几个结点并访问它,然后按其右指针再去中序遍历该结点的右子树。

您可能感兴趣的

二叉树后序遍历递归算法实现

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

假诺有四个遍历体系明确二叉树

总得要有中序遍历
一旦已知先序和中序;

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

(3)后序遍历

4858.com 6

一连遍历.JPG

后序遍历是指对树中任一节点的访问是在遍历完其左、右子树后举办的。遍历从根节点初步,境遇各样结点时,其遍历进程为:

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

二叉树后序遍历非递归算法完结

与前序遍历和中序遍历不一致的是你跑完了左子树和右子树才能访问根节点,此时当你遍历完左子树时,你须求重返根节点,可是此时您还不能够访问,因为你要先遍历右子树所以你还要根结点再度入栈,然后下次在出栈的时候才能访问,所以这里用一个标记来拍卖

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

二叉查找树的概念与贯彻

静态查找:二分查找
动态查找:二叉搜索树;
也称为二叉排序树,大概二叉查找树;

  • 分空左子树的具有键值小于其根节点的键值。
  • 分空右子树的具备键值大于其根节点的键值。
  • 左右子树都以二叉搜索树。

对于二叉树ADT,一般必要提供以下操作:

  • 清空二叉查找树:MakeEmpty
  • 追寻有个别节点:Find
  • 去除有个别节点:DeleteElement
  • 检索最大值:Find马克斯
  • 找寻最小值:FindMin
  • 布署三个节点:InsertElement
    二叉查找树的平分深度为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);
    }
  }

二叉树的层序遍历

对于先序,中序,后序来说,他们属于深度遍历,也正是先探到低然后再折回到。对于层序遍历来说,顾名思义,就是一层一层的扫过去,所以层序遍历的艺术为先上层在下层,同层之间,从左到遍历过去。从这么的遍历描述可以看看该遍历为广度遍历,可用队列来贯彻。
上图的遍历结果为: 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;
}

二叉查找树的贯彻

二叉树的基本结构定义:

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,将其入栈,然后沿其左子树平昔往下寻找,直到搜索到没有左孩子的结点,此时该结点出现在栈顶,不过此时不可能将其出栈并访问,由此其右孩子还为被访问。所以接下去根据同等的规则对其右子树进行相同的拍卖,当访问完其右孩羊时,该结点又冒出在栈顶,此时能够将其出栈并访问。这样就保障了天经地义的拜访顺序。能够见见,在那几个历程中,各个结点都三回现身在栈顶,只有在其次次面世在栈顶时,才能访问它。由此须要多安装一个变量标识该结点是不是是第三回面世在栈顶。

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

(5)求二个二叉树的纵深

/**
   * 树的深度
   *用到了递归
   * @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地图
Copyright @ 2010-2019 美高梅手机版4858 版权所有