连式存储的二叉树结构图：

代码实现：

//-----------------------------------------创建二叉树以及添加根节点测试类-----------------------------------------------
package day0504;

/**
 * @author Czw
 * @Description 创建一棵链式二叉树
 * @Date 2019/5/4 0004 上午 10:58
 */
public class TestBinaryTree {
    public static void main ( String [] args){
        //创建一棵二叉树
        BinaryTree binTree=new BinaryTree();
        //创建一个根节点
        TreeNode root=new TreeNode(1);
        //为根节点创建左节点
        TreeNode leftNode=new TreeNode(2);
        //为根节点创建右节点
        TreeNode rightNode=new TreeNode(3);
        //为根节点赋左右节点值
        root.setLeftNode(leftNode);
        root.setRightNode(rightNode);
        //赋给树
        binTree.setRoot(root);

    }
}
//-------------------------------------链式存储的二叉树类-------------------------------------------------
package day0504;


/**
 * @author Czw
 * @Description 链式存储的二叉树
 * @Date 2019/5/4 0004 上午 10:59
 */
public class BinaryTree {
    //树的根节点
    TreeNode root;


    public void setRoot(TreeNode root) {
        this.root = root;
    }
}
//-----------------------------------------代表每个节点对象的类-----------------------------------------------
package day0504;

/**
 * @author Czw
 * @Description 链式存储二叉树的节点内容
 * @Date 2019/5/4 0004 上午 11:05
 */
public class TreeNode {
    //节点的权
    int value;
    //左儿子
    TreeNode leftNode;
    //右儿子
    TreeNode rightNode;
    public TreeNode(int value){
        this.value=value;
    }

    public void setLeftNode(TreeNode leftNode) {
        this.leftNode = leftNode;
    }

    public void setRightNode(TreeNode rightNode) {
        this.rightNode = rightNode;
    }
}

二叉树的遍历分为前、中、后三种遍历方式：

前序遍历：A B D E C F G（先取自己再去子节点，子节点若有节点同样如此）
中序遍历：D B E A F C G (先取左边子节点再自己然后右节点，若子节点有节点则同样如此）
后序遍历：D E B F G C A (先取左节点再取右节点再取自己，若有子节点则同样如此)
代码实现：

package day0504;

/**
 * @author Czw
 * @Description 测试创建一棵链式二叉树
 * @Date 2019/5/4 0004 上午 10:58
 */
public class TestBinaryTree {
    public static void main ( String [] args){
        //创建一棵二叉树
        BinaryTree binTree=new BinaryTree();
        //创建一个根节点
        TreeNode root=new TreeNode(1);
        //赋给树
        binTree.setRoot(root);
        //为根节点创建左节点
        TreeNode leftNode=new TreeNode(2);
        //为根节点创建右节点
        TreeNode rightNode=new TreeNode(3);
        //为根节点赋左右节点值
        root.setLeftNode(leftNode);
        root.setRightNode(rightNode);

        //为第二层左节点创建两个子节点
        leftNode.setLeftNode(new TreeNode(4));
        leftNode.setRightNode(new TreeNode(5));
        //为第二层右节点创建两个子节点
        rightNode.setLeftNode(new TreeNode(6));
        rightNode.setRightNode(new TreeNode(7));

        //前序遍历
        binTree.frontShow();//结果：1 2 4 5 3 6 7
        System.out.println("");
        //中序遍历
        binTree.middleShow();//结果：4 2 5 1 6 3 7
        System.out.println("");
        //后序遍历
        binTree.afterShow();//结果：

    }
}
------------------------------------------------------------------
package day0504;


/**
 * @author Czw
 * @Description 链式存储的二叉树
 * @Date 2019/5/4 0004 上午 10:59
 */
public class BinaryTree {
    //树的根节点
    TreeNode root;


    public void setRoot(TreeNode root) {
        this.root = root;
    }

    public void frontShow() {
        root.frontShow();
    }

    public void middleShow() {
        root.middleShow();
    }

    public void afterShow() {
        root.afterShow();
    }
}
---------------------------------------------
package day0504;

/**
 * @author Czw
 * @Description 链式存储二叉树的节点内容
 * @Date 2019/5/4 0004 上午 11:05
 */
public class TreeNode {
    //节点的权
    int value;
    //左儿子
    TreeNode leftNode;
    //右儿子
    TreeNode rightNode;
    public TreeNode(int value){
        this.value=value;
    }

    //前遍历
    public void frontShow(){
        System.out.print(value+" ");
        if (leftNode!=null){
            leftNode.frontShow();
        }
        if (rightNode!=null){
            rightNode.frontShow();
        }

    }




    public void setLeftNode(TreeNode leftNode) {
        this.leftNode = leftNode;
    }

    public void setRightNode(TreeNode rightNode) {
        this.rightNode = rightNode;
    }


    public void middleShow() {
        if (leftNode!=null){
            leftNode.middleShow();
        }
        System.out.print(value+" ");
        if (rightNode!=null){
            rightNode.middleShow();
        }


    }

    public void afterShow() {
        if (leftNode!=null){
            leftNode.afterShow();
        }
        if (rightNode!=null){
            rightNode.afterShow();
        }
        System.out.print(value +" ");
    }
}

查找value值相同的节点：
实现代码：

package day0504;

/**
 * @author Czw
 * @Description 测试创建一棵链式二叉树
 * @Date 2019/5/4 0004 上午 10:58
 */
public class TestBinaryTree {
    public static void main ( String [] args){
        //创建一棵二叉树
        BinaryTree binTree=new BinaryTree();
        //创建一个根节点
        TreeNode root=new TreeNode(1);
        //赋给树
        binTree.setRoot(root);
        //为根节点创建左节点
        TreeNode leftNode=new TreeNode(2);
        //为根节点创建右节点
        TreeNode rightNode=new TreeNode(3);
        //为根节点赋左右节点值
        root.setLeftNode(leftNode);
        root.setRightNode(rightNode);

        //为第二层左节点创建两个子节点
        leftNode.setLeftNode(new TreeNode(4));
        leftNode.setRightNode(new TreeNode(5));
        //为第二层右节点创建两个子节点
        rightNode.setLeftNode(new TreeNode(6));
        rightNode.setRightNode(new TreeNode(7));

        //前序遍历
        binTree.frontShow();//结果：1 2 4 5 3 6 7
        System.out.println("");
        //中序遍历
        binTree.middleShow();//结果：4 2 5 1 6 3 7
        System.out.println("");
        //后序遍历
        binTree.afterShow();//结果：4 5 2 6 7 3 1
        System.out.println();
        //查找指定元素
        TreeNode result=binTree.frontSearch(5);
        System.out.println(result);

    }
}

-------------------------------------------------------------------------------------------
package day0504;


/**
 * @author Czw
 * @Description 链式存储的二叉树
 * @Date 2019/5/4 0004 上午 10:59
 */
public class BinaryTree {
    //树的根节点
    TreeNode root;


    public void setRoot(TreeNode root) {
        this.root = root;
    }

    public void frontShow() {
        root.frontShow();
    }

    public void middleShow() {
        root.middleShow();
    }

    public void afterShow() {
        root.afterShow();
    }

    public TreeNode frontSearch(int i) {
        return root.frontSearch(i);
    }
}

--------------------------------------------------------------------------------------
package day0504;


/**
 * @author Czw
 * @Description 链式存储的二叉树
 * @Date 2019/5/4 0004 上午 10:59
 */
public class BinaryTree {
    //树的根节点
    TreeNode root;


    public void setRoot(TreeNode root) {
        this.root = root;
    }

    public void frontShow() {
        root.frontShow();
    }

    public void middleShow() {
        root.middleShow();
    }

    public void afterShow() {
        root.afterShow();
    }

    public TreeNode frontSearch(int i) {
        return root.frontSearch(i);
    }
}

二叉树的遍历

为了先了解二叉树的结构，此处先手动快速创建一棵简单的二叉树：

typedef char BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType _data;
	struct BinaryTreeNode* _left;
	struct BinaryTreeNode* _right;
}BTNode;

BTNode* BuyNode(BTDataType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	node->_data = x;
	node->_left = NULL;
	node->_right = NULL;
}

BTNode* CreatBinaryTree()
{
	BTNode* node1 = BuyNode('A');
	BTNode* node2 = BuyNode('B');
	BTNode* node3 = BuyNode('C');
	BTNode* node4 = BuyNode('D');
	BTNode* node5 = BuyNode('E');
	BTNode* node6 = BuyNode('F');
	BTNode* node7 = BuyNode('G');

	node1->_left = node2;
	node1->_right = node3;
	node2->_left = node4;
	node3->_left = node5;
	node3->_right = node6;
	node4->_left = node7;
	return node1;
}

按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历：1. 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。2. 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。3. 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。

前序遍历

void PreOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	printf("%c ", root->_data);
	PreOrder(root->_left);
	PreOrder(root->_right);
}

前序遍历递归图解：

中序遍历：

void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	InOrder(root->_left);
	printf("%c ", root->_data);
	InOrder(root->_right);
}

后序遍历

void PostOrder(BTNode* root)
{
	if (root == NULL) {
		printf("NULL ");
		return;
	}

	PostOrder(root->left);
	PostOrder(root->right);
	printf("%c ", root->data);
}

测试结果：

节点个数及高度等

求二叉树节点个数

核心思想：节点个数=1+左子树节点个数+右子树节点个数

int BinaryTreeSize(BTNode* root)
{
	return root==NULL?0:1
		+BinaryTreeSize(root->_left)
		+ BinaryTreeSize(root->_right);
}

求二叉树叶子节点个数

int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	else if (root->_left == NULL && root->_right == NULL)
		return 1;
	else
		return BinaryTreeLeafSize(root->_left)
		+ BinaryTreeLeafSize(root->_right);
}

求二叉树第k层节点个数

核心思路：当前树的第k层节点个数=当前树的左子树的第k-1层个数+当前树的右子树的第k-1层个数

int BinaryTreeLeavelKSize(BTNode* root, int k)
{
	if (root == NULL)
		return 0;
	else if (k == 1)
		return 1;
	else
		return BinaryTreeLeavelKSize(root->_left,k-1)
		+ BinaryTreeLeavelKSize(root->_right,k-1);
}

求二叉树深度/高度

核心思想：当前树的深度=max(左子树深度，右子树深度)+1

int BinaryTreeDepth(BTNode* root)
{
	if (root == NULL)
		return 0;
	
	//先给两个变量存储结果，若直接放到return就得算两次
	int leftDepth = BinaryTreeDepth(root->_left);
	int rightDepth = BinaryTreeDepth(root->_right);

	return leftDepth > rightDepth?leftDepth+1:rightDepth+1;
}

查找值为x的节点

1. 先判断是不是当前节点，是就返回
2. 不是就先去左树找，找到了就返回
3. 左树没找到，再去右树找。

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;

	if (root->_data == x)
		return root;

	BTNode* left = BinaryTreeFind(root->_left, x);
	if (left)
		return left;
	BTNode* right = BinaryTreeFind(root->_right, x);
	if(right)
	return right;

	return NULL;
}

二叉树基础oj练习

分治：大问题分成小问题，小问题再继续分，直到分割成不可再分割的子问题。

单值二叉树

题目描述：如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。只有给定的树是单值二叉树时，才返回true，否则返回false

思路：

1. ==具有传递性
2. a == b && a == c
3. b == e && b == f
4. 即a跟e和f相等。

bool isUnivalTree(struct TreeNode* root){
    if(root==NULL)
        return true;
    if(root->left && root->val != root->left->val)
        return false;
    if(root->right && root->val != root->right->val)
        return false;
    
    return isUnivalTree(root->left) 
    && isUnivalTree(root->right);
}

其中if(root->left && root->val != root->left->val) &&两边不能调换，否则如果root->left为空，但却已经进行了两个值的比较，会报错。

二叉树的前序遍历

题目描述：给你二叉树的根节点root，返回它节点值的前序遍历

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int TreeSize(struct TreeNode* root)
{
    if(root==NULL)
        return 0;
    return 1+TreeSize(root->left)+TreeSize(root->right);
}

void _preorderTraversal(struct TreeNode* root,int* arr,int* pi)
{
    if(root==NULL)
        return;

    arr[(*pi)++]=root->val;
    _preorderTraversal(root->left,arr,pi);
    _preorderTraversal(root->right,arr,pi);
}

int* preorderTraversal(struct TreeNode* root, int* returnSize){
    *returnSize=TreeSize(root);
    int* arr=(int*)malloc(sizeof(int)* *returnSize);
    int i=0;
    _preorderTraversal(root,arr,&i);
    return arr;
}

注意： 在void _preorderTraversal中，最后一个参数要传的是指针。每个递归调用栈帧中都有一个i，下一层++i，不会对上一次影响。但是我们想要的是只有一个i作为下标++

相同的树

题目描述：给你两棵二叉树的根节点p和q，编写一个函数来检验这两棵树是否相同。如果两个数在结构上相同，并且节点具有相同的值，则认为它们是相同的。

要比较两棵树是否相同，就要比较两棵树的根节点和各自的左子树和右子树是否相同。

bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{
    if(p==NULL && q==NULL)
        return true;
    if(p==NULL || q==NULL)
        return false;
    if(p->val!=q->val)
        return false;
        
    return isSameTree(p->left,q->left)
        && isSameTree(p->right,q->right);
}

• 时间复杂度：O(N)
• 空间复杂度：O(h）-> 最坏情况 O(N) 完全二叉树或满二叉树h=logN

对称二叉树

题目描述：给定一个二叉树，检查它是否是镜像对称的。

要判断是否对称，首先判断根节点是否为空，再判断根节点的左右子树是否对称，递归。

bool _isSymmetric(struct TreeNode* p, struct TreeNode* q)
{
    if(p==NULL && q==NULL)
        return true;
    if(p==NULL || q==NULL)
        return false;
    if(p->val!=q->val)
        return false;
        
    return _isSymmetric(p->left,q->right)
        && _isSymmetric(p->right,q->left);
}

bool isSymmetric(struct TreeNode* root){
    if(root==NULL)
        return true;
    
    return _isSymmetric(root->left,root->right);      
}

另一棵树的子树

题目描述：给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot)
{
    if(root==NULL)
        return false;
    if(isSameTree(root,subRoot))
        return true;
    return isSubtree(root->left,subRoot)
        || isSubtree(root->right,subRoot);
}

二叉树的创建和销毁

通过前序遍历的数组构建二叉树

问题描述：编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。

struct TreeNode
{
    char val;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct TreeNode* CreatTree(char* str,int* pi)
{
    if(str[*pi]=='#')
    {
        (*pi)++;
        return NULL;
    }
    
    struct TreeNode* root=(struct TreeNode*)
        malloc(sizeof(struct TreeNode));
    root->val=str[(*pi)++];
    root->left=CreatTree(str, pi);
    root->right=CreatTree(str, pi);
    
    return root;
}

void InOrder(struct TreeNode* root)
{
    if(root==NULL)
        return;
    InOrder(root->left);
    printf("%c ",root->val);
    InOrder(root->right);
}
int main()
{
    char str[100];
    scanf("%s",str);
    int i=0;
    struct TreeNode* root=CreatTree(str, &i);
    InOrder(root);
    return 0;
}

二叉树销毁

//二叉树销毁
void BinaryTreeDestroy(BTNode* root)
{
	if (root == NULL)
		return;

	BinaryTreeDestroy(root->_left);
	BinaryTreeDestroy(root->_right);
	free(root);
}

层序遍历

用队列实现二叉树的层序遍历。先把第一次（根）放入队列。上一层出队，带入下一层。

//层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
	{
		QueuePush(&q, root);
	}
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		printf("%c ", front->_data);
		if (front->_left)
		{
			QueuePush(&q,front->_left);
		}
		if (front->_right)
		{
			QueuePush(&q, front->_right);
		}
	}
	printf("\n");
	QueueDestroy(&q);
}

以此树为例：

测试结果：

判断是否是完全二叉树

核心思路： 层序遍历，把空的节点也入队列。如果是完全二叉树，非空节点是连续的，空也是连续的。如果不是完全二叉树，非空节点不连续，空也不连续。

bool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
	{
		QueuePush(&q, root);
	}
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front==NULL)
		{
			break;
		}
		QueuePush(&q, front->_left);
		QueuePush(&q, front->_right);
	}
	//找到空后，队列中全是空，就是完全二叉树
	//还有非空，就不是完全二叉树
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front)
		{
			QueueDestroy(&q);
			return false;
		}
	}
	QueueDestroy(&q);
	return true;
}

测试结果：

二叉树链式存储及二叉树各种遍历的算法实现

书是一种一对多的逻辑结构，在使用链式存储的时候，经常使用的是二叉链表（三个域：左孩子指针域，数据域，右孩子指针域），三叉链表（左孩子域，数据域，双亲域，右孩子域），这里使用的是二叉链表完成了几个最基本的二叉树的操作。

#include <iostream>
using namespace std;


typedef struct BiTNode
{
	char data;
	struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

//1.创建树
struct BiTNode* CreateBiTree(char data)
{
	struct BiTNode* T = (struct BiTNode*)malloc(sizeof(struct BiTNode));
	T->data = data;
	T->lchild = NULL;
	T->rchild = NULL;
	return T;
}
void insertNode(struct BiTNode* curNode, struct BiTNode* lefNode, struct BiTNode* rigNode)
{
	curNode->lchild = lefNode;
	curNode->rchild = rigNode;
}

void printData(struct BiTNode* curNode)
{
	cout << curNode->data;
}

void preorder(struct BiTNode* tree) //递归前序
{
	if (tree != NULL)
	{
		printData(tree);
		preorder(tree->lchild);
		preorder(tree->rchild);

	}
}

void midorder(struct BiTNode* tree) //递归中序
{
	if (tree != NULL)
	{
		midorder(tree->lchild);
		printData(tree);
		midorder(tree->rchild);

	}
}

void postorder(struct BiTNode* tree)  //递归后序
{
	if (tree != NULL)
	{
		postorder(tree->lchild);
		postorder(tree->rchild);
		printData(tree);
	}
}

void midorderbystack(struct BiTNode* tree)   //非递归中序遍历
{
	if (tree == NULL)
		return;
	struct BiTNode* stack[10];
	int stacktop = -1;
	struct BiTNode* pmove = tree;
	while (stacktop != -1 || pmove)
	{
		while (pmove)
		{
			stack[++stacktop] = pmove;
			pmove = pmove->lchild;
		}
		if (stacktop != -1)
		{
			pmove = stack[stacktop--];
			cout << pmove->data;
			pmove = pmove->rchild;
		}
	}
}

void preorderbystack(struct BiTNode* tree)   //非递归前序遍历
{
	if (tree == NULL)
		return;
	struct BiTNode* stack[10];
	int stacktop = -1;
	struct BiTNode* pmove = tree;
	stack[++stacktop] = pmove;
	while (stacktop != -1)
	{
		pmove = stack[stacktop--];
		cout << pmove->data;
		if (pmove->rchild != NULL)
			stack[++stacktop] = pmove->rchild;
		if (pmove->lchild != NULL)
			stack[++stacktop] = pmove->lchild;
	}
}

void postorderbystack(struct BiTNode* tree)   //非递归后序遍历
{
	if (tree == NULL)
		return;
	struct BiTNode* stack[10];
	int stacktop = -1;
	struct BiTNode* p = tree; //移动节点
	struct BiTNode* q = NULL; //标记结点
	while (p != NULL)
	{
		while (p->lchild != NULL)
		{
			stack[++stacktop] = p;
			p = p->lchild;
		}
		while (p != NULL && (p->rchild == NULL || p->rchild == q))
		{
			cout << p->data;
			q = p;
			if (stacktop == -1)
			{
				return;
			}
			p = stack[stacktop--];
		}
		stack[++stacktop] = p;
		p = p->rchild;
	}

}

void levelorderbyqueue(struct BiTNode* tree)
{
	if (tree == NULL)
	{
		return;
	}
	struct BiTNode* queue[10];
	int front, rear;
	front = rear = 0;
	struct BiTNode* p = tree;
	rear = (rear + 1) % 10;
	queue[rear] = p;
	while (front != rear)
	{
		front = (front + 1) % 10;
		p = queue[front];
		cout << p->data;
		if (p->lchild != NULL){ rear = (rear + 1) % 10; queue[rear] = p->lchild; }
		if (p->rchild != NULL){ rear = (rear + 1) % 10; queue[rear] = p->rchild; }
	}
}


void main()
{
	struct BiTNode* A = CreateBiTree('A');
	struct BiTNode* B = CreateBiTree('B');
	struct BiTNode* C = CreateBiTree('C');
	struct BiTNode* D = CreateBiTree('D');
	struct BiTNode* E = CreateBiTree('E');
	struct BiTNode* F = CreateBiTree('F');
	struct BiTNode* G = CreateBiTree('G');

	insertNode(A, B, C);
	insertNode(B, D, E);
	insertNode(D, F, NULL);
	insertNode(E, NULL, G);

	cout << "递归先序遍历："; preorder(A); cout << "\n";
	cout << "递归中序遍历："; midorder(A); cout << "\n";
	cout << "递归后序遍历："; postorder(A); cout << "\n";
	cout << "非递归先序遍历："; preorderbystack(A); cout << "\n";
	cout << "非递归中序遍历："; midorderbystack(A); cout << "\n";
	cout << "非递归后序遍历："; postorderbystack(A); cout << "\n";
	cout << "层次遍历："; levelorderbyqueue(A); cout << "\n";
	system("pause");
}

二叉树如下：

简单讲一下二叉树非递归的三种遍历方法：
1.非递归先序遍历：非递归先序遍历使用的是栈结构来实现的。大致思路是，首先将根节点入栈，只要栈不为空就出栈一个元素，然后将这个元素的右孩子和左孩子分别入栈，重复以上操作，知道栈中元素为空时，结束遍历。

2.非递归中序遍历：非递归中序遍历的方法也是栈结构来实现的。大致思路是，创建一个移动的结构体指针，如果结点不为空，则入栈，然后结构体指针指向自己的左孩子（p = p -> lchild），直到p为空为止，这时候 判断栈是否为空，如果不为空，则出栈一个元素，p指向这个出栈元素，输出这个元素，移动的结构体指针p在指向这个元素的右孩子(p = p -> rchild)，重复这部分操作，直到栈中元素为空时，结束。

3.非递归后序遍历：非递归中序遍历的方法也是栈结构来实现的。大致思路是，创建一个移动的结构体指针 p 和一个用来做标记的结构体指针 q ，首先将根节点入栈，然后将根节点的左孩子入栈，只要入栈结点的左孩子不为空时，则将元素一直入栈，当入栈元素的左孩子为空时，这时候判断 p 指向的元素的右孩子是否为空或者是否指向标记的指针，如果这个条件不满足（有右孩子），则将这个结点入栈，移动的结构体指针指向入栈元素的右孩子（p = p -> rchild），这时候重复上面的过程，当满足入栈元素的右孩子是否为空或者是否指向标记的指针时，这时候打印这个元素 p 指向的元素，然后让 q = p; 标记这个元素结点被标记（已经被遍历过了），然后出现一个元素让 p 指向这个出栈的元素。重复上述过程，当栈为空是，遍历结束。

4.层次遍历：层次遍历二叉树的方法使用队列来实现的。大致思路是，首先将根节点入队，如多队列不为空就出队一个元素，再将这个出队元素的左右孩子分别入队，重复上述步骤，如果队列为空，则层次遍历结束。

二叉树的非递归遍历需要好好理解，大家可以看我上面写的大致思路，参考代码来领悟。有不解得可以发评论或者私信。