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

思路:

二叉树的遍历

贰叉树的操作有好二种,个中最常用的是贰叉树的遍历。二叉树的遍历是指依据某种顺序访问贰叉树中的每种结点,使得各种结点都被仅且访问叁回。
由此三遍完整的遍历,可使贰叉树中的结点由原来的非线性系列变为某种意义的线性系列。依照根节点访问的相继区别,遍历的逐一分为前序遍历,中序遍历,后序遍历。

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

多年来看了一下大学的数据结构,学到了原先没学到的事物看到了二叉树那一块,感觉贰叉树是个很重点的事物,就看了一下头部是怎么落实的,固然能看懂书上用c语言写的伪代码,但是不能够运转,身为3个Java程序员,既然人家能用别的的言语能完结,自个儿也去试着写了眨眼间间。

树与贰叉树,非递归后序遍历二叉树版本二。标记三个结点的左右子树是不是早已被访问过,叶子节点也展开标记

贰叉树的遍历方法与算法实现

亚洲必赢官网 1

二叉树

  • 树中有二个根的分歧常常节点,用r解释;
  • 子树;
    树与非树?
  • 子树是不想交的;
  • 除去根节点外,每种结点点有且仅有3个父节点;
  • 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;
  }
}

拓展:

先序遍历

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

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

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

  • 先访问根节点A
  • 先序遍历根节点的左子树,然后继续遵从先序遍历的依次

  • 先走访结点B

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

终极得到的遍历体系为: ABDEfGC

核心术语

1、 结点的度 结点的子树个数
二、树的度:树的富有结点最大的度数
3、叶结点:度为1的结点;
4、父节点:有子树的结点是其子树的根节点的父节点
5、子节点;
陆、兄弟结点:同1父节点的各结点是并行的兄弟结点;
7、路径和途径长度;
捌、祖先结点;
玖、子孙节点;
1一、结点的层系;
1二、树的吃水;

完成格局

亚洲必赢官网 2

image.png

二叉树:度为2;
出奇二叉树

  • 斜2叉树
  • 八面玲珑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特征可以达成三个算法:(1)根到某节点的路子(二)三个节点的近来公共祖先

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

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

根性情质

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

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

(壹)先序遍历

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

亚洲必赢官网 3

先序遍历.JPG

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

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

typeDef struct{

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

因为进行的各种为从根节点起先,沿着左子树一贯找下去,找到底,然后再次来到到近期找过的结点的右子树。所以要求记录走访过的根节点,便于往回走,由于是先让根节点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;

按先序系列建立二叉树

创造2叉树时的输入的树为把树的每一个叶子结点的男女结点填充为’#’。

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
  • 右孩子节点二i+1
    一般2叉树也可以选用那种结构,但会导致空间浪费。

先序遍历非递归完成代码

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

中序遍历是指对树中任1节点的走访是在遍历完其左子树后进行的,访问此结点后再对其右子树遍历。遍历从根节点早先,蒙受每一个结点时,其遍历进程为:

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

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

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

对于中序遍历与先序遍历差异的是造访的逐1不相同,但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;
    }
}

二叉树的非递归算法

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

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则代表该节点左右子树均遍历达成,则连续弹出直至现身第3个右子树不为空的节点,重复递归。

压栈图中,在前序遍历时,只要境遇节点(压栈进程)就间接出口就能够保障根节点首先被输出,而中序遍历由于须要在左子树输出实现后才能出口,因此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)
    }
}

过程

在沿左子树深深时,进入3个结点就将其压人堆栈。若是先序遍历,则在入栈在此以前访问之;
当沿左分支深人不下来时,则赶回,即从仓库中弹出前边压人的结点;若为中序遍历,则此时作客
该结点,然后从该结点的右子树继续深远;若为后序遍历,则将此结点二回入栈,然后从该结点的
右子树继续长远,与前方类同,仍为进入五个结点入栈贰个结点,深入不下去再重回,直到第三遍
从栈里弹出该结点,才访问之。
据此,依据上述描述的进程,使用堆栈能够平素促成相应的非递归算法。先序和中序算法相
对间果些,而后序遍历因为必要四次将1个结点人栈,情形稍复杂些。上边只以中序遍所头份
介绍二叉树遍历的非递归算法。
在按中序遍历二叉树时,碰到三个结点,就把它入栈,并去遍历它的左子树,当左子树遍历甘休后,从栈顶弹出那个结点并访问它,然后按其右指针再去中序遍历该结点的右子树。

你只怕感兴趣的

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

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叉树中度为二的结点
  • 递归算法–二叉树中度为一的结点
  • 非递归达成斐波那契数列
  • 非递归后序遍历贰叉树版本1
  • 层次遍历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;
            }
        }
    }
}

二叉查找树的概念与落实

静态查找:二分查找
动态查找:二叉搜索树;
也号称二叉排序树,可能2叉查找树;

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

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

  • 清空贰叉查找树:MakeEmpty
  • 搜寻有些节点:Find
  • 剔除有个别节点:DeleteElement
  • 探寻最大值:FindMax
  • 寻找最小值: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);
    }
  }

2叉树的层序遍历

对此先序,中序,后序来说,他们属于深度遍历,也等于先探到低然后再折回去。对于层序遍历来说,顾名思义,便是一层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;
}

二叉查找树的兑现

二叉树的中坚构造定义:

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

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

有三种思路:

率先种思路:对于任一结点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;
    }
  }

(四)层序遍历

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

(伍)求四个2叉树的深度

/**
   * 树的深度
   *用到了递归
   * @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地图